一、树的基本知识（一）树的基本结构一棵二叉树中的每个节点最多有两个子节点，可以分别称为左子节点和右子节点分别是节点。二叉树的根节点没有父节点，非空二叉树只有一个父节点。二叉树的叶节点没有子节点。名词解释：叶节点：如果一个节点没有子节点，那么它就是叶节点。例如图1中的二叉树，节点4、5、6、7没有子节点，所以节点4、5、6、7都是叶子节点。(2)二叉树的递归性二叉树是一种典型的具有递归性的数据结构。二叉树的根节点可能有子节点，子节点是对应子树的根节点，子树也可能有自己的子节点。例如图1中的节点1是二叉树的根节点，节点1有左子节点2和右子节点3。节点2是左子树的根节点，节点2也有子节点。既然具有递归的性质，自然要用递归来遍历一棵二叉树。(3)创建二叉树定义一个二叉树数据结构classNode{public$left=NULL;公共$right=NULL;公共$数据；公共函数__construct($data){$this->data=$data;}}二、中序遍历（1）什么是中序遍历？先遍历二叉树的左子树，再遍历二叉树的根节点，最后遍历二叉树的右子树。例如，如果按顺序遍历图1中的二叉树，依次遍历节点4、节点2、节点5、节点1、节点6、节点3、节点7。(2)递归实现(1)参考代码：classTree{public$nodes=[];//Node类就是上面创建二叉树的Node类。publicfunctioninorderTraversal(Node$root){$this->dfs($root,$this->nodes);返回$this->nodes;}publicfunctiondfs($root,$nodes){if($root!=NULL){$this->dfs($root->left,$nodes);$this->nodes[]=$root->data;$this->dfs($root->right,$nodes);}}}(2)代码分析：在我之前写的《递归十诫》博客中，递归的对象是一个列表。递归二叉树时，也可以参考《递归十诫》。①第一条诫命：递归列表时，空是所有问题的第一道；根据二叉树的递归特性，可以得出结论，在递归一棵二叉树时，根节点是否为空是首要问题。其实也很好理解：当输入为空二叉树时，无法进行递归。publicfunctiondfs($root,$nodes){if($root!=NULL){...}}②第四条诫命：至少改变一个参数，参数必须朝着结束条件的方向改变，changed参数必须在最后进行测试。在这里，主要的变化是根节点。将当前根节点的左右子节点作为下一次调用的根节点。公共函数dfs($root,$nodes){...$this->dfs($root->left,$nodes);...$this->dfs($root->right,$nodes);...}③顺序：按照中序遍历的顺序，先递归左子树，再遍历根节点，最后递归右子树。(3)迭代实现在使用迭代实现之前，需要先了解本博客的主题——深度优先搜索。(1)什么是深度优先搜索？DepthFirstSearch（简称DFS），其原理是沿着一条路径寻找最深的结点，当没有子结点时，返回上一层结点，找到另一个子结点，继续向下遍历，没有则返回向上一层直到遍历所有节点，每个节点只能访问1次。(2)参考代码：classTree{public$nodes=[];公共$堆栈=[]；publicfunctioninorderTraversal(Node$root){$cur=$root;while($cur!=NULL||!empty($this->stack)){while($cur!=NULL){array_push($this->stack,$cur);$cur=$cur->左；}$cur=array_pop($this->stack);array_push($this->nodes,$cur->data);$cur=$cur->右；}返回$this->nodes;}}(3)代码分析：①沿着当前节点的左子节点指针一直向左走，直到遇到第一个缺少左子节点的节点N，将一路遇到的节点存入堆栈。此时栈顶是第一个在向左走的路上遇到的缺少左子节点的节点N。publicfunctioninorderTraversal(Node$root){//变量cur代表当前遍历的节点。$cur=$root;while($cur!=null||!empty($this->stack)){while($cur!=null){array_push($this->stack,$cur);}$cur=$cur->左；}...}...}②节点N出栈，保存节点N的值。③将当前节点的值更新为节点N的右子节点。再次循环，②和③步骤代码如下：publicfunctioninorderTraversal(Node$root){$cur=$root;while($cur!=null||!empty($this->stack)){...$cur=array_pop($this->stack);array_push($this->nodes,$cur->data);$cur=$cur->右；}return$this->nodes;}总结：一直向左走Black，直到遇到结点N（第一个缺少左子结点的结点），左边走不过去，然后检查右边的是否节点N可以通过：如果可以通过，则继续向左一直走。如果不行，则返回到节点N的根节点R，到节点R的右边，然后继续向左走。这个循环重复，直到遍历所有节点。3、先序遍历（1）什么是先序遍历？先遍历二叉树的根节点，再遍历二叉树的左子树，最后遍历二叉树的右子树。例如，如果先序遍历图1中的二叉树，则依次遍历节点1、节点2、节点4、节点5、节点3、节点6、节点7。(2)递归实现前序遍历的递归代码实现与中序遍历的递归代码实现类似，只需要调整递归函数中代码的顺序即可。树类{public$nodes=[];publicfunctioninorderTraversal(Node$root){$this->dfs($root,$this->nodes);返回$this->nodes;}publicfunctiondfs($root,$nodes){if($root!=NULL){$this->nodes[]=$root->data;$this->dfs($root->left,$nodes);$this->dfs($root->right,$nodes);}}}(3)迭代前序遍历的迭代代码与中序遍历的迭代代码类似。它们唯一的区别是，前序遍历在左子节点指针向下移动时，将遍历遇到的每个节点都加入栈中。这是由前序遍历的顺序决定的。前序遍历先遍历根节点，再遍历其左子节点。树类{public$nodes=[];公共$堆栈=[]；公共函数preOrderTraversal(Node$root){$cur=$root;while($cur!=NULL||!empty($this->stack)){while($cur!=NULL){array_push($this->nodes,$cur->data);array_push($this->stack,$cur);$cur=$cur->左；}$cur=array_pop($this->stack);$cur=$cur->右；}返回$this->nodes;}}4.后序遍历（1）什么是后序遍历？先遍历二叉树的左子树，再遍历二叉树的右子树，最后遍历二叉树的根节点。例如，如果先序遍历图1中的二叉树，则依次遍历节点4、节点5、节点2、节点6、节点7、节点3、节点1。(2)递归实现后序遍历的递归代码实现与中序遍历的递归代码实现类似，只需要调整递归函数中代码的顺序即可。树类{public$nodes=[];公共函数postOrderTraversal(Node$root){$this->dfs($root,$this->nodes);返回$this->nodes;}publicfunctiondfs($root,$nodes){if($root!=NULL){$this->dfs($root->left,$nodes);$this->dfs($root->right,$nodes);$this->nodes[]=$root->data;}}}(3)迭代实现与中序遍历和前序遍历相比，后序遍历的迭代代码稍微复杂一些。到达一个结点时：如果之前没有遍历过它的右子树，就要去它的右子结点。如果之前已经遍历过节点的右子树，则可以遍历该节点。也就是说，此时需要根据其之前没有遍历过的右子树来判断当前节点是否应该遍历：如果之前右子树中最后遍历过的节点应该是本节点的根节点右子树，即当前节点右子节点的节点。可以记录上一个遍历的节点。如果一个节点有右孩子，而右孩子刚好是之前遍历过的节点，那么它的右子树已经遍历完了，就该遍历当前节点了。树类{public$nodes=[];公共$堆栈=[]；公共函数postOrderTraversal(Node$root){$cur=$root;$prev=NULL;while($cur!=NULL||!empty($this->stack)){while($cur!=NULL){array_push($this->stack,$cur);$cur=$cur->左；}$cur=$this->stackPeek($this->stack);如果($cur->right!=NULL&&$cur->right!=$prev){$cur=$cur->right;}else{array_pop($this->stack);$this->nodes[]=$cur->data;$prev=$cur;$cur=NULL;}}返回$this->nodes;}publicfunctionstackPeek($stack){return$stack[count($stack)-1];}}总结：只有当栈顶元素的右子节点不为空且不等于前一个节点时，才能向右走。参考文献《剑指offer》二叉树深度优先遍历?
