二叉树的遍历

递归遍历

递归遍历写起来比较简单,代码也很简洁

前序遍历/先序遍历

1
2
3
4
5
6
7
void preorder(BTree *p) {
if (p!=NULL) {
Visit(p);
preorder(p->lchild);
preorder(p->rchild);
}
}

中序遍历

1
2
3
4
5
6
7
void inorder(BTree *p) {
if (p!=NULL) {
inorder(p->lchild);
Visit(p);
inorder(p->rchild);
}
}

后序遍历

1
2
3
4
5
6
7
void postorder(BTree *p) {
if (p!=NULL) {
postorder(p->lchild);
postorder(p->rchild);
Visit(p);
}
}

非递归遍历

递归遍历是通过系统栈实现的,需要很大的开销