数据结构 · 二叉树遍历

一：创建二叉树结构

1 struct tree{
2     char c;
3     tree left;
4     tree right;
5 };

二：基于BFS的递归遍历：

1、先序遍历

1 void preorder(tree t){
2     if(!t) 
3         return;
4     visit(t);
5     preorder(t->left);
6     preorder(t->right);
7 }

2、中序遍历

1 void inorder(tree t){
2     if(!t)
3         return;
4     lastorder(t->left);
5     visit(t);
6     lastorder(t->right);
7 }

3、后序遍历

1 void lastorder(tree t){
2     if(!t)
3         return;
4     inorder(t->left);
5     inorder(t->right);
6     visit(t);
7 }

三：基于BFS的层序遍历

　　层序遍历用队列实现，从根节点开始，首先将根节点入队，然后执行循环：结点出队并访问，左右结点入队，直到队列为空，形成按广度优先搜索（BFS）的遍历方式。

基本过程：

　　1) 根节点入队；

　　2) 从队列中出队一个结点；

　　3) 访问该结点；

　　4) 如果该结点左右子结点非空，依次入队；

　　5) 队列为空，遍历结束。

 1 void  cengorder(tree t){
 2     if(!t)
 3         return;
 4     queue<tree> re;
 5     tree p = T;
 6     re.push(p);
 7     while(!re.empty()){
 8         p = re.front();
 9         visit(p);
10         if(p->left)
11             re.push(p->left);
12         if(p->right)
13             re.push(p->right)
14     }
15 }