数据结构-5.6.二叉树的首阶、中阶和尾阶遍历

一.遍历：

---

二.二叉树的遍历：利用了递归操作

1.简介：

二叉树的先序遍历，中序遍历，后序遍历都是以根结点遍历顺序为准的，如先序遍历就先遍历根结点

2.实例：

例一：

例二：

• 先序遍历：

  

• 中序遍历：

  

• 后序遍历：

  

叶子结点可以当作是左结点和右结点都是空结点的结点：

3.练习：

注：左子树的全部结点遍历完后才会开始遍历右子树

如果一个结点是分支结点而不是叶子结点的话，就需要嵌套递归的按照特定的遍历序列把该结点展开到下一级

---

三.遍历二叉树的代码实现：

1.先序遍历：

2.中序遍历：

3.后序遍历：

• 上述代码(先/中/后序遍历的代码)的visit函数没有固定内容，他是用来访问根结点的，比如内容可以是打印根结点，修改根结点等；

• 当PreOrder函数的形参T为NULL时，就会停止访问结点即递归停止；

4.以先序遍历为例，分析其代码的递归过程：路过结点不代表就访问该结点，是否访问该结点和采取的遍历方式有关

首先传入结点A，压入栈顶：

结点A不为空(因为为空的话就不会有下面的结点了)，系统会记录该行代码的位置，再访问结点A的左子结点，递归调用函数后传入A的左子结点，访问A的左子结点即B结点，B结点不为空压入栈顶，再记录操作结点B这行代码的位置：

访问B的左子结点，B的左子结点D不为空，会压入栈顶，再访问D的左子结点：

D的左子结点为空，因此这一层函数中不做任何处理：

此时操作D的左子结点的函数就需要出栈，此时就返回到对结点D处理的这一次函数：

操作D结点的第126行代码执行完毕，就该执行第127行代码，此时传入的参数就是D结点的右子结点即G结点：

访问G结点，G结点压入栈顶：

此时该访问G结点的左子结点，G结点的左子结点为空：

由于G结点的左子结点为空，所以什么都不做：

回到G结点这一层函数，此时该执行第127行代码，访问G结点的右子结点：

由于G结点的右子结点为空，所以什么都不做：

此时操作G结点的这一层函数执行完毕，回到操作D结点的这一层函数：

此时操作D结点的这一层函数执行完毕，回到操作B结点的这一层函数：

回到B结点这一层函数，此时该执行第127行代码，访问B结点的右子结点即E结点，易知E结点访问完之后就会回到操作B结点的这一层函数：

操作B结点的这一层函数也已经执行完毕，回到操作A结点的这一层函数，执行第127行代码：

操作A的右子结点C，之后的操作过程和之前同理，这里就不再赘述：

过程解析：

5.中序遍历和后序遍历的解析：

6.递归算法进行遍历二叉树的空间复杂度为O(h)，其中h为二叉树的高度，加一是因为叶子节点下面还有两个空结点，所以处理空结点的这层函数仍然需要把它的信息压入栈顶，因此空间复杂度为O(h+1)，等价于O(h):

7.小练习：

---

四.求树的深度(应用)：

二叉树有根结点，左子树和右子树的递归特性，所以要求二叉树的高度的话，应该先递归的求出左子树的高度，再求出右子树的高度，之后选择左子树和右子树当中高度较大的那一个，加一就是该二叉树的高度(加一是因为那个根结点)：

---

五.总结：

---