5.3 二叉树的遍历
5.3.1 概述
- 二叉树的遍历:沿着某条搜索路径对二叉树中的结点进行访问,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义较为广泛,例如:输出结点信息。
- 二叉树有3条搜索路径:
- 先上后下
- 先左后右
- 先右后左
- 对应3条搜索路径,二叉树有7种遍历方式:
- 先上后下
- 层次遍历
- 先左后右 (D data根、 L left左、R right 右)
- DLR (先根遍历、先序遍历、先根序遍历)
- LDR (中根遍历、中序遍历、中根序遍历)
- LRD (后根遍历、后序遍历、后根序遍历)
- 先右后左
- DRL
- RDL
- RLD
- 需要遍历的二叉树
A
B
C
D
E
F
G
H
K
5.3.2 遍历方式【重点】
1) 层次遍历
- 若二叉树为空,则为空操作;否则,按自上而下先访问第0层的根节点,然后再从左到右依次访问各层次中的每一个结点。
- 层次遍历序列
ABECFDGHK
2)先根(序)遍历 DLR
- 若二叉树为空,则为空操作,否则
- 访问根节点
- 先根遍历左子树
- 先根遍历右子树
- 先根遍历序列
ABCDEFGHK
3)中根(序)遍历 LDR
- 若二叉树为空,则为空操作;否则
- 中根遍历左子树
- 访问根节点
- 中根遍历右子树
- 中根遍历序列
BDCAEHGKF
4)后根(序)遍历LRD
- 若二叉树为空,则为空操作;否则
- 后根遍历左子树
- 后根遍历右子树
- 访问根节点
- 后根遍历序列
DCBHKGFEA
5)练习
- 练习1:
先根序遍历:ABDEGCFH
中根序遍历:DBGEAFHC
后根序遍历:DGEBHFCA
- 练习2:
先根序遍历:ABDEGJHCFIKL
中根序遍历:DBJGEHACKILF
后根序遍历:DJGHEBKLIFCA
- 练习3:
先根序遍历:ABCDEFGHK
中根序遍历:BDCAEHGKF
后根序遍历:DCBHKGFEA
5.3.3 遍历方式:递归实现【重点】
1)算法:先根(序)遍历DLRpublicvoidpreRootTraverse(BiTreeNodeT) { if(T!=null) { System.out.print(T.data); //输出根元素preRootTraverse(T.lchild); //先根遍历左子树preRootTraverse(T.rchild); //先根遍历右子树 } } 2)算法:中根(序)遍历LDRpublicvoidinRootTraverse(BiTreeNodeT) { if(T!=null) { inRootTraverse(T.lchild); //中根遍历处理左子树System.out.print(T.data); //访问根节点inRootTraverse(T.rchild); //中根遍历处理右子树 } } 3)算法:后根(序)遍历LRDpublicvoidpostRootTraverse(BiTreeNodeT) { if(T!=null) { postRootTraverse(T.lchild); //后根遍历左子树postRootTraverse(T.rchild); //后根遍历右子树System.out.print(T.data); //访问根结点 } }
5.3.4 遍历方式:非递归实现
1)分析:先根(序)遍历 DLR
- 借助一个==栈==来记录当前被访问结点的右孩子结点,以便遍历完一个结点的左子树后,可以继续遍历该结点的右子树。
- 实现思想:
- 将根节点压栈
- 从栈顶获得需要遍历的结点A,并访问结点A。
- 此时结点A有左孩子直接访问,结点A有右孩子压入栈顶
- 同时沿着左子树继续搜索,重复步骤3
- 当左子树访问完成后,重复步骤2依次访问对应的右子树
2)算法:先根(序)遍历 DLR【重点】
publicvoidpreRootTraverse() { BiTreeNodeT=root; if( T!=null ) { LinkStackS=newLinkStack(); // 创建栈记录没有访问过的右子树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)
3)分析:中根(序)遍历 LDR
- 借助一个==栈==来记录遍历过程中所经历的而未被访问的所有结点,以便遍历完左子树后能顺利的返回到它的父节点。
- 实现思想
- 从非空二叉树的根节点出发
- 沿着该结点的左子树向下搜索,在搜索过程中将遇到的每一个结点依次压栈,直到二叉树中最左下结点压栈为止,
- 然后从栈中弹出栈顶结点并对其进行访问,访问完成后再进入该结点的右子树,
- 并用上述相同的方法去遍历该结点的右子树,直到二叉树中所有的结点都被访问。
4)算法:中根(序)遍历 LDR
publicvoidinRootTraverse() { BiTreeNodeT=root; if(T!=null) { LinkStackS=newLinkStack(); S.push(T); //将根节点压入到栈顶while( !S.isEmpty() ) { //栈中有数据,表示遍历未完成//1 将所有的左孩子压栈while(S.peek() !=null) { //栈顶的元素不为空,注意:不是弹栈// 获得栈顶,BiTreeNodetemp= (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指向当前遍历过程中最后一个被访问的结点。
- 实现思想
- 从非空二叉树的根节点出发
- 将所有的左孩子相继压栈,
- 然后获得栈中每个结点A,如果该结点A没有右孩子或右孩子已经访问过,将访问结点A
- 如果结点A有右孩子或右孩子未被访问过,继续压栈
- 通过标记,使程序开始出了新添加进入的结点。
6)算法:后根(序)遍历LRD
publicvoidpostRootTraverse() { BiTreeNodeT=root; if( T!=null) { LinkStackS=newLinkStack(); S.push(T); // 声明两个变量Booleanflag; //用于记录是否被访问BiTreeNodep; //用于记录上一次处理的结点while(!S.isEmpty() ) { //1 将所有的左孩子压栈while(S.peek() !=null) { //栈顶的元素不为空,注意:不是弹栈// 获得栈顶,BiTreeNodetemp= (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; //如果有右子树,需要重新开始 } } } } }