5-5 遍历二叉树的非递归算法

中序遍历非递归算法

二叉树中序遍历的非递归算法的关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树

基本思想：

1. 建立一个栈
2. 根结点进栈，遍历左子树
3. 根结点出栈，输出根结点，遍历右子树

代码：

Status InOrderTraverse(BiTree T) {
	BiTree p; InitStack(S); p = T;
	while(p || !StackEmpty(S)) {
		if(p) {
			Push(S, p);
			p = p->lchild;
		//如果此根结点的左子树不存在，则从栈中出栈最上面的元素，然后遍历该元素的右子树
		} else {
			Pop(S, q);
			printf（"%c", q->data);
			p = q->rchild;
		}
	}
	return OK;
}

5-5 二叉树的层次遍历

二叉树的层次遍历

层次遍历：对于一棵二叉树，从根节点开始，按从上到下，从左到右的顺序访问每一个结点。（每一个结点仅仅访问一次）

算法设计思路：使用一个队列

1. 将根结点入队
2. 队不空时循环：从队列中列出一个结点*p，访问它：
   1. 若它有左孩子结点，将左孩子结点进队；
   2. 若他有右孩子结点，将右孩子结点进队

二叉树层次遍历算法：

void LevelOrder(BTNode *b) {
	BTNode *p; SqQueue *qu;
	InitQueue(qu); //初始化队列
	enQueue(qu, b); //根结点指针进入队列
	while(!QueueEmpty(qu)) { //队不为空，则循环
		deQueue(qu, p); //出队结点p
		printf("%c", p->data); //访问结点p
		if(p->lchild!=NULL) //若p有左孩子，将其左孩子结点入队
			enQueue(qu, p->lchild);
		if(p->rchild != NULL) //若p有右孩子，将其右孩子结点入队
			enQueue(qu, p->rchild);
	}
}