第6讲 树和二叉树(二叉树的遍历)(完成)

1、数据结构与算法设计数据结构与算法设计 任课教师：任课教师：刘晋萍刘晋萍Email： 785297343 QQ: 785297343第六讲第六讲 树和二叉树树和二叉树 v树的基本概念树的基本概念 树的定义 树的基本术语v二叉树二叉树 二叉树的定义 二叉树的性质 二叉树的基本操作 二叉树的存储结构v二叉树的遍历二叉树的遍历v树与二叉树树与二叉树 树与二叉树的转换 树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历v二叉树遍历的概念二叉树遍历的概念二叉树的遍历二叉树的遍历v二叉树遍历的概念二叉树遍历的概念v二叉树遍历的方法二叉树遍历的方法二叉树的遍历二叉树的遍历v二叉树遍历的概念二叉树遍历的概

2、念v二叉树遍历的方法二叉树遍历的方法v二叉树遍历的应用二叉树遍历的应用二叉树的遍历二叉树的遍历v二叉树遍历的概念二叉树遍历的概念v二叉树遍历的方法二叉树遍历的方法v二叉树遍历的应用二叉树遍历的应用v二叉树遍历的实现算法二叉树遍历的实现算法结束结束二叉树遍历的概念二叉树遍历的概念v遍历的含义遍历的含义 访问结构中的所有元素且只访问一次v二叉树遍历的定义二叉树遍历的定义 按一定规律对二叉树中每个结点访问且仅访问一次v二叉树遍历的目的二叉树遍历的目的 在对二叉树的很多处理中，需要二叉树结点的一个线性序列 实质而言，遍历的目的就是对二叉树进行线性化处理，以得到一个结点的线性序列 对二叉树处理而言，遍历

3、的目的是为二叉树的其他运算奠定基础非线性结构非线性结构遍历遍历结点的访问序列结点的访问序列线性化线性化回去回去二叉树遍历的方法二叉树遍历的方法v有哪些方法有哪些方法 二叉树由三个基本部分组成：根结点根结点 左子树左子树 右子树右子树 遍历二叉树实质就是完成如下三项工作：v访问根结点访问根结点 Dv遍历左子树遍历左子树 Lv遍历右子树遍历右子树 R 这三项工作按顺序组合可以得到6 种遍历方案：DLR DRL LDR RDL LRD RLD 对这6 种方案加上“先左后右”的限定，则得到如下3种遍历方案：DLR 称为先（根）序遍历称为先（根）序遍历LDR 称为中（根）序遍历称为中（根）序遍历LRD

4、称为后（根）序遍历称为后（根）序遍历v遍历方法的描述遍历方法的描述根根左左子树子树右右子树子树看图看图路径路径DLR DRL LDR RDL LRD RLDDLR DRL LDR RDL LRD RLDDLR DRL LDR RDL LRD RLDDLR DRL LDR RDL LRD RLD访问根结点、遍历左子树、遍历右子树访问根结点、遍历左子树、遍历右子树访问根结点、遍历右子树、遍历左子树访问根结点、遍历右子树、遍历左子树遍历左子树、访问根结点、遍历右子树遍历左子树、访问根结点、遍历右子树遍历右子树、访问根结点、遍历左子树遍历右子树、访问根结点、遍历左子树遍历左子树、遍历右子树、访问根结点

5、遍历左子树、遍历右子树、访问根结点遍历右子树、遍历左子树、访问根结点遍历右子树、遍历左子树、访问根结点回去回去二叉树遍历的方法二叉树遍历的方法v有哪些方法有哪些方法 二叉树由三个基本部分组成：根结点根结点 左子树左子树 右子树右子树 遍历二叉树实质就是完成如下三项工作：v访问根结点访问根结点 Dv遍历左子树遍历左子树 Lv遍历右子树遍历右子树 R 这三项工作按顺序组合可以得到6 种遍历方案：DLR DRL LDR RDL LRD RLD 对这6 种方案加上“先左后右”的限定，则得到如下3种遍历方案：DLR 称为先（根）序遍历称为先（根）序遍历LDR 称为中（根）序遍历称为中（根）序遍历LRD

