文章目录

5.3 二叉树的遍历

5.3.1 概述

5.3.2 遍历方式【重点】

5.3.3 遍历方式：递归实现【重点】

5.3.4 遍历方式：非递归实现

5.3 二叉树的遍历

5.3.1 概述

• 二叉树的遍历：沿着某条搜索路径对二叉树中的结点进行访问，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义较为广泛，例如：输出结点信息。

• 二叉树有3条搜索路径：

  1. 先上后下

  2. 先左后右

  3. 先右后左

• 对应3条搜索路径，二叉树有7种遍历方式：

  • 先上后下

    1. 层次遍历

  • 先左后右 （D data根、 L left左、R right 右）

    1. DLR （先根遍历、先序遍历、先根序遍历）

    2. LDR （中根遍历、中序遍历、中根序遍历）

    3. LRD （后根遍历、后序遍历、后根序遍历）

  • 先右后左

    1. DRL

    2. RDL

    3. RLD

• 需要遍历的二叉树

  A

  B

  C

  D

  E

  F

  G

  H

  K

5.3.2 遍历方式【重点】

1） 层次遍历

• 若二叉树为空，则为空操作；否则，按自上而下先访问第0层的根节点，然后再从左到右依次访问各层次中的每一个结点。

• 层次遍历序列

  ABECFDGHK

2）先根（序）遍历 DLR

• 若二叉树为空，则为空操作，否则

  1. 访问根节点

  2. 先根遍历左子树

  3. 先根遍历右子树

  4. 

      

• 先根遍历序列

  ABCDEFGHK

3）中根（序）遍历 LDR

• 若二叉树为空，则为空操作；否则

  1. 中根遍历左子树

  2. 访问根节点

  3. 中根遍历右子树

• 中根遍历序列

  BDCAEHGKF

 

4）后根（序）遍历LRD

• 若二叉树为空，则为空操作；否则

  1. 后根遍历左子树

  2. 后根遍历右子树

  3. 访问根节点

• 后根遍历序列

  DCBHKGFEA

 

5）练习

• 练习1：

 

先根序遍历：ABDEGCFH

中根序遍历：DBGEAFHC

后根序遍历：DGEBHFCA

• 练习2：

  

   

  先根序遍历：ABDEGJHCFIKL

  中根序遍历：DBJGEHACKILF

  后根序遍历：DJGHEBKLIFCA

• 练习3：

  

   

  先根序遍历：ABCDEFGHK

  中根序遍历：BDCAEHGKF

  后根序遍历：DCBHKGFEA

5.3.3 遍历方式：递归实现【重点】

1）算法：先根（序）遍历 DLR

