[回忆梳理] 二叉树遍历

前序遍历

概括为根 --> 左 --> 右，具体为遇到根节点就返回，然后同层次没有结点时遍历左子树，遍历左子树遇到根就返回，然后继续遍历左子树，如果没有左子树时，遍历右子树，依旧是先根然后左，然后右，以下二叉树的前序遍历结果为ABDGHCEIF

另外从前序遍历的结果可以推测出第一个结点是根节点，往下继续，如果能确定一棵新的子树，那么第一个结点一定是子树的根结点

前序遍历示意图

• 遍历算法的伪代码为

  
  

中序遍历

概括为左 --> 根 --> 右，但是与前序不同的是，先一直向左子树查找，当查找到没有左子树的时候则返回该结点，然后返回该结点对应的根节点，然后返回该结点对应的右结点，所以上图二叉树的中序遍历顺序为 GDHBAEICF,

如果前序和中序结合来看，通过前序找到根以后，那么以这个点为分界，中序的结果的左右两部分分别为左右有两棵子树，绕后根节点一定是处于中间的位置，如果没有左或者没有右的情况，那么中序的根一定是在左或者右的位置

• 遍历算法的伪代码为

  
  

后序遍历

概括为左--> 右 --> 根，与中序很相似，先一直向左子树查找，当查找到没有左子树的时候则返回该结点，然后返回该结点对应的右结点，然后返回该结点对应的根结点，所以上图二叉树的中序遍历顺序为 GHDBIEFCA,

根据规则可以看出，后序遍历的最后一个元素一定是整棵树的根节点，并且在每一颗子树的根节点都是在最后，然后如果结合中序遍历的数序就可以推导出整棵二叉树的结构

• 遍历算法的伪代码为

  
  

二叉树的建立

这里之所以要说一下二叉树的建立，是因为建立二叉树和遍历二叉树的原理一样，显示将一颗二叉树以一定顺序遍历出结果，然后利用该种顺序的算法去创建二叉树，将之前遍历二叉树时打印结点的代码改为创建结点的代码

在遍历过程中为了使其结构完整，我们使每个结点都有孩子结点，没有的用# 表示，表示这是一空值

这种被扩展以后的二叉树前序遍历顺序为AB#D##C##，然后我们按照这个顺序去编写算法

其他两种方式创建二叉树不再赘述