二叉树的遍历

发表于 分类于 阅读次数： 1
【未完待续】二叉树的深度优先，广度优先遍历的递归与非递归代码实现

递归遍历

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

前序遍历/先序遍历

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);
    }
}

非递归遍历

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