public void preRootTraverse(BiTreeNode T) {if(T != null) {System.out.print(T.data);       //输出根元素preRootTraverse(T.lchild);      //先根遍历左子树preRootTraverse(T.rchild);      //先根遍历右子树}
}

2）算法：中根（序）遍历 LDR

public void inRootTraverse(BiTreeNode T) {if(T != null) {inRootTraverse(T.lchild);       //中根遍历处理左子树System.out.print(T.data);       //访问根节点inRootTraverse(T.rchild);       //中根遍历处理右子树}
}

3）算法：后根（序）遍历LRD

public void postRootTraverse(BiTreeNode T) {if(T != null) {postRootTraverse(T.lchild);     //后根遍历左子树postRootTraverse(T.rchild);     //后根遍历右子树System.out.print(T.data);       //访问根结点}
}

4）动画演示：后根遍历

 

5.3.4 遍历方式：非递归实现

1）分析：先根（序）遍历 DLR

• 借助一个==栈==来记录当前被访问结点的右孩子结点，以便遍历完一个结点的左子树后，可以继续遍历该结点的右子树。

• 实现思想：

  1. 将根节点压栈

  2. 从栈顶获得需要遍历的结点A，并访问结点A。

  3. 此时结点A有左孩子直接访问，结点A有右孩子压入栈顶

  4. 同时沿着左子树继续搜索，重复步骤3

  5. 当左子树访问完成后，重复步骤2依次访问对应的右子树

2）算法：先根（序）遍历 DLR【重点】

public void preRootTraverse() {BiTreeNode T = root;if( T != null ) {LinkStack S = new LinkStack();      // 创建栈记录没有访问过的右子树S.push(T);                          // 将根节点压入栈顶while(!S.isEmpty()) {               // 栈中只要有数据，表示继续遍历T = S.pop();                    // 弹出栈顶数据System.out.print(T.data);       // 结点被访问while(T != null) {              // T指针，访问每一个左孩子if(T.lchild != null) {      // 输出左孩子System.out.print(T.lchild.data);}if(T.rchild != null) {      // 将右孩子压栈T.push(T.rchild);}T = T.lchild;               // 访问下一个左孩子}}}
}

3）分析：中根（序）遍历 LDR

• 借助一个==栈==来记录遍历过程中所经历的而未被访问的所有结点，以便遍历完左子树后能顺利的返回到它的父节点。

• 实现思想

  1. 从非空二叉树的根节点出发

  2. 沿着该结点的左子树向下搜索，在搜索过程中将遇到的每一个结点依次压栈，直到二叉树中最左下结点压栈为止，

  3. 然后从栈中弹出栈顶结点并对其进行访问，访问完成后再进入该结点的右子树，

  4. 并用上述相同的方法去遍历该结点的右子树，直到二叉树中所有的结点都被访问。

4）算法：中根（序）遍历 LDR

public void inRootTraverse() {BiTreeNode T = root;if(T != null) {LinkStack S = new LinkStack();S.push(T);                          //将根节点压入到栈顶while( !S.isEmpty() ) {             //栈中有数据，表示遍历未完成//1 将所有的左孩子压栈while(S.peek() != null) {       //栈顶的元素不为空，注意：不是弹栈// 获得栈顶，BiTreeNode temp = (BiTreeNode)S.peek();// 并将左孩子压入栈顶S.push(temp.lchild);}S.pop();                        //将栈顶的空元素弹出//2 依次弹出栈，访问当前节点，如果有右孩子继续压栈if(! S.isEmpty()) {T = (BiTreeNode)S.pop();System.out.print(T.data);       //访问栈顶S.push(T.rchild);}}}
}

5）分析：后根（序）遍历LRD

• 借助一个栈用记载遍历过程中所经历而未被访问的所有结点。

  • 确定顶点结点是否能访问，需要知道该结点的右子树是否被遍历完成。

  • 引入两个变量，一个访问标记变量flag和一个结点指针p

    • flag永不标记当前栈顶结点是否被访问

    • p指向当前遍历过程中最后一个被访问的结点。

• 实现思想

  1. 从非空二叉树的根节点出发

  2. 将所有的左孩子相继压栈，

  3. 然后获得栈中每个结点A，如果该结点A没有右孩子或右孩子已经访问过，将访问结点A

  4. 如果结点A有右孩子或右孩子未被访问过，继续压栈

  5. 通过标记，使程序开始出了新添加进入的结点。

6）算法：后根（序）遍历LRD

public void postRootTraverse() {BiTreeNode T = root;if( T != null) {LinkStack S = new LinkStack();S.push(T);// 声明两个变量Boolean flag;               //用于记录是否被访问BiTreeNode p;               //用于记录上一次处理的结点while(! S.isEmpty() ) {//1 将所有的左孩子压栈while(S.peek() != null) {       //栈顶的元素不为空，注意：不是弹栈// 获得栈顶，BiTreeNode temp = (BiTreeNode)S.peek();// 并将左孩子压入栈顶S.push(temp.lchild);}S.pop();                        //将栈顶的空元素弹出while( !S.isEmpty() ) {T = (BiTreeNode) S.peek();if(T.rchild == null || T.rchild == p) {  // 没有右孩子 或 已经访问过System.out.print(T.data);S.pop();                    //弹出p = T;                      //记录刚才访问过的flag = true;            //没有新元素，继续访问} else {S.push(T.rchlid);flag = false;           //新右子树添加}if(!flag) {break;              //如果有右子树，需要重新开始}}}}
}