在学习数据结构二叉树这块的时候,遍历二叉树无疑是一个重中之重,比如我们在做一个学生管理系统的时候,我们要查某个学生基本信息表数据库,还得访问他的家庭信息,成绩信息,生平信息等却不再一个表上,但是能从表A读取到表B和C,表B读取到表D和表E,环环相扣,如果要将这些数据遍历出来,那也是需要一定算法的。今天我就用四种算法来遍历二叉树。
![](https://img.haomeiwen.com/i17073306/aa3c8cd148e377d8.png)
1.先序遍历
- 先访问根节点
- 再访问左子树
- 最后访问右子树
例子图P 先序 访问的结果为 ABCDEF
先序解析:
根据上述的三点原则,我用一串 小明语言代码来解释下,代码而非判断,而是根据例子图P来做的解释
小明代码:把例子图p的排序规则转换为代码形式,代码形式能又转换为口头语言,非运行语言。
1. A start
2. A=true=getA; //A
3. A.left=true=getB;//B
4. B.left=C=true=getC;//C
5. C.left=null;C.right=null; return B;
6. B.right=true=getD;//D
7. D.left=null;D.right=null;return B;return A;
8. A.right=true=getE;//E
9. E.left=null; E.right=true=getF;//F
//连起来就是先序遍历的结果
从上述的小明语言代码可以发现每个结点都是先get它(取出打印此结点,也就是先访问根结点),然后访问的该节点的左节点,然后右节点,后面的大体原理一样
![](https://img.haomeiwen.com/i17073306/aa3c8cd148e377d8.png)
2.中序遍历
- 先访问左子树
- 再访问根节点
- 最后访问右子树
例子图P 中序 访问的结果为 CBDAEF
中序解析:
1. start A
2. A.left.left=B.left=true=getC; //C
3.return B;getB;//B
4.B.right=true=getD;//D
5.return B;return A;getA;//A
6.A.right.left=E.left=null;getE;//E
7.E.right=true=getF;//F
![](https://img.haomeiwen.com/i17073306/aa3c8cd148e377d8.png)
3.后序遍历
- 先访问左子树
- 再访问右子树
- 最后访问根节点
例子图P 后序 访问的结果为CDBFEA
后序解析:
start A
A.left.left=B.left=true=getC;
B.right=true=getD;
return B;getB;
return A;
A.right.left=E.left=null;
E.right=true=getF;
return E;getE;
return A;getA;
![](https://img.haomeiwen.com/i17073306/aa3c8cd148e377d8.png)
4.层序遍历
- 一层一层来遍历
例子图P 层序遍历 访问的结果为ABECDF
层序解析:
在代码中 我们以队列的方式进行遍历,根据先进先出的原则。
getA
getA.left=B;
getA.right=E
getB.left=C; getB.right=D;
getE.left=null;getE.right=F;
网友评论