[数据结构与算法]二叉树遍历

先序遍历

规则：

1. 根节点
2. 左孩子节点
3. 右孩子节点

递归

void preorder_traversal(BiTree T){
	if(T == NULL)
		return;
	visit(T->data);
	preorder_traversal(T->lchild);
	preorder_traversal(T->rchild);
}

非递归

void preorder_traversal(BiTree T){
	if(T == NULL)
		return;
	BiTree *p;
	p=&T;
	InitStack(S);
	while(p||!StackEmpty(S)){
		while(p){
			S.Push(p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			p=S.Top();
			S.Pop();
			visit(p->data);
			p=p->rchild;
		}
	}
}

中序遍历

规则：

1. 左孩子节点
2. 根节点
3. 右孩子节点

递归

void inorder_traversal(BiTree T){
	if(T == NULL)
		return;
	inorder_traversal(T->lchild);
	visit(T->data);
	inorder_traversal(T->rchild);
}

非递归

void inorder_traversal(BiTree T){
	if(T == NULL)
		return;
	BiTree *p;
	p=&T;
	InitStack(S);
	while(p||!StackEmpty(S)){
		while(p){
			visit(p->data);
			S.Push(p);
			p=p->lchild;
		}
		if(!StackEmpty(S)){
			p=S.Top();
			S.Pop();
			p=p->rchild;
		}
	}
}

后序遍历

规则：

1. 左孩子节点
2. 右孩子节点
3. 根节点

递归

void postorder_traversal(BiTree T){
	if(T == NULL)
		return;
	postorder_traversal(T->lchild);
	postorder_traversal(T->rchild);
	visit(T->data);
}

非递归

void postorder_traversal(BiTree T){
	if(T == NULL)
		return;
	BiTree *Cur,*preVisit;
	Cur=&T;
	preVisit=NULL;
	InitStack(S);
	while(Cur){
		S.push(Cur);
		Cur=Cur->lchild;
	}
	while(!StackEmpty(S)){
		if(Cur->rchild==NULL || Cur->rchild==preVisit){
			visit(Cur->data);
			preVisit=Cur;
		}else{
			if(Cur->lchild==preVisit){
				Cur=Cur->rchild;
				while(Cur){
					S.push(Cur);
					Cur=Cur->lchild;
				}
			}
		}
	}
}