第8周树和二叉树（上）第6讲-本周小结.pdf

《第8周树和二叉树（上）第6讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第8周树和二叉树（上）第6讲-本周小结.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1树 度为度为m的树中所有节点的度的树中所有节点的度 m 至少有一个度为至少有一个度为m的节点的节点 度为度为2的树至少有的树至少有3个节点个节点！ 1/22 任何非空树中任何非空树中：分支数分支数 = 所有节点度之和所有节点度之和，分支数分支数 = n- -1 度为度为m的树中的树中：n = n0+ n1+ + + nm 度为度为m的树中的树中：所有节点度之和所有节点度之和 = n1+ 2n2+ + mnm 树中节点计算的基本公式 2/22 已知一棵度为已知一棵度为4的树中的树中，度为度为i（i1）的节点个数有的节点个数有i 个个，问该树中有多少个叶子节点问该树中有多少个叶子节点？ 解解：n

2、 = n0+n1+n2+ n3+n4 = n0+1+2+3+4 = n0+10，即即：n0 = n- -10 度之和度之和 = n- -1 度之和度之和 = n1+2n2+3n3+4n4 = 30 所以所以 n = 30+1 = 31，n0 = n- -10 = 31- -10 = 21。 3/22 二叉树还原为树二叉树还原为树 树转换为二叉树树转换为二叉树 过程过程 4/22 将森林将森林T转换为二叉树转换为二叉树B，若若T中有中有n个非叶子节点个非叶子节点， 则二叉树则二叉树B中中无右孩子的节点个数无右孩子的节点个数是多少是多少？ A BC DEFG B D E BT 非叶子节点非叶子节点

3、：3 无右孩子的节点无右孩子的节点：4 T中一个非叶子节点至少有一个孩子节点中一个非叶子节点至少有一个孩子节点，其中有一个最右边的孩子节点其中有一个最右边的孩子节点s 在在B中中s没有右孩子没有右孩子 T中中n个个非叶子节点非叶子节点，B中对应中对应n个没有右孩子节点个没有右孩子节点 T的根节点对应的根节点对应B的根节点的根节点，它一定是没有右孩子节点它一定是没有右孩子节点 n+1 5/22 先根遍历先根遍历 后根遍历后根遍历 层次遍历层次遍历 具有递归性具有递归性 6/22 给定一棵树给定一棵树T，将其转换成二叉树将其转换成二叉树B后后，T的的先根遍先根遍 历历对应对应B的什么遍历序列的什么

4、遍历序列？ 先根遍历先根遍历：A B T11T12T2先序遍历先序遍历：A B t11t12t2 7/22 A A T11T12 t11 t12 t2 B T2 B TB 给定一棵树给定一棵树T，将其转换成二叉树将其转换成二叉树B后后，T的的后根后根 遍历遍历对应对应B的什么遍历序列的什么遍历序列？ 后根序列后根序列： B T11T12T2 A中序序列中序序列：B t11t12t2 A A A T11T12 t11 t12 t2 B T2 B 8/22 已知一棵树已知一棵树T的先根序列和后根序列的先根序列和后根序列，可以唯一确定这棵树可以唯一确定这棵树？ T T的的先根序列先根序列B的的先序序

5、列先序序列 T的的后根序列后根序列B的的中序序列中序序列 唯一确定唯一确定B 唯一还原为唯一还原为T 9/22 双亲存储结构双亲存储结构：表示表示1：1的关系的关系 孩子链存储结构孩子链存储结构：表示表示1：n的关系的关系 孩子兄弟链存储结构孩子兄弟链存储结构：树转化为二叉树树转化为二叉树，对应二叉链对应二叉链 10/22 在一棵树在一棵树T中最常用的操作是查找某个节点的祖先节中最常用的操作是查找某个节点的祖先节 点点，采用采用哪种存储结构最合适哪种存储结构最合适？ 双亲存储结构双亲存储结构 孩子链存储结构孩子链存储结构或者或者孩子兄弟链存储结构孩子兄弟链存储结构 如最常用的操作是查找某个节点

6、的所有兄弟如最常用的操作是查找某个节点的所有兄弟，采用采用 哪种存储结构最合适哪种存储结构最合适？ 11/22 2二 叉 树 当当n=3，结果为结果为5。 第第n个个Catalan数数 12/22 有有n个节点并且高度为个节点并且高度为n的的不同形态不同形态的二叉树个数是多少的二叉树个数是多少？ 该二叉树该二叉树：有有n层层，每层一个节点每层一个节点，该节点可以作为双该节点可以作为双 亲节点的左孩子亲节点的左孩子，也可以作为右孩子也可以作为右孩子 这样的二叉树的个数这样的二叉树的个数=122=2n-1。 例如例如，当当n=3时有时有22=4个这样的二叉树个这样的二叉树。 13/22 二叉树中所

7、有节点的度二叉树中所有节点的度2 分支数分支数 = 所有节点度之和所有节点度之和，分支数分支数 = n- -1 n = n0+ n1+ n2 所有节点度之和所有节点度之和 = n1+ 2n2 n0=n2+1 14/22 节点个数为节点个数为n，树形树形可以唯一确定可以唯一确定 叶子节点个数为叶子节点个数为n0，树形不能唯一确定树形不能唯一确定 n为奇数时为奇数时，n1=0； n为偶数时为偶数时，n1=1。 n0=n2+1 高度高度h= log2(n+1) ，是是n个节点高度最小的二叉树个节点高度最小的二叉树 15/22 含有含有60个叶子节点的二叉树的个叶子节点的二叉树的最小高度最小高度是多少

8、是多少？ 在该二叉树中在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1。 当当n1=0且为完全二叉树时高度最小且为完全二叉树时高度最小。 此时高度此时高度h= log2(n+1) = log2120 =7。 16/22 高度高度h=log2n 高度为高度为h的满二叉树的满二叉树，n=2h-1，n一定为奇数一定为奇数 n0=n2+1 n1=0 17/22 已知一棵非空满二叉树中有已知一棵非空满二叉树中有31个分支节点个分支节点，则则总节点个数总节点个数是多少是多少？ n2+n1=31，而而n1=0，所以所以n2=31（双分支节点个数双分支节点个数）。）。 n0=

9、n2+1=32（二叉树性质二叉树性质），），n=n0+n1+n2=63。 18/22 3二叉树的存储结构 B A C D 1 23 6 A 1 B 2 C 3 # 4 # 5 D 6 i 2i2i+1 i/2 19/22 一棵高度为一棵高度为h的并且只有的并且只有h个节点的二叉树个节点的二叉树，采用顺序存采用顺序存 储结构存放在储结构存放在R1.n中中，则则n应该至少应该至少是是（ ）。）。 A.2hB.2h-1C.2h-1D.2h 可能是一棵有斜树可能是一棵有斜树，最后一个节点的层序编号为最后一个节点的层序编号为2h-1。C 层序编号为层序编号为2h-1 h 20/22 B A C D A b BC D 21/22 任何节点的左任何节点的左、右指针分别指向一棵二叉树右指针分别指向一棵二叉树！ 递归数据结构递归数据结构 含有含有n个节点的二叉树采用二叉链存储结构个节点的二叉树采用二叉链存储结构，其中其中 空指针域个数空指针域个数是多少是多少？ 每个节点每个节点2个指针域个指针域，共共2n个指针域个指针域 除了根节点外除了根节点外，每个节点被一个非空指针所指向每个节点被一个非空指针所指向 共有共有n-1个非空指针域个非空指针域 空指针域的个数空指针域的个数=2n-(n-1)=n+1。 22/22