6、称为后（根）序遍历称为后（根）序遍历v遍历方法的描述遍历方法的描述根根左左子树子树右右子树子树看图看图三种遍历方案的遍历路径一样，只是访问根结点的时机不同三种遍历方案的遍历路径一样，只是访问根结点的时机不同二叉树遍历的方法二叉树遍历的方法v有哪些方法有哪些方法v遍历方法的描述遍历方法的描述先序遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则 (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。中序遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则 (1)中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。后序遍历二叉树 若二叉树

7、为空，则空操作； 否则 (1)后序遍历左子树； (2)后序遍历右子树; (3)访问根结点。根根左左子树子树右右子树子树看例看例先序序列先序序列中序序列中序序列后序序列后序序列（根、左、右）（根、左、右）（左、根、右）（左、根、右）（左、右、根）（左、右、根）二叉树遍历方法例二叉树遍历方法例1先序序列先序序列中序序列中序序列后序序列后序序列A B C D E F G H K待遍历的二叉树待遍历的二叉树根根右子树右子树左子树左子树ABCEFGDHK回去回去C D B A E H G K F D C B H K G F E A二叉树遍历的应用二叉树遍历的应用v输出二叉树中的所有结点输出二叉树中的所有

8、结点v输出二叉树中的叶子结点输出二叉树中的叶子结点v求二叉树的深度求二叉树的深度v对每一个应用问题：对每一个应用问题： 确定确定“访问访问” 的具体操作是什么的具体操作是什么 分析对遍历顺序的要求，确定用先序遍历、中序遍历还分析对遍历顺序的要求，确定用先序遍历、中序遍历还是后序遍历是后序遍历 给出解决问题的算法描述给出解决问题的算法描述v思考练习：思考练习： 用何种遍历实现对二叉树左右子树的交换？用何种遍历实现对二叉树左右子树的交换？ 在交换二叉树左右子树的遍历中，在交换二叉树左右子树的遍历中，“访问访问”操作是什么？操作是什么？ 写出一个实现二叉树左右子树交换的算法描述。写出一个实现二叉树左

9、右子树交换的算法描述。回去回去先序遍历二叉树先序遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则，依次做如下操作：否则，依次做如下操作：(1) (1) 访问根结点；访问根结点；(2) (2) 先序遍历左子树；先序遍历左子树；(3) (3) 先序遍历右子树。先序遍历右子树。输出二叉树中的所有结点输出二叉树中的所有结点v分析：分析： 该问题需要对二叉树进行遍历，即：对所有结点进行“访问”，且只访问一次v这里的这里的“访问访问”就是就是“结点的输出结点的输出” “访问” 顺序的确定v只要能对所有结点进行输出，没有结点输出顺序的要求，因此，只要能对所有结点进行输出，没有结点输出顺序的要求

10、，因此，按先序、中序和后序都可以按先序、中序和后序都可以v这里以先序为例这里以先序为例v算法描述（基于先序遍历）算法描述（基于先序遍历） 若二叉树为空，则空操作； 否则，依次做如下操作： (1) 输出根结点； (2) 输出左子树中的所有结点； (3) 输出右子树中的所有结点。思考：若基于中序遍历或基于后序遍历，则该问题的算法应该是怎样的？思考：若基于中序遍历或基于后序遍历，则该问题的算法应该是怎样的？看例子看例子回去回去基于中序遍历基于中序遍历基于后序遍历基于后序遍历输出二叉树中的所有结点输出二叉树中的所有结点v算法描述（基于中序遍历）算法描述（基于中序遍历） 若二叉树为空，则空操作； 否则，

11、依次做如下操作： (1)输出左子树中的所有结点； (2)输出根结点； (3) 输出右子树中的所有结点。中序遍历二叉树中序遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则，依次做如下操作：否则，依次做如下操作：(1)(1)中序遍历左子树；中序遍历左子树；(2)(2)访问根结点；访问根结点；(3)(3)中序遍历右子树。中序遍历右子树。回去回去输出二叉树中的所有结点输出二叉树中的所有结点v算法描述（基于后序遍历）算法描述（基于后序遍历） 若二叉树为空，则空操作； 否则，依次做如下操作： (1)输出左子树中的所有结点； (2)输出右子树中的所有结点； (3)输出根结点。后序遍历二叉树后序

12、遍历二叉树若二叉树为空，则空操作；若二叉树为空，则空操作；否则，依次做如下操作：否则，依次做如下操作：(1)(1)后序遍历左子树；后序遍历左子树；(2)(2)后序遍历右子树；后序遍历右子树；(3)(3)访问根结点。访问根结点。回去回去输出二叉树中的所有结点例输出二叉树中的所有结点例ABCEFGDHK待输出的二叉树待输出的二叉树基于先序遍历结点的输出序列：基于先序遍历结点的输出序列：A B C D E F G H K基于中序遍历结点的输出序列：基于中序遍历结点的输出序列：基于后序遍历结点的输出序列：基于后序遍历结点的输出序列：C D B A E H G K FD C B H K G F E A回

13、去回去输出二叉树中的叶子结点输出二叉树中的叶子结点v分析：分析： 该问题需要对二叉树中所有结点进行“访问”，且只访问一次v这里的这里的“访问访问” 是是“带判断的输出带判断的输出”，也就是：，也就是：“是叶子结点就输出是叶子结点就输出” “访问” 顺序的确定v只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以先序、中序和后序都可以v算法描述算法描述 若二叉树为空，则空操作； 否则，依次做如下操作：（1）如果根结点既没有左孩子也没有右孩子，则输出根结点（2）输出左子树中的叶子结点（3）输出右子树中的叶

14、子结点v算法描述（基于中序遍历）算法描述（基于中序遍历）v算法描述（基于后序遍历）算法描述（基于后序遍历）（基于先序遍历）（基于先序遍历）思考：该算法是基于先序的？中序的？思考：该算法是基于先序的？中序的？ 还是后序的？还是后序的？看例子看例子（1）如果根结点是叶子结点，则输出根结点。）如果根结点是叶子结点，则输出根结点。回去回去输出二叉树中的叶子结点输出二叉树中的叶子结点v分析：分析： 该问题需要对二叉树中所有结点进行“访问”，且只访问一次v这里的这里的“访问访问” 是是“判断判断+输出输出”，也就是：，也就是：“是叶子结点就输出是叶子结点就输出” 需要按某种顺序进行“访问”v只要能对所有叶

15、子结点进行输出，没有结点输出顺序的要求，因此，按只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以先序、中序和后序都可以v算法描述算法描述 若二叉树为空，则空操作； 否则，依次做如下操作：（1）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（2）输出左子树中的叶子结点（3）输出右子树中的叶子结点v算法描述（基于中序遍历）算法描述（基于中序遍历）v算法描述（基于后序遍历）算法描述（基于后序遍历）（基于先序遍历）（基于先序遍历）看例子看例子输出二叉树中的叶子结点输出二叉树中的叶子结点v分析：分析： 该问题需要对二叉树中所有结点进行“访问”，且只访问一次v

16、这里的这里的“访问访问” 是是“判断判断+输出输出”，也就是：，也就是：“是叶子结点就输出是叶子结点就输出” 需要按某种顺序进行“访问”v只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以先序、中序和后序都可以v算法描述算法描述v算法描述（基于中序遍历）算法描述（基于中序遍历） 若二叉树为空，则空操作； 否则，依次做如下操作：（1）输出左子树中的叶子结点（2）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（3）输出右子树中的叶子结点v算法描述（基于后序遍历）算法描述（基于后序遍历）（基于先

17、序遍历）（基于先序遍历）看例子看例子输出二叉树中的叶子结点输出二叉树中的叶子结点v分析：分析： 该问题需要对二叉树中所有结点进行“访问”，且只访问一次v这里的这里的“访问访问” 是是“判断判断+输出输出”，也就是：，也就是：“是叶子结点就输出是叶子结点就输出” 需要按某种顺序进行“访问”v只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按只要能对所有叶子结点进行输出，没有结点输出顺序的要求，因此，按先序、中序和后序都可以先序、中序和后序都可以v算法描述算法描述v算法描述（基于中序遍历）算法描述（基于中序遍历）v算法描述（基于后序遍历）算法描述（基于后序遍历） 若二叉树为空，则空操作

18、； 否则，依次做如下操作：（1）输出左子树中的叶子结点（2）输出右子树中的叶子结点（3）如果当前二叉树的根既没有左孩子也没有右孩子，则输出根结点（基于先序遍历）（基于先序遍历）看例子看例子输出二叉树中的叶子结点例输出二叉树中的叶子结点例ABCEFGDHK待输出的二叉树待输出的二叉树基于先序遍历叶子结点的输出序列：基于先序遍历叶子结点的输出序列： D H K D H K D H K基于后序遍历叶子结点的输出序列：基于后序遍历叶子结点的输出序列：基于中序遍历叶子结点的输出序列：基于中序遍历叶子结点的输出序列：思考：输出二叉树叶子结点的算法，不论基于先序、中序和后序，叶子结点的思考：输出二叉树叶子结

19、点的算法，不论基于先序、中序和后序，叶子结点的 输出顺序都一样吗？为什么？输出顺序都一样吗？为什么？回去回去求二叉树的深度求二叉树的深度v二叉树深度的定义：二叉树深度的定义： 结点的最大层次数 MAX左子树的深度，右子树的深度+1v求二叉树深度的算法描述：求二叉树深度的算法描述： 若二叉树为空，则返回0； 否则，依次做如下操作： 求左子树的深度lh 求右子树的深度rh 返回maxlh，rh+1v思考：思考： 基于什么遍历顺序v后序遍历后序遍历 这里，对结点访问的操作是什么v求以该结点为根的二叉树的深度求以该结点为根的二叉树的深度根根左左子树子树右右子树子树lhrh二叉树的深度？二叉树的深度？二

20、叉树的深度二叉树的深度= MAX lh= MAX lh，rhrh +1 +1看例子看例子回去回去思考：思考：根据根据”二叉树的深度二叉树的深度= MAX lh= MAX lh，rhrh +1“ +1“这这个定义，求二叉树深度能否按先序或中序进行？个定义，求二叉树深度能否按先序或中序进行？为什么？为什么？求二叉树的深度例求二叉树的深度例v求二叉树深度的算法描述：求二叉树深度的算法描述： 若二叉树为空，则返回0； 否则，依次做如下操作： 求左子树的深度lh 求右子树的深度rh 返回maxlh，rh+1ABCEFGDHK0120003000000112345回去回去思考与练习思考与练习v交换二叉树的

21、左右子树交换二叉树的左右子树 用何种遍历实现对二叉树左右子树的交换？ 在交换二叉树左右子树的遍历中，”访问“操作是什么？ 写出一个实现二叉树左右子树交换的算法描述v根据：根据：二叉树的深度= MAX lh，rh +1 这个定义，求二叉树深度能否按先序或中序进行？这个定义，求二叉树深度能否按先序或中序进行？为什么？为什么？v输出二叉树叶子结点的算法，不论基于先序、中输出二叉树叶子结点的算法，不论基于先序、中序和后序，叶子结点的输出顺序都一样吗？为什序和后序，叶子结点的输出顺序都一样吗？为什么？么？二叉树遍历的实现算法二叉树遍历的实现算法v先序遍历的递归实现算法先序遍历的递归实现算法v中序遍历的递

22、归实现算法中序遍历的递归实现算法v后序遍历的递归实现算法后序遍历的递归实现算法v解决应用问题的实现算法解决应用问题的实现算法返回返回P7先序遍历的递归实现算法先序遍历的递归实现算法先序遍历以先序遍历以root为根的二叉树为根的二叉树void PreOrder ( BiTree root ) if (root!=NULL) Visit(root -data); /*访问根结点访问根结点*/ PreOrder(root -lchild); /*先序遍历左子树先序遍历左子树*/ PreOrder(root -rchild); /*先序遍历右子树先序遍历右子树*/ 返回返回P26中序遍历的递归实现算法

23、中序遍历的递归实现算法中序遍历以中序遍历以root为根的二叉树为根的二叉树void InOrder ( BiTree root ) if (root!=NULL) InOrder(root -lchild); /*中序遍历左子树中序遍历左子树*/ Visit(root -data); /*访问根结点访问根结点*/ InOrder(root -rchild); /*中序遍历右子树中序遍历右子树*/ 返回返回P26后序遍历的递归实现算法后序遍历的递归实现算法后序遍历以后序遍历以root为根的二叉树为根的二叉树void PostOrder ( BiTree root ) if(root!=NULL)

24、 PostOrder(root -lchild); /*后序遍历左子树后序遍历左子树*/ PostOrder(root -rchild); /*后序遍历右子树后序遍历右子树* Visit(root -data); /*访问根结点访问根结点*/ 返回返回P26解决应用问题的实现算法解决应用问题的实现算法v输出二叉树中结点的实现算法输出二叉树中结点的实现算法v输出二叉树中叶子结点的实现算法输出二叉树中叶子结点的实现算法v求二叉树深度的实现算法求二叉树深度的实现算法v二叉树的创建算法二叉树的创建算法v算法阅读算法阅读返回返回P26输出二叉树中结点的实现算法输出二叉树中结点的实现算法输出以输出以roo

25、t为根的二叉树中的结点。为根的二叉树中的结点。基于先序遍历的实现算法基于先序遍历的实现算法void OutBiTree ( BiTree root ) if (root!=NULL) printf (root -data); /* 输出根结点输出根结点 */ OutBiTree (root -lchild); /* 输出左子树中的结点输出左子树中的结点 */ OutBiTree (root -rchild); /* 输出右子树输出右子树 中的结点中的结点*/ 返回返回P30输出二叉树中叶子结点的实现算法输出二叉树中叶子结点的实现算法输出以输出以root为根的二叉树中叶子结点为根的二叉树中叶子结

26、点 基于先序遍历的实现算法基于先序遍历的实现算法void OutLeaf ( BiTree root ) if (root!=NULL) if (root -lchild=NULL & root -rchild=NULL) printf (root -data); /* 输出叶子结点输出叶子结点 */ OutLeaf (root -lchild); /* 输出左子树输出左子树 中的叶子结点中的叶子结点*/ OutLeaf (root -rchild); /* 输出右子树中的叶子结点输出右子树中的叶子结点 */ 返回返回P30求二叉树深度的实现算法求二叉树深度的实现算法求以求以root为

27、根的二叉树的深度为根的二叉树的深度int BiTreeDepth ( BiTree root ) if(root!=NULL) hl=BiTreeDepth (root -lchild); /* 求左子树的深度求左子树的深度 */ hr=BiTreeDepth (root -rchild); /* 求右子树的深度求右子树的深度 */ max=hlhr?hl:hr; /* 得到左、右子树深度较大者得到左、右子树深度较大者*/ return(max+1); /* 返回树的深度返回树的深度 */ else return(0); /* 如果是空树，则返回如果是空树，则返回0 */返回返回P30关于二叉

28、树的创建关于二叉树的创建v给定一棵二叉树，可以得到它的遍历序列给定一棵二叉树，可以得到它的遍历序列v反之，给定一棵二叉树的遍历序列，也可以画出反之，给定一棵二叉树的遍历序列，也可以画出该二叉树该二叉树 能画出就意味着能创建二叉树能画出就意味着能创建二叉树v已知二叉树的已知二叉树的“扩展的遍历序列，画出该二叉树扩展的遍历序列，画出该二叉树 在二叉树的遍历序列中，用特定的元素表示空子树，就在二叉树的遍历序列中，用特定的元素表示空子树，就得到相应的扩展遍历序列得到相应的扩展遍历序列 例如，下图例如，下图 中二叉树的中二叉树的“扩展先序遍历序列扩展先序遍历序列”为：为：AB.DF.G.C.E.H.（这

29、里以（这里以.表示空子树）表示空子树）继续继续关于二叉树的创建关于二叉树的创建v画出扩展先序序列为：画出扩展先序序列为：ACF.GK.HB.FE 的二叉树的二叉树v将此过程作为创建二叉树的将此过程作为创建二叉树的过程过程,即即: 创建二叉链表的过程创建二叉链表的过程v则对应此过程的实现算法见：则对应此过程的实现算法见：“利用利用扩展先序遍历序列扩展先序遍历序列创创建二叉链表的算法建二叉链表的算法”ACFBFGEKH继续继续利用利用“扩展先序遍历序列扩展先序遍历序列” 创建二叉链表的算创建二叉链表的算法法void CreateBiTree ( BiTree &root ) ch=getc

30、har(); if(ch=.) root =NULL; else root =(BiTree)malloc(sizeof(BiTNode); root -data=ch; CreateBiTree( root -lchild ); CreateBiTree(root -rchild); 继续继续ABFECFGKHrootACF.GK.HB.FE关于二叉树的创建关于二叉树的创建v已知某二叉树的先序序列和中序序列如下：已知某二叉树的先序序列和中序序列如下： 先序序列：先序序列：A B D G C E H F 中序序列：中序序列：B G D A E H C F 画出该二叉树，并写出其后序序列。画出该

31、二叉树，并写出其后序序列。ABDGCEFH后序序列：后序序列：G D B H E F C A由先序序列确定根是由先序序列确定根是A A由中序序列确定：由中序序列确定：（1 1）A A有左、右子树；有左、右子树；（2 2）左子树中的结点有）左子树中的结点有B D GB D G；右子树中的结点有；右子树中的结点有 C E F HC E F H再由先序序列确定左子树的结点再由先序序列确定左子树的结点B D GB D G中中B B是根是根由中序序列确定由中序序列确定B B没有左子树，但有右子树，其中右没有左子树，但有右子树，其中右子树中的结点有子树中的结点有D GD G依此类推，直到依此类推，直到A

32、A的左子树的结构确定。的左子树的结构确定。用同样的方法分析右子树的结构。用同样的方法分析右子树的结构。继续继续关于二叉树的创建关于二叉树的创建v已知某二叉树的中序序列和后序序列如下：已知某二叉树的中序序列和后序序列如下： 中序序列：中序序列：E G H C F A DE G H C F A D 后序序列：后序序列：E G C A D F H E G C A D F H 画出该二叉树，并写出其先序序列。画出该二叉树，并写出其先序序列。由后序序列确定根是由后序序列确定根是H H由中序序列确定：由中序序列确定：（1 1）H H有左、右子树；有左、右子树；（2 2）左子树中的结点有）左子树中的结点有G EG E；右子树中的结点有；右子树中的结点有 F D C AF D C A再由后序序列确定左子树的结点再由后序序列确定左子树的结点G E G E 中中G G是根，由中序序列是根，由中序序列确定确定G G有左子树，但没有右子树，其中左子树中的结点有有左子树，但没有右子树，其中左子树中的结点有E E。用同样的方法分析右子树的结构：用同样的方法分析右子树的结构：根：根：F F 且且F F有左子树，也有右子树。有左子树，也有右子树。左子树有