第6章树和二叉树数据结构.ppt
185页
第5章 树 2024/8/252第6章 树w6.1 树的概念及操作树的概念及操作w6.2 二叉树二叉树 n 6.2.1 二叉树的概念及操作二叉树的概念及操作 n 6.2.2 二叉树的性质二叉树的性质n6.2.3 二叉树的存储结构二叉树的存储结构w6.3 二叉树的遍历二叉树的遍历w6.4 线索二叉树线索二叉树w6.5 树和森林树和森林 n6.5.1 树的存储结构树的存储结构 n6.5.2 森林、树、二叉树的相互转换森林、树、二叉树的相互转换 n6.5.3 树和森林的遍历树和森林的遍历w6.6 哈夫曼树及其应用哈夫曼树及其应用 n 6.6.1 最优二叉树最优二叉树(哈夫曼树哈夫曼树) n 6.6.2 哈夫曼编码哈夫曼编码 w*6.7算法设计举例算法设计举例 2024/8/253主要内容 w知识点知识点n树和二叉树定义树和二叉树定义n二叉树的性质，存储结构二叉树的性质，存储结构n二叉树的遍历及遍历算法的应用二叉树的遍历及遍历算法的应用n** ** 线索二叉树线索二叉树n二叉树和树及森林的关系二叉树和树及森林的关系nHuffmanHuffman树与树与HuffmanHuffman编码编码w重点难点重点难点n二叉树的性质及应用二叉树的性质及应用n二叉树的遍历算法及应用二叉树的遍历算法及应用n** 线索二叉树的算法线索二叉树的算法nHuffmanHuffman树的构造方法树的构造方法n树的算法树的算法 2024/8/254树例与特征n社会的组织结构社会的组织结构n家族的族谱家族的族谱n计算机中的目录组织计算机中的目录组织描述层次结构，是一种一对多的逻辑关系描述层次结构，是一种一对多的逻辑关系 2024/8/255树的定义 w树树(Tree)(Tree)是n(n>=0)个结点的有限集。
n=0时称为空树w（注：有人定义树不能为空）（注：有人定义树不能为空）n有且仅有一个称为根的结点（Root）；nn>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树(SubTree)FGIJABCEDH 2024/8/256树的定义 w树树的的递递归归定定义义的的各各子子树树T1,T2,…,Tm的相对次序是重要的，即树是有序的 2024/8/257树定义(图示)T1T2T3 2024/8/258树的抽象数据类型的树的抽象数据类型的定义wADT Tree{w数据对象数据对象 D：：D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合 w数据关系数据关系 R：若：若D为空集，则称为空树；为空集，则称为空树；w 若若D仅含有一个数据元素，则仅含有一个数据元素，则R为空集，否则为空集，否则R={H}，，H是是如下定义的二元关系：如下定义的二元关系：w（（1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱；w（（2）若）若D-{root},则存在则存在D-{root}的一个划分的一个划分D1，，D2,…,Dm（（m>0））,对任意对任意j k(1 j,k m)有有Dj Dk= ,且对任意且对任意的的i(1 i m ),存在唯一数据元素存在唯一数据元素xi Di ,
的子树w （转下页）（转下页） 2024/8/259 Tree (); ~Tree (); BuildRoot (const T& value); //建立树的根结点 position FirstChild(position p); //返回 p 第一个子女地址, 无子女返回 0 position NextSibling(position p); //返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); //返回 p 双亲结点地址, 若 p 为根返回 0 T getData(position p); //返回结点 p 中存放的值 bool InsertChild(position p, T& value); //在结点 p 下插入值为 value 的新子女, 若插 //入失败, 函数返回false, 否则返回true树的抽象数据类型(续) bool DeleteChild (position p, int i); //删除结点 p 的第 i 个子女及其全部子孙结 //点, 若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); //删除以 t 为根结点的子树 bool IsEmpty (); //判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p)); //遍历以 p 为根的子树}ADT Tree2024/8/2510树的抽象数据类型(续) 2024/8/2511树的其它表示方式凹入表示凹入表示嵌套集合嵌套集合广义表广义表A(B(E,F),C,D(G(J),H,I))AE FBIJGHCDAB E FCD G J H IFGIJABCEDH 2024/8/2512w结点结点：：一个数据元素一个数据元素及及若干指向其子树的分支；若干指向其子树的分支；w结点的度结点的度：结点拥有的子树的数目。
结点拥有的子树的数目w树的度树的度：树内各结点的度的最大值；：树内各结点的度的最大值；w叶子叶子（终端结点）：度为（终端结点）：度为0的结点；的结点；w分分支支结结点点（（非非终终端端结结点点））：：度度不不为为0的的结结点点；；除除根根结点外，也称内部结点；结点外，也称内部结点；w孩孩子子，，双双亲亲，，兄兄弟弟，，堂堂兄兄：：结结点点的的子子树树的的根根称称为为该该结结点点的的孩孩子子；；该该结结点点称称为为孩孩子子的的双双亲亲；；同同一一个个双双亲亲的的孩孩子子之之间间互互称称兄兄弟弟；；其其父父结结点点是是兄兄弟弟的的结结点点互互称称堂兄树的概念 2024/8/2513概念w祖先祖先：从根结点到该结点所经分支上的所有结点从根结点到该结点所经分支上的所有结点w子子孙孙：：以以某某结结点点为为根根的的子子树树中中的的任任一一结结点点都都称称为为该该结结点的子孙点的子孙w层次层次：结点在树结构中的层（：结点在树结构中的层（一般定义根为一般定义根为1层）w深度深度：树中结点的最大层次称为树的深度树中结点的最大层次称为树的深度w有有序序树树：：结结点点的的子子树树在在树树中中的的位位置置固固定定，，不不能能互互换换，，称有序树。
称有序树w无序树无序树：子树在树中的位置可以互换子树在树中的位置可以互换w树的度树的度：结点度的最大值：结点度的最大值w森林森林：：m(m≥0)棵互不相交的树的集合棵互不相交的树的集合 2024/8/2514概念示例w结点结点w结点的度结点的度(Degree)w叶子（叶子（Leaf)或终端结点或终端结点w分支结点或非终端结点分支结点或非终端结点w树的度树的度w层次层次(Level)w树的深度树的深度(Depth)w孩子（孩子（child)w双亲（双亲（Parent)w兄弟兄弟(Sibling)w祖先祖先w子孙子孙树的示例树的示例 2024/8/2515自测题 1n(n>0)个结点的树的高度个结点的树的高度: 最低是多少？最低是多少？ 最高是多少？最高是多少？ 2024/8/2516二叉树的概念 w二叉树二叉树(Binary Tree)(Binary Tree)：：或者是一棵空树，或者是一棵空树，或者是一棵由一个根结点和两棵互不相交或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树树和右子树同样也都是二叉树 w特征特征：：n每个结点最多只有两棵子树每个结点最多只有两棵子树n子树有左右之分，其次序不能任意颠倒，只有子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。
一棵子树时也必须分清是左、右子树 2024/8/2517二叉树的抽象数据类型ADT BinaryTree { 数据对象数据对象D：：D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合 数据关系数据关系R：若：若D= ，则，则R= ，称二叉树为空二叉树；，称二叉树为空二叉树； 若若D，则，则R={H}，，H是如下二元关系：是如下二元关系： （（1））在在D中中存存在在唯唯一一的的称称为为根根的的数数据据元元素素root，，它它在在关关系系H下下无无前驱；前驱； （（2）若）若D-{root},则存在则存在D-{root}={D1,Dr},且且 D1 Dr；； （（3））若若D1，，则则D1中中存存在在唯唯一一的的元元素素x1,
是一棵符合本定义的二叉树，称为根的右子树基本操作如下：基本操作如下： 2024/8/2518二叉树的抽象数据类型(续)BinTreeNode
证明：设n1为T中度为1的结点数，则总结点数：n = n0 + n1 + n2 (1) 另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则n=B+1 =n1 + 2 * n2+1 (2) 由(1)和(2)有： n1 + 2 * n2 ＋ 1 = n0 + n1 + n2 故 n0 = n2 + 1; 2024/8/2523满二叉树w满二叉树满二叉树：深度为深度为k且有且有2k-1个结点的二叉树个结点的二叉树满二叉树满二叉树w考虑到有序性，考虑到有序性，任一结点在树中任一结点在树中都有确切的位置，都有确切的位置，因此可以对满二因此可以对满二叉树进行编号叉树进行编号编号方式为：从编号方式为：从上到下，从左到上到下，从左到右 2024/8/2524完全二叉树w完全二叉树：完全二叉树：深度为深度为k，有，有n个结点的二叉个结点的二叉树，当且仅当树，当且仅当其每一个结点其每一个结点都与深度为都与深度为k的的满二叉树编号满二叉树编号从从1到到n的结点的结点一一对应时，一一对应时，称为称为完全二叉完全二叉树树。
完全二叉树完全二叉树 2024/8/2525完全二叉树的树形特征w特征：特征：n叶子结点只可能在层次最大的两层上叶子结点只可能在层次最大的两层上出现n任一结点，若其左分支下的子孙的最任一结点，若其左分支下的子孙的最大层次为大层次为l，则其右分支下的最大层次，则其右分支下的最大层次为为l或或l-1，，即若结点无左子女即若结点无左子女，，决不应决不应有右子女有右子女 2024/8/2526完全二叉树的特性（1）1.1.具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度: : k = k = 证明：假设证明：假设n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，则，则n的值的值应大于深度为应大于深度为k-1的满二叉树的结点数的满二叉树的结点数2k-1-1，小于等于，小于等于深度为深度为k的满二叉树的结点数的满二叉树的结点数2k-1，即，即 2k-1-1
（（b））如如果果2i>n,则则结结点点i无无左左孩孩子子，，i为为叶叶子子结点结点,否则其左孩子是结点否则其左孩子是结点2i （（c）如果）如果2i+1>n，则结点，则结点i无右孩子，否无右孩子，否则其右孩子是结点则其右孩子是结点2i+1 2024/8/2528完全二叉树的特性（2）的示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j层j+1层 2024/8/2529完全二叉树的特性（2）的示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1) i/2i/2 2024/8/2530自测题 2n(n>0)个结点的二叉树的高度个结点的二叉树的高度: 最低是多少？最低是多少？ 最高是多少？最高是多少？ 2024/8/2531自测题 3 有关二叉树下列说法正确的是（有关二叉树下列说法正确的是（ ））A．二叉树的度为．二叉树的度为2 B．一棵二叉树的度可以小于．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为．二叉树中任何一个结点的度都为2【【南京理工大学南京理工大学 2000 一一.11 （（1.5分）分）】】 2024/8/2532自测题自测题 w 5. 已知一棵完全二叉树的第已知一棵完全二叉树的第6层（设根是第层（设根是第1层）层）有有8个叶结点，则该完全二叉树的结点个数最多个叶结点，则该完全二叉树的结点个数最多是是wA. 39 wB. 52 wC. 111 wD. 119w【2009年全国硕士研究生入学计算机学科专业基础综合试题年全国硕士研究生入学计算机学科专业基础综合试题】 2024/8/2533完全二叉树性质的推论wn个结点的完全二叉树个结点的完全二叉树中：中：n 度为度为1的结点数为的结点数为(n+1)%2; n 度为度为0的结点数为的结点数为 (n+1)/2 ；；n 度为度为2的结点数为的结点数为 (n+1)/2 -1；；n 编号最大的分支结点是编号最大的分支结点是 n/2 ；；n 编号最小的叶子结点是编号最小的叶子结点是 n/2 +1。
wn个结点的二叉树：个结点的二叉树：n高最多为高最多为n；；n最低为最低为 （完全二叉树）完全二叉树） 2024/8/2534树的叶子数与其它结点数的关系树的叶子数与其它结点数的关系w设设度为度为m的树中度为的树中度为0,1,2,…,m的结点数分的结点数分别为别为n0, n1, n2,…, nm，结点总数为，结点总数为n，分枝，分枝数为数为B，则下面二式成立，则下面二式成立wn= n0+ n1+n2+…+nm (1)wn=B+1= n1+2n2 +…+mnm (2)w由由(1)和和(2)得叶子结点数得叶子结点数n0=1+ 2024/8/2535二叉树的存储储结构w顺序存储结构w链式存储结构 2024/8/2536二叉树的顺序存储结构n整个二叉树可以按照从上到下，从左到整个二叉树可以按照从上到下，从左到右的顺序编号；右的顺序编号；n对于满对于满/完全二叉树，可以从根结点开始完全二叉树，可以从根结点开始按序号存放；按序号存放；n对于一般的二叉树，可以参照满二叉树对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点为的编号方法进行编号，位置空的结点为“虚结点虚结点”。
2024/8/2537顺序存储结构举例123456789101 18 89 910104 45 52 26 67 73 3完全二叉树完全二叉树 2024/8/2538顺序存储结构举例1234578101 18 810104 45 52 27 73 3一般二叉树一般二叉树 2024/8/2539顺序存储结构举例ABC非完全二叉树非完全二叉树XABCØØØØA Ø B Ø Ø Ø C 2024/8/2540二叉树的链式存储结构w二叉链表二叉链表w三叉链表三叉链表w（线索链表）（线索链表）lchilddatarchilddatalchild rchildlchilddatarchildparentdatalchild rchildparent 2024/8/2541链式存储结构示例ACFEDBADBCEF∧∧∧∧∧∧∧∧∧∧∧∧∧∧A∧∧∧∧∧BCDEF∧∧∧∧∧∧∧二叉链表二叉链表三叉链表三叉链表 42二叉树的类定义二叉树的类定义//构造函数 { lefttemplate
个结点 wA.247 wB.248 wC.249; wD.250; wE.251w【【中国科学技术大学中国科学技术大学1995十四十四.3(2分分)】】 2024/8/2550自测题自测题 5w已知一棵完全二叉树中共有已知一棵完全二叉树中共有626个结点，个结点，叶子结点的个数应为叶子结点的个数应为( )wA. 311 wB. 312 wC. 313 wD. 314 wE. 其它其它 w【【上海交通大学上海交通大学2005四四.6(2分分)】】 2024/8/2551自测题自测题 6w一个具有一个具有1025个结点的二叉树的高个结点的二叉树的高h为（为（ ））wA．．11 wB．．10 wC．．11至至1025之间之间 wD．．10至至1024之间之间w【【南京理工大学南京理工大学1999 一一.19(2分分)】】 2024/8/2552自测题自测题 7w 一棵树高为一棵树高为K的完全二叉树至少有（的完全二叉树至少有（ ）个结）个结点点wA. 2k –1 wB. 2k-1 –1 wC. 2k-1 wD. 2kw【【南京理工大学南京理工大学 1998 一一.3 （（2分）分）】】 2024/8/2553自测题自测题 8w已知一棵度为已知一棵度为3的树有的树有2个度为个度为1的结点，的结点，3个度个度为为2的结点，的结点，4个度为个度为3的结点，则该树有的结点，则该树有______个叶子结点。
个叶子结点w【【厦门大学厦门大学 2000 六六.2 （（16%/3分）分）】】 2024/8/2554二叉树的遍历二叉树的遍历 二叉树的遍历的定义二叉树的遍历的定义：： 按某种规律，访问二叉树的结点，使每个结点按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次访问的含义包括查询、打印、被访问一次且仅一次访问的含义包括查询、打印、计算、修改等对结点的操作计算、修改等对结点的操作 遍历的过程，实际上是按某种规律，将一个非遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结点性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系这种遍历中有唯一前驱和后继关系 一棵二叉树的遍历序列（在某种遍历方式下）一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序列是唯一的，但一般说，二叉树不能由某一遍历序列唯一确定唯一确定 2024/8/2555二叉树的遍历二叉树的遍历 w前序遍历二叉树前序遍历二叉树w中序遍历二叉树中序遍历二叉树w后序遍历二叉树后序遍历二叉树访问根结点；访问根结点；前序遍历左子树；前序遍历左子树；前序遍历右子树前序遍历右子树； 中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树；中序遍历右子树； 后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树； 访问根结点；访问根结点；D DL LR RLDRLDR、、LRDLRD、、DLRDLRRDLRDL、、RLDRLD、、DRLDRL若二叉树为空，则空操作，否则：若二叉树为空，则空操作，否则：层次遍历二叉树层次遍历二叉树 2024/8/2556ADBCD L RAD L RD L R>B>>D>>CD L R前序遍历序列：前序遍历序列：A B D CA B D C前序遍历 2024/8/2557ADBCL D RBL D RL D R>A>>D>>CL D R中序遍历序列：中序遍历序列：B D A CB D A C中序遍历 2024/8/2558ADBC L R DL R DL R D>A>>D>>CL R D后序遍历序列：后序遍历序列： D B C AD B C A后序遍历B 2024/8/2559ADBC层次遍历序列：层次遍历序列： A B C DA B C D 层次遍历 2024/8/2560遍历图例ACFEDB中序序列为：中序序列为：DBEACFDBEACF 前序序列为：前序序列为：ABDECFABDECF 后序序列为：后序序列为：DEBFCADEBFCA 2024/8/2561自测题自测题3. 给定二叉树如下图所示。
设给定二叉树如下图所示设N代表二叉树的根，代表二叉树的根，L代表代表根结点的左子树，根结点的左子树，R代表根结点的右子树若遍历后的代表根结点的右子树若遍历后的结点序列为结点序列为3,1,7,5,6,2,4，则其遍历方式是，则其遍历方式是wA. LRN B. NRL C. RLN D. RNLw【2009年全国硕士研究生入学计算机学科专业基础综合试题年全国硕士研究生入学计算机学科专业基础综合试题】 1234567 2024/8/2562中序遍历二叉树的递归算法template
以递归方式建立二叉树w输入结点值的顺序必须对应二叉树结点前序输入结点值的顺序必须对应二叉树结点前序遍历的顺序并约定以输入序列中不可能出遍历的顺序并约定以输入序列中不可能出现的值作为空结点的值以结束递归现的值作为空结点的值以结束递归, 此值在此值在RefValue中例如用中例如用“@”或用或用“-1”表示字表示字符序列或正整数序列空结点符序列或正整数序列空结点 70如图所示的二叉树的前序遍历顺序为如图所示的二叉树的前序遍历顺序为A B C @ @ D E @ G @ @ F @ @ @ABCDEGF@@@@@@@@ 71 template
2024/8/2574非递归中序遍历栈S的变化－cba×t→→”－－”－－t→→”×”×t→→”a”－×at→→”NULL”a出栈出栈－×t→→”NULL”×出栈出栈－－bt→→”b”－t→→”NULL”b出栈出栈t→→”NULL”－－出栈出栈t→→”c”ct→→”NULL”c出栈出栈t→→”NULL”栈空栈空结束结束 2024/8/2575中序非递归遍历 算法template
表示从右子树退回要访问根结点 ptr tag{L,R} 利用栈的后序遍历非递归算法利用栈的后序遍历非递归算法 77aLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaRabcde 78后序遍历的非递归算法后序遍历的非递归算法 template
唯一确定一棵二叉树w 已知二叉树的已知二叉树的后序序列和中序序列后序序列和中序序列，可以，可以唯一确定一棵二叉树；唯一确定一棵二叉树；w 已知二叉树的已知二叉树的先序序列和后序序列先序序列和后序序列，，不不能能唯一确定一棵二叉树；唯一确定一棵二叉树；w 已知二叉树的已知二叉树的层次序列和中序序列层次序列和中序序列，可以，可以唯一确定一棵二叉树唯一确定一棵二叉树 2024/8/2581自测题 9 构造二叉树w已知二叉树的已知二叉树的w 先序序列先序序列ABDFCEHGw 中序序列中序序列DBFAHECGw请构造该二叉树请构造该二叉树 2024/8/2582自测题 10 构造二叉树w w已知二叉树的已知二叉树的w 后序序列后序序列DMFBHELGCAw 中序序列中序序列DBMFAHECGLw请构造该二叉树请构造该二叉树 2024/8/2583自测题自测题 11w一棵二叉树的先序、中序和后序序列如下，其一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树中有部分未标出，试构造出该二叉树w先序序列为：先序序列为：_ _ C D E _ G H I _ Kw中序序列为：中序序列为：C B _ _ F A _ J K I Gw后序序列为：后序序列为： _ E F D B _ J I H _ A w【【电子科技大学电子科技大学2001三三.1(5分分)】】w【【厦门大学厦门大学2002七七.1(6分分)】】 2024/8/2584自测题 12 构造二叉树试找出满足下列条件的二叉树试找出满足下列条件的二叉树1 1）先序序列与后序序列相同）先序序列与后序序列相同 2 2）中序序列与后序序列相同）中序序列与后序序列相同3 3）先序序列与中序序列相同）先序序列与中序序列相同 4 4）中序序列与层次遍历序列相同）中序序列与层次遍历序列相同 2024/8/2585自测题自测题 13w一棵二叉树的前序遍历序列为一棵二叉树的前序遍历序列为ABCDEFG，它，它的中序遍历序列可能是（的中序遍历序列可能是（ ）。
wA．．CABDEFG wB．．ABCDEFG wC．．DACEFBG wD．．ADCFEGB w w 【【北京工业大学北京工业大学2001一一.2(2分分)】】 2024/8/2586自测题自测题 14w一棵非空的二叉树的先序序列和后序序列正好一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足相反，则该二叉树一定满足( )wA. 其中任意一个结点均无左孩子其中任意一个结点均无左孩子 wB. 其中任意一个结点均无右孩子其中任意一个结点均无右孩子wC. 其中只有一个叶子结点其中只有一个叶子结点 wD. 其中度为其中度为2的结点最多为一个的结点最多为一个w【【中南大学中南大学2005一一.7(2分分)】】 2024/8/2587自测题自测题 15w某二叉树的先序序列和后序序列正好相反，则某二叉树的先序序列和后序序列正好相反，则该二叉树一定是该二叉树一定是( )的二叉树的二叉树wA．空或只有一个结点．空或只有一个结点 wB. 高度等于其结点数高度等于其结点数wC．任一结点无左孩子．任一结点无左孩子 wD. 任一结点无右孩子任一结点无右孩子w【【东华大学东华大学2003二二.1(1分分)】】 2024/8/2588表达式的二叉树表示用二叉树可以表示表达式用二叉树可以表示表达式
的算法wint BinTreeDepth(BiTree T)w {if(T==NULL) return 0;w else{l=BinTreeDepth(T->lchild);w r=BinTreeDepth(T->rchild);w return(l>r? l+1 :r+1);w }w } 2024/8/2590算法举例6.2 求二叉树的叶子数求二叉树的叶子数(1)w以二叉链表作为存储结构，试编写求二叉树中叶子数以二叉链表作为存储结构，试编写求二叉树中叶子数的算法wint LeafCount(BiTree T) w{if(!T) return 0; //空树没有叶子空树没有叶子 w else w if(!T->lchild && !T->rchild) return 1; //叶子结点叶子结点 w else return LeafCount(T->lchild)+w LeafCount(T->rchild); w //左子树叶子数加上右子树叶子数左子树叶子数加上右子树叶子数 w} 2024/8/2591算法举例6.2 求二叉树的叶子数求二叉树的叶子数(2)w以二叉链表作为存储结构，试编写求二叉树中以二叉链表作为存储结构，试编写求二叉树中 叶子数的算法。
叶子数的算法wint num=0;wvoid LeafCount(BiTree T) w{if(T) w {LeafCount(T->lchild) ; //中序遍历左子树中序遍历左子树w if(!T->lchild && !T->rchild) num++; //访问根结点访问根结点w LeafCount(T->rchild) ; //中序遍历右子树中序遍历右子树w }w} 2024/8/2592算法举例6.3 交换二叉树的子树交换二叉树的子树w以二叉链表作为存储结构，设计算法交换二以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树叉树中所有结点的左、右子树wvoid change(BiTree T)w {if(T!=NULL)w { change(T->lchild);w change(T->rchild);w t=T->lchild;w T->lchild=T->rchild;w T->rchild=t;w}w } 2024/8/2593算法举例6.4 以二叉链表作为存储以二叉链表作为存储 结构，设计算法拷贝二叉树。
结构，设计算法拷贝二叉树wBiTree copy(BiTree T)w {BiTree T1;w if(T==null) T1=null;w elsew {T1=(BiTree)malloc(sizeof(BiNode)); //申请结点申请结点w T1->data=T->data; w T1->lchild=copy(T->lchild);w T1->rchild=copy(T->rchild);w}w return T1;w } 2024/8/2594算法举例6.5 由顺序存储的由顺序存储的n个结点个结点的完全二叉树建立二叉链表存储的二叉树的完全二叉树建立二叉链表存储的二叉树wBiTree creat(ElemType A[ ],int i)w {BiTree T;w if(i>n) T=null;w elsew {T=(BiTree)malloc(sizeof(BiNode)); //申请结点申请结点w T->data=A[i]; w T->lchild=creat(A,2*i);w T->rchild=creat(A,2*i+1);w}w return T;w } //初始调用：初始调用：p=creat(A,1); 2024/8/2595wvoid PreInCreat(BiTree root,ElemType pre[],in[],int l1,h1,l2,h2)w//根据二叉树前序序列根据二叉树前序序列pre和中序序列和中序序列in建立二叉树。
建立二叉树l1,h1,l2,h2是序列第一和最后元素下标是序列第一和最后元素下标w{root=(BiTree)malloc(sizeof(BiNode)); //申请结点申请结点w root->data=pre[l1]; //pre[l1]是根是根w for(i=l2;i<=h2;i++) w if(in[i]==pre[l1]) break; //中序序列中中序序列中,根结点将树分成左右子树根结点将树分成左右子树w if(i==l2) root->lchild=null; //无左子树无左子树w else PreInCreat(root->lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)；；w //递归建立递归建立//左子树左子树w if(i==h2) root->rchild=null; //无右子树无右子树w else PreInCreat((*root)->rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) //递归建递归建//立右子树立右子树w}//结束结束PreInCreat算法举例6.6 设一棵二叉树中各结点的值互不相同，设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组其前序序列和中序序列分别存于两个一维数组pre[1..n ]和和mid[1..n ]中，试遍写算法建立该二叉树的二叉链表。
中，试遍写算法建立该二叉树的二叉链表 2024/8/2596线索二叉树线索二叉树 线索二叉树的提出：线索二叉树的提出： 1、遍历的实质：非线性结构线性化（前驱、、遍历的实质：非线性结构线性化（前驱、后继）后继）; 2、前驱和后继是在遍历中得到的、前驱和后继是在遍历中得到的; 3、知道前驱和后继，再遍历时就不需要栈、知道前驱和后继，再遍历时就不需要栈; 4、可以在二叉链表结构中增加前驱和后继两、可以在二叉链表结构中增加前驱和后继两个指针域个指针域; 5、、n个结点的二叉树有个结点的二叉树有n＋＋1个空指针，可以利个空指针，可以利用 2024/8/2597线索二叉树线索二叉树 n个结点的二叉链表中含有个结点的二叉链表中含有n+1个空指针域，可以利用这个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息些空指针域来存放结点的前驱和后继的信息, ,这样的指针称这样的指针称为为“线索线索”，加上了线索的二叉链表称为，加上了线索的二叉链表称为线索链表线索链表，加上线，加上线索的二叉树就是索的二叉树就是线索二叉树线索二叉树（（Threaded Binary Tree）。
将）将二叉树变为线索二叉树的过程称为二叉树变为线索二叉树的过程称为线索化线索化 lchildltagdata rtag rchildltag= rtag= 2024/8/2598线索二叉树线索二叉树 <？序？序><前驱前驱/后继后继/ 全全> 线索化线索化只有空指针才能加线索只有空指针才能加线索 2024/8/2599前序前驱线索化前序前驱线索化w前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID 2024/8/25100中序（全）线索二叉树中序（全）线索二叉树NULLACFEDBNULLA 00E 11C 01D 11F 11B 00NULLA 为方便起见，索链表中增加一个头结点，令其为方便起见，索链表中增加一个头结点，令其lchild域指向二叉树的根结点，域指向二叉树的根结点，rchild域指向访问序列的最域指向访问序列的最后一个结点，这样，就建立了一个后一个结点，这样，就建立了一个双向线索链表双向线索链表 2024/8/25101后序（全）线索化后序（全）线索化 2024/8/25102线索链表的类型定义typedef struct BiThrNode {ElemTyte data; struct BiThrNode *lchild, *rchild; 左、右孩子指针左、右孩子指针 int ltag, rtag; }BiThrNode，，*BiThrTree 2024/8/25103算法举例6.7 中序线索化BiThrTree pre=null;//设置前驱设置前驱void InOrderThreat(BiThrTree T){if (T) {InOrderThreat(T->lchild); //左子树中序线索化左子树中序线索化 if (T->lchild==null) {T->ltag=1; T->lchild=pre; } //左线索为左线索为pre; if (T->rchild==null) T->rtag=1; //置右标记，为右线索作准备置右标记，为右线索作准备 if (pre!=null && pre->rtag==1) pre->rchild=T;} //给前驱加后继线索给前驱加后继线索 pre=T; //前驱指针后移前驱指针后移 InOrderThreat(T->rchild); //右子树中序线索化右子树中序线索化 } }//结束结束InOrderThreat 2024/8/25104算法举例6.8 前序线索化BiThrTree pre=null;//设置前驱设置前驱void PreOrderThreat(BiThrTree T){if (T!=null) {if (T->lchild==null) {T->ltag=1; T->lchild=pre;} //设置左线索设置左线索 if (T->rchild==null) T->rtag=1; //为建立右链作准备为建立右链作准备 if (pre!=null && pre->rtag==1) pre->rchild=T; //设置前驱的右线索；设置前驱的右线索； pre=T; //前驱后移前驱后移 if (T->ltag==0) PreOrderThreat(T->lchild); //左子树前序线索化左子树前序线索化 PreOrderThreat(BT->rchild); //右子树前序线索化右子树前序线索化 } } 2024/8/25105算法举例6.9 后序线索化BiThrTree pre=null;//设置前驱设置前驱void PostOrderThreat(BiThrTree T){if (T) {PostOrderThreat(T->lchild); //左子树后序线索化左子树后序线索化 PostOrderThreat(T->rchild); //右子树后序线索化右子树后序线索化 if (T->lchild==null) {T->ltag=1; T->lchild=pre; }//左线索为左线索为pre; if (T->rchild==null) T->rtag=1;//置右标记，为右线索作准备置右标记，为右线索作准备 if (pre!=null && pre->rtag==1) pre->rchild=T;} //给前驱加后继线索给前驱加后继线索 pre=T; //前驱指针后移前驱指针后移 } }//结束结束PostOrderThreat 2024/8/25106算法举例6.10 线索二叉树的中序遍历wvoid InorderTraverseThr(BiThrTree p)w{while(p) 二叉树非空二叉树非空w { while (p->tag==0) 找中序序列的开始结点找中序序列的开始结点 p=p->lchild; printf(p->data);w while(p&&p->rtag= =1)w {p=p->rchild; printf(p->data);}//找找P的中序后继结点的中序后继结点w if(p) p=p->rchild;w }//whilew} InorderTraverseThr 2024/8/25107算法举例6.11 带头结点的线索二叉树 的中序遍历wvoid InorderTraverseThr(BiThrTree thrt)w{p=thrt->lchild;w while(p!=thrt) 二叉树非空二叉树非空w { while (p->ltag==0) 找中序序列的开始结点找中序序列的开始结点w p=p->lchild; w printf(p->data);w while(p->rtag==1 && p->rchild!=thrt)w {p=p->rchild; printf(p->data);}//找找P的中序后继结点的中序后继结点w p=p->rchild;w }// while(p!=thrt) w} InorderTraverseThr 2024/8/25108前序线索树上找前驱和后继找前驱：找前驱： 困难困难找后继找后继：： 若结点有左子女，则左子女是后继；否则，若结点有左子女，则左子女是后继；否则，rchild指向后继。
指向后继 2024/8/25109算法举例6.12 前序线索树上找后继BiThrTree PreorderNext(BiThrTree p){ if (p->ltag= =0) 结点有左子女结点有左子女 return(p->lchild); 结点的左子女为其前序后继结点的左子女为其前序后继 else return(p->rchild) ;} PreorderNext 2024/8/25110中序线索树上找前驱和后继 中序的前驱和后继都往上指向祖先找前驱：找前驱： 若左标记为若左标记为1，则，则lchild指向其前驱；否则，其指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点前驱是其左子树上按中序遍历的最后一个结点找后继找后继：： 若右标记为若右标记为1，则，则rchild指向其后继；否则，指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点其后继是其右子树上按中序遍历的第一个结点 2024/8/25111算法举例6.13 中序线索树上找前驱BiThrTree InorderPre(BiThrTree p){BiThrTree q; if (p->ltag= =1) 结点的左子树为空结点的左子树为空 q=p->lchild 结点的左指针域为左线索，指向其前驱结点的左指针域为左线索，指向其前驱 else {q=p->lchild; p结点的中序前驱是左子树中最右边结点结点的中序前驱是左子树中最右边结点 while (q->rtag==0 ) q=q->rchild; } if return (q);} InorderPre 2024/8/25112算法举例6.14 中序线索树上找后继BiThrTree InorderNext(BiThrTree p){BiThrTree q; if (p->rtag= =1) 结点的右子树为空结点的右子树为空 q=p->rchild 结点的右指针域为右线索，指向其后继结点的右指针域为右线索，指向其后继 else {q=p->rchild; P结点的中序后继是其右子树中最左边结点结点的中序后继是其右子树中最左边结点 while (q->ltag==0 ) q=q->lchild; } if return (q);} InorderNext 2024/8/25113后序线索树上找前驱和后继找前驱：找前驱： 若结点有右子女，则右子女是其前驱；否若结点有右子女，则右子女是其前驱；否则，则，lchild指向其前驱。
指向其前驱找后继找后继：： 困难，需要知道其双亲困难，需要知道其双亲 2024/8/25114算法举例6.15 后序线索树上找前驱BiThrTree PostorderPre(BiThrTree p){ if (p->rtag= =0) 结点有右子女结点有右子女 return(p->rchild); 结点的右子女为其后序前驱结点的右子女为其后序前驱 else return(p->lchild) ;} PreorderPre 2024/8/25115线索树上结点的插入与删除除修改结点指针外，除修改结点指针外，还需要修改线索还需要修改线索 2024/8/25116自测题自测题 16w二叉树索化后，仍不能有效求解的问题是二叉树索化后，仍不能有效求解的问题是（（ ）wA. 先序线索二叉树中求先序后继先序线索二叉树中求先序后继 wB. 中序线索二叉树中求中序后继中序线索二叉树中求中序后继wC. 中序线索二叉树中求中序前驱中序线索二叉树中求中序前驱 wD. 后序线索二叉树中求后序后继后序线索二叉树中求后序后继w【【北方交通大学北方交通大学2003一一.4(2分分)】】 2024/8/25117自测题自测题 17w引入二叉线索树的目的是（引入二叉线索树的目的是（ ））wA．加快查找结点的前驱或后继的速度．加快查找结点的前驱或后继的速度wB．为了能在二叉树中方便的进行插入与删除．为了能在二叉树中方便的进行插入与删除wC．为了能方便的找到双亲．为了能方便的找到双亲 wD．使二叉树的遍历结果唯一．使二叉树的遍历结果唯一 2024/8/25118自测题自测题 18w若若X是二叉中序线索树中一个有左孩子的结点，是二叉中序线索树中一个有左孩子的结点，且且X不为根，则不为根，则x的前驱为的前驱为( ) wA. X的双亲的双亲 wB. X的右子树中最左的结点的右子树中最左的结点 wC. X的左子树中最右结点的左子树中最右结点 wD. X的左子树中最右叶结点的左子树中最右叶结点w【【南京理工大学南京理工大学1996 一一.6 (2分分)】】 2024/8/25119自测题自测题 19w一棵左右子树均不空的二叉树在先序线索化后，一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：其中空的链域的个数是：( )。
wA. 0 wB. 1 wC. 2 wD. 不确定不确定w w【【合肥工业大学合肥工业大学 2000 一一.5 （（2分）分）】】 2024/8/25120树的存储结构w考虑存储结构时，主要考虑逻辑结构：n数据元素n数据元素之间的关系 2024/8/25121树的存储结构ABECDFw双亲表示法双亲表示法 w孩子表示法孩子表示法 w孩子兄弟表示法孩子兄弟表示法 2024/8/25122双亲表示法w使用静态数组（本质是静态链表）静态数组（本质是静态链表）；w数组的每个数据元素，包括两个域：一个域是数据元素数据元素；另一个域用游标指示该结点的双亲结点在数组中的相对位置位置；根结点的游标为-1w特点：n方便找结点的双亲双亲；n顺序存储结构； 2024/8/25123双亲表示法类型定义#define MAX_NODE 64typedef struct Ptnode { ElemTyte data; 数据域 int parent; 双亲指示域 } Ptnode；typedef struct { Ptnode nodes[MAX_NODE]; int n; }Ptree; 2024/8/25124双亲表示示例ACGEDBHF 数组下标 0 1 2 3 4 5 6 7 data A B C D E F G H parent -1 0 0 1 1 2 2 2 2024/8/25125算法举例6.16 双亲表示法 表示的树的深度wint Depth(Ptree t)w{int maxdepth=0;w for(i=1;i<=t.n;i++)w {temp=0; f=i;w while(f>0) // 求结点求结点i的深度的深度w {temp++; f=t.nodes[f].parent; }w if(temp>maxdepth) //最大深度更新最大深度更新 maxdepth=temp; w }wreturn(maxdepth); //返回树的深度返回树的深度w} //结束结束Depth 2024/8/25126孩子表示法w任一数据元素，有任一数据元素，有0个或多个孩子；个或多个孩子；w因此可以设计一个链式存储结构，其结点除因此可以设计一个链式存储结构，其结点除放置数据元素外，还放置若干指针，分别用放置数据元素外，还放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中来指示该结点的所有孩子结点在存储空间中的位置。
的位置 2024/8/25127孩子表示法w方法方法1 1n根据结点的度，设置结点的指针个数，比如若根据结点的度，设置结点的指针个数，比如若结点的度为结点的度为d:d:datachild1child2…childd问题问题：：n量体裁衣，节省存储空间量体裁衣，节省存储空间n不同的数据元素，结点构造不同；不同的数据元素，结点构造不同；n操作不方便操作不方便 2024/8/25128孩子表示法（续）w方法方法2 2n按照树的度定义结点若树的度为按照树的度定义结点若树的度为d,定义定义degree，表示该结点的度，表示该结点的度datachild1child2…childddegree问题问题：n因因degree为树的度，是所有结点的最大的度，为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间因此树中有相当部分的指针域为空，浪费空间n有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有 n(k-1)+1个 2024/8/25129孩子表示法（续）w有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有n(k-1)+1个w证明：证明：nn个结点的树，除根结点外，每个结点有一个指针个结点的树，除根结点外，每个结点有一个指针指向，也就是树中有指向，也就是树中有n-1个有效链域（指针）个有效链域（指针）n而按该结点定义，而按该结点定义，n个结点总的指针域有：个结点总的指针域有：nk个。
个n因此空链域：因此空链域：nk – (n-1) = n ( k - 1 ) + 1 2024/8/25130w一个静态数组，存放所有的结点一个静态数组，存放所有的结点w数组的每个数据元素，包括两部分：数组的每个数据元素，包括两部分：数数据元素据元素，，指针指针；指针指向一个链表，链；指针指向一个链表，链表结点的数据域是一个整数，表示该结表结点的数据域是一个整数，表示该结点的孩子在点的孩子在数组中的下标数组中的下标；；w特点：特点：n顺序顺序+链式存储结构；链式存储结构；n找孩子容易，找双亲难；找孩子容易，找双亲难；孩子表示法（续）孩子表示法（续） 2024/8/25131孩子表示法ACGEDBHF01234567∧∧∧∧657 ∧ABCDEFG312 ∧4 ∧∧H 2024/8/25132双亲孩子链表w在静态数组的结点中增加一个域，表示该结点的双亲在静态数组的结点中增加一个域，表示该结点的双亲在该树组中的相对位置在该树组中的相对位置w有利于寻找孩子结点和双亲结点有利于寻找孩子结点和双亲结点ACGEDBHF01234567657 ∧312 ∧∧G∧∧∧ABCDEF-1001122parent4 ∧H2∧ 2024/8/25133孩子表示法类型定义#define MAX_NODE 64typedef struct Ctnode 孩子结点孩子结点{ int child; struct Ctnode *next;}*childlink;typedef struct 头结点头结点{ ElemType data; childlink firstchild;}CTBox;CTBox nodes[MAX_NODE]；； 2024/8/25134孩子兄弟表示法w从向下的纵向和向右的横向描述树；从向下的纵向和向右的横向描述树；w定义结点，除存放数据元素外，存放两个定义结点，除存放数据元素外，存放两个指针，一个指向该结点的指针，一个指向该结点的第一个孩子第一个孩子，另，另一个指向该结点的一个指向该结点的下一个兄弟下一个兄弟；； 2024/8/25135孩子兄弟表示法typedef struct CSNode {ElemTyte data; struct CSNode *firstchild, *nextsibling; }CSNode,*CSTree; 该该表表示示方方法法又又称称二二叉叉树树表表示示法法，，本本质质上上与与二二叉链表表示法一致。
叉链表表示法一致datafirstchildnextsibling 2024/8/25136孩子兄弟表示法A∧∧BC∧∧D∧∧E∧∧F∧∧G∧∧∧∧H∧∧∧∧ACGEDBHF 2024/8/25137算法举例6.16 求孩子孩子-兄弟表示法兄弟表示法 存储的森林的存储的森林的叶子数叶子数wint Leaves (Tree t)w//计算以孩子计算以孩子-兄弟表示法存储的森林的兄弟表示法存储的森林的叶子数叶子数w{if(t==null) return 0;w else{ if(t->firstchild==null) //无孩子的结点必是叶子无孩子的结点必是叶子w return(1+Leaves(t->nextsibling)); w //返回叶子结点和其兄弟子树中的叶子结点数返回叶子结点和其兄弟子树中的叶子结点数w else return (Leaves(t->firstchild)+w Leaves(t->nextsibling)); w //孩子子树和兄弟子树中叶子数之和孩子子树和兄弟子树中叶子数之和w }w}//结束结束Leaves 2024/8/25138算法举例6.17 求孩子孩子-兄弟表示法兄弟表示法 存储的树的深度存储的树的深度wint Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度递归求以孩子兄弟链表表示的树的深度w{int hc,hs; w if (bt==null) return (0);w else if (!bt->firstchild) w return max(1,height(bt->nextsibling））；））；w //子女空，取子女空，取1和兄弟的深度和兄弟的深度 的大者的大者w else // 高度取子女高度高度取子女高度+1和兄弟子树高度的大者和兄弟子树高度的大者w {hc=height(bt->firstchild)；； //第一子女树高第一子女树高w hs=height(bt->nextsibling)；；//兄弟树高兄弟树高w if(hc+1>hs) w return(hc+1); w else return (hs); w }w}//结束结束height 2024/8/25139w若若树采用孩子兄弟表示法树采用孩子兄弟表示法，二叉树采用二叉链表，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。
表示，则从存储结构上看，结点定义完全相同因此，在使用该存储结构下，树和二叉树是等价因此，在使用该存储结构下，树和二叉树是等价的，树可以转化为二叉树的，树可以转化为二叉树树和二叉树的转化w步骤步骤（（1））连线连线：在兄弟结点之间加一条连线在兄弟结点之间加一条连线2））切切线线：：对对于于每每个个结结点点，，除除了了保保留留与与其其最最左左孩孩子的连线外，切掉该结点与其它孩子的连线子的连线外，切掉该结点与其它孩子的连线 （（3））旋转旋转：将按（：将按（1）、（）、（2）的方法形成的二叉）的方法形成的二叉树，沿顺时针方向旋转树，沿顺时针方向旋转450,就可以得到一棵形式上就可以得到一棵形式上更为清楚的二叉树更为清楚的二叉树 2024/8/25140树和二叉树转化例FGHABCEDFGHABCEDFGHABCEDFHABGCED 2024/8/25141自测题自测题 w 6. 将森林转换为对应的二叉树，若在二叉树中，将森林转换为对应的二叉树，若在二叉树中，结点结点u是结点是结点v的父结点的父结点，则在原来的森的父结点的父结点，则在原来的森林中，林中，u和和v可能具有的关系是可能具有的关系是wⅠ. 父子关系父子关系 wⅡ. 兄弟关系兄弟关系 wⅢ. u的父结点与的父结点与v的父结点是兄弟关系的父结点是兄弟关系wA. 只有只有Ⅱ B. Ⅰ和和Ⅱ wC. Ⅰ和和Ⅲ D. Ⅰ、、Ⅱ和和Ⅲw【2009年全国硕士研究生入学计算机学科专业基础综合试题年全国硕士研究生入学计算机学科专业基础综合试题】 2024/8/25142自测题自测题 2020 将树转换成二叉树树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空ABCDEFG H IJKLABCDEFGHIJKLCDABCDEFGHIJKLC 2024/8/25143森林到二叉树的转换w若若树采用孩子兄弟表示法树采用孩子兄弟表示法，二叉树采用，二叉树采用二叉链表二叉链表表示，则：表示，则：n任一棵树，都可以找到唯一的一棵二叉树和它任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树。
对应，而且该二叉树没有右子树因此因此一棵一棵二二叉树，不一定保证能转换为叉树，不一定保证能转换为一棵一棵(>=1)树树)n若把森林中的第二棵树的根结点，看成是第一若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树（该二叉树的根结点的右子女换为一棵二叉树（该二叉树的根结点的右子女没有右子树）没有右子树）n依次类推，可以认为森林和二叉树是一一对应依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则的，从而得到二叉树和森林的转换规则 2024/8/25144森林到二叉树的转换w步骤：步骤：w（（1））连线连线：在兄弟（各树的根结点看作兄弟）：在兄弟（各树的根结点看作兄弟）结点之间加一条连线结点之间加一条连线w（（2））切线切线：对于每个结点，除了保留与其最左：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线孩子的连线外，切掉该结点与其它孩子的连线 w（（3））旋转旋转：将按（：将按（1）、（）、（2）的方法形成的二）的方法形成的二叉树，沿顺时针方向旋转叉树，沿顺时针方向旋转450,就可以得到一棵形就可以得到一棵形式上更为清楚的二叉树。
式上更为清楚的二叉树 2024/8/25145AGJBC DHIKEFLM NABGCEHFJKILMND自测题自测题 21 森林转为二叉树森林转为二叉树 2024/8/25146二叉树到森林的转换w 如果B={root,LBT,RBT}是一棵二二叉叉树树，F={T1 ,T2 ,…,Tn}表示与其对应的森林森林，转换规则如下：（1）若B为空，则F为空；（2）若B非空，则F中第一棵树第一棵树T1的根的根即为二叉二叉树树B的根的根root，T1中根结点的子树森林根结点的子树森林F1是由B的的左子树左子树LBT转换而成的森林；F中除除T1之外其余之外其余树组成的森林树组成的森林F’={ T2 ,T3…,Tn}是由B的右子树的右子树RBT转化而成的森林 2024/8/25147二叉树到森林的转换例1IABDFGHKCEJIABDJHCEFGK 2024/8/25148DEFGHIJLABCKFILCABEGHJKD二叉树到森林的转换例2 2024/8/25149树和森林的遍历树和森林的遍历 树的遍历树的遍历： （（1）前序遍历）前序遍历 （（2）后序遍历）后序遍历森林的遍历森林的遍历： （（1）前序遍历）前序遍历 （（2）中序遍历）中序遍历（有的教材称森林的（有的教材称森林的“中序遍历中序遍历”为为“后序遍历后序遍历”）） 2024/8/25150树的遍历前序遍历树前序遍历树的规则为：的规则为：若树非空，则：若树非空，则：（（1）访问树的根结点；）访问树的根结点；（（2）依次前序遍历树的第一棵子树、第二棵子树，）依次前序遍历树的第一棵子树、第二棵子树，……后序遍历树后序遍历树的规则为：的规则为：若树非空，则：若树非空，则：（（1）依次后序遍历树的第一棵子树、第二棵子树，）依次后序遍历树的第一棵子树、第二棵子树，……（（2）访问树的根结点；）访问树的根结点； ABCED前序遍历序列：前序遍历序列： ABCDE后序遍历序列：后序遍历序列： BCEDA 2024/8/25151树的遍历与二叉树遍历对应 树树的的前前序序遍遍历历序序列列与与其其对对应应的的二二叉叉树树的的前前序序遍遍历序列相同；历序列相同； 树树的的后后序序遍遍历历序序列列与与其其对对应应的的二二叉叉树树的的中中序序遍遍历序列相同；历序列相同； 2024/8/25152森林的遍历前序遍历森林前序遍历森林的规则为：的规则为：若森林为空，返回；否则：若森林为空，返回；否则：（（1）访问森林中第一棵树的根结点；）访问森林中第一棵树的根结点；（（2）前序遍历第一棵树的子树森林；）前序遍历第一棵树的子树森林；（（3）前序遍历其它树组成的森林；）前序遍历其它树组成的森林； 中序遍历森林中序遍历森林的规则为：的规则为：若森林为空，返回；否则：若森林为空，返回；否则：（（1）中序遍历第一棵树的子树森林；）中序遍历第一棵树的子树森林；（（2）访问第一棵树的根结点；）访问第一棵树的根结点；（（3）中序遍历）中序遍历除除第一棵树外其它树组成的森林；第一棵树外其它树组成的森林； ABCFGHJIED右图森林的前序遍历序列为： ABCDEFGHIJ右图森林的中序遍历序列为：BDCAFEHIJG 2024/8/25153森林的遍历与二叉树的遍历对应 森森林林的的先先序序遍遍历历序序列列与与其其对对应应的的二二叉叉树树的的先先序序遍历序列相同；遍历序列相同； 森森林林的的中中序序遍遍历历序序列列与与其其对对应应的的二二叉叉树树的的中中序序遍历序列相同；遍历序列相同； 2024/8/25154自测题自测题 22w已知一个森林的先序序列和后序序列如下，请已知一个森林的先序序列和后序序列如下，请构造出该森林。
构造出该森林w先序序列：先序序列：ABCDEFGHIJKLMNOw后序序列：后序序列：CDEBFHIJGAMLONK 2024/8/25155自测题自测题 23w设森林设森林F中有三棵树，第一，第二，第三棵树中有三棵树，第一，第二，第三棵树的结点个数分别为的结点个数分别为M1，，M2和和M3与森林F对对应的二叉树根结点的右子树上的结点个数是应的二叉树根结点的右子树上的结点个数是 （（ )wA．．M1 wB．．M1+M2 wC．．M3 wD．．M2+M3 2024/8/25156自测题自测题 24w设设F是一个森林，是一个森林，B是由是由F变换得的二叉树若变换得的二叉树若F中有中有n个非终端结点，则个非终端结点，则B中右指针域为空的中右指针域为空的结点有（结点有（ ）个wA．．n-1 wB．．n wC．．n+1 wD．．n+2 w【【西安电子科技大学西安电子科技大学1998 一一.10 （（2分）分）】】 2024/8/25157自测题自测题 25w设设X是树是树T中的一个非根结点，中的一个非根结点，B是是T所对应的所对应的二叉树。
在二叉树在B中，中，X是其双亲的右孩子，下列是其双亲的右孩子，下列结论正确的是结论正确的是( )wA. 在树在树T中，中，X是其双亲的第一个孩子是其双亲的第一个孩子 wB. 在树在树T中，中，X一定无右边兄弟一定无右边兄弟wC. 在树在树T中，中，X一定是叶子结点一定是叶子结点 wD. 在树在树T中，中，X一定有左边兄弟一定有左边兄弟w【【南京邮电学院南京邮电学院2004一一.4(3分分)】】 2024/8/25158自测题自测题 26w设树形设树形T在后根次序下的结点排列和各结点相在后根次序下的结点排列和各结点相应的次数如下：应的次数如下：w后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡw次 数：００００３０００２０２４次 数：００００３０００２０２４w请画出Ｔ的树形结构图请画出Ｔ的树形结构图 w【【吉林大学吉林大学 2001 一一.2 （（4分）分）】】 2024/8/25159哈夫曼树的概念 w路路径径：从从树树中中一一个个结结点点到到另另一一个个结结点点之之间的分支构成两个结点之间的间的分支构成两个结点之间的路径w路路径径长长度度：路路径径上上的的分分支支数数目目称称为为路路径径长度长度。
w树树的的路路径径长长度度：：树树的的根根结结点点到到树树中中每每一一个结点的路径长度的和个结点的路径长度的和 2024/8/25160w结结点点的的带带权权的的路路径径长长度度：该该结结点点到到根根结结点点之间的路程长度与该结点上权的乘积之间的路程长度与该结点上权的乘积w树树的的带带权权的的路路径径长长度度：树树中中所所有有叶叶子子结结点点的的带带权权的的路路径径长长度度的的和和通通常常记记为为：：WPL(Weighted Path Length)w由由n个个带带权权值值的的叶叶子子结结点点构构成成的的二二叉叉树树中中，WPL最最小小的的二二叉叉树树称称为为最最优优二二叉叉树树，或哈夫曼（（ Huffman）树哈夫曼树的概念（续） 2024/8/25161 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35dcab2475 2024/8/25162哈夫曼树的性质w1、哈夫曼树只有度为哈夫曼树只有度为0和和2的结点，无度的结点，无度为为1的结点；的结点；w2、权值大的结点离根结点近；、权值大的结点离根结点近；w3、、n个叶子的哈夫曼树的形态一般不唯一，个叶子的哈夫曼树的形态一般不唯一，但但WPL是相同的；是相同的；w4、、n个叶子的哈夫曼树共有个叶子的哈夫曼树共有2n-1个结点。
个结点 2024/8/25163v根据给定的根据给定的n个权值个权值{w1,w2,…,wn}，，构造构造n棵只有棵只有根结点的二叉树，令其权值为根结点的二叉树，令其权值为wj;v在森林中选取两棵根结点权值最小的树作左右子在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和值为其左右子树根结点权值之和;v在森林中删除这两棵树，在森林中删除这两棵树，同时将新得到的二叉树同时将新得到的二叉树加入森林中加入森林中;v重复上述两步，直到只含一棵树为止，这棵树即重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树哈夫曼树 v构造构造HuffmanHuffman树步骤树步骤 2024/8/25164dcba9653ba96358a9614358962314538abcdcbd哈夫曼树的构造举例 2024/8/25165例例 w={5, 29, 7, 8, 14, 23, 3, 11}51429 7823 3111429 7823 1153887151429235381111538191429238715115381929 23148715292914871529115381923421153819234229148715295811538192342291487152958100哈夫曼树的形态是不唯一的哈夫曼树的形态是不唯一的 2024/8/25166自测题自测题 27w给给定定权权值值7，，6，，3，，32，，5，，26，，12，，9，，构构造造相相应应的的哈哈夫夫曼曼树树，，并并计计算算其其带带权权路路径径长长度度。
为为使使结结果果答答案案唯唯一一，，请请用用左左结结点点的的值值小小于于等等于于右右结点的值来构造哈夫曼树结点的值来构造哈夫曼树 哈夫曼树的类型定义wtypedef structw {int weight;w int parent, lchild, rchild;w } HufmTree; 2024/8/25168哈夫曼树的构造算法viod CreatHuffman(HufmTree tree[]，，int n){ 构造哈夫曼树，构造哈夫曼树，n为初始森林中的结点数为初始森林中的结点数 int i,j,t1,t2；； if (n<=1) return; m=2*n; //下标为下标为0的单元不用的单元不用 for (i=1; i w但：译码有困难：但：译码有困难：“0001”有多种译法：有多种译法：CCP, AP, CAT, ……u前缀码前缀码 2024/8/25172哈夫曼编码w前缀码前缀码w用二叉树可以构造前缀码；用二叉树可以构造前缀码；w哈夫曼树可以构造最短的前哈夫曼树可以构造最短的前缀码（哈夫曼编码）缀码（哈夫曼编码） 2024/8/25173v思想：根据字符出现频率编码，使电文总长最短例例 要传输的字符集要传输的字符集 D={a,b,c,d,e } 字符出现频率字符出现频率 w={0.12, 0.40, 0.15, 0.08, 0.25}HuffmanHuffman编码：数据通信用的二进制编码编码：数据通信用的二进制编码字符概率编码1编码2编码3a0.120000001111b0.40001110c0.1501001110d0.080110111110e0.251001010编码编码1：：3*(0.12+0.40+0.15+0.08+0.25)=3编码编码2: 3*(0.12+0.08)+2*(0.40+0.15+0.25)=2.2编码编码3: 4*(0.12+0.08)+3*0.15+2*0.25+0.40=1.9 2024/8/25174哈夫曼编码哈夫曼编码 w前缀编码方法：前缀编码方法：n设有设有n种字符，在一个电文中，第种字符，在一个电文中，第i种字符出种字符出现的次数为现的次数为Wi,编码长度为编码长度为li，则一段电文的，则一段电文的总长度为：总长度为： L = w1l1 + w2l2 + … + wnln = ∑ wilin使使L最小，可以看作是已知最小，可以看作是已知n个结点的权个结点的权wi，，求一棵求一棵Huffman树的问题。 由此得到的二进树的问题由此得到的二进制编码，称为制编码，称为Huffman编码 2024/8/25175ACBDEF160000111364125736912G0112801A：：100B：：11C：：011D：：1011E：：1010F：：000G：：01哈夫曼编码哈夫曼编码 2024/8/25176哈夫曼编码哈夫曼编码 wHuffmanHuffman树树中，一定没有度为一定没有度为１１的结点的结点（称为严格或正则二叉树），因此有（称为严格或正则二叉树），因此有n n个个结点的结点的Huffman树，一定有树，一定有2n-12n-1个结点w在在编码编码中，需要从中，需要从叶子叶子结点出发，走从结点出发，走从叶子叶子到到根根的路径；的路径；译码译码中，需要从中，需要从根根到到叶子叶子 2024/8/25177定义哈夫曼编码的存储结构wtypedef structw // 哈夫曼编码的存储结构哈夫曼编码的存储结构w{char ch;w char bits[n+1];w}CodeNode;wtypedef CodeNode HuffmanCode[n]; 2024/8/25178求哈夫曼编码的算法wvoid HuffmanCoding(HufmTree tree[ ], HuffmanCode H[ ])w{// 根据哈夫曼树根据哈夫曼树tree求哈夫曼编码求哈夫曼编码w int c, t, i; // c指向孩子，指向孩子，t 指向双亲的位置指向双亲的位置w int start; // 指示编码在临时向量中的起始位置指示编码在临时向量中的起始位置w char cd[n+1]; // 存放编码的临时向量存放编码的临时向量w cd[n]= ‘ \ 0’; // 编码结束符编码结束符w for(i=0; i 二叉树的每个结点有三个域径长度二叉树的每个结点有三个域:lchild,rchild 和和element算法可用算法可用PASCAL语言或语言或C语言描述，语言描述，要求写出类型说明要求写出类型说明 【【南京邮电学院南京邮电学院2002五五(14分分)】】 2024/8/25181求哈夫曼树的带权路径长度树的带权路径长度wvoid HuffmanWPl(BiTree t)w ∥∥求哈夫曼树的带权路径长度求哈夫曼树的带权路径长度w {if(t)w {HuffmanWPl(t->lchild); HuffmanWPl(t->rchild);w if(!t->lchild && !t->rchild)w {h=height(t); ∥∥求叶子结点高度，前面有算法，不再重写求叶子结点高度，前面有算法，不再重写 w wpl+=t->element*h; ∥∥wpl为全局变量，初值为为全局变量，初值为0.0 w }∥∥if w } w } 2024/8/25182算法举例6.19 树的应用 unix的文件的文件/目录结构如左图所示，目录结构如左图所示，*表示目录，括弧内的数字表示目录，括弧内的数字是文件是文件/目录的大小。 目录的大小1) 试设计一种数据结构表达这种关系试设计一种数据结构表达这种关系(2) 设计一种算法，输出如右图所示的结果设计一种算法，输出如右图所示的结果(次序和数字不能改变次序和数字不能改变) 【【浙江大学浙江大学2004五五(15分分)】】/usr* (1) mark* (1) hw.c (3) course* (1) aa.txt(12) alex* (1) hw.c (5) bak* (1) aa.txt (13) hw.c (3)aa.txt (12)course (13)mark (17)hw.c (5)alex (6)aa.txt (13)bak (14)/usr (38) 2024/8/25183算法举例6.19 树的应用 【【题目分析题目分析】】用树形结构表示这种文件用树形结构表示这种文件/目录结目录结构，题中的输出是对树进行后根遍历的结果，括构，题中的输出是对树进行后根遍历的结果，括号内数字代表文件大小：原文件号内数字代表文件大小：原文件(*.c和和*.txt)是是叶叶子结点，其大小照原大小输出，子目录文件的大子结点，其大小照原大小输出，子目录文件的大小是其本身大小和其目录下的文件大小之和。 小是其本身大小和其目录下的文件大小之和设树用孩子兄弟链表表示设树用孩子兄弟链表表示 2024/8/25184算法举例6.19 树的应用的算法wtypedef struct CSNodew {char name[maxsize]; ∥∥目录目录(文件文件)名名,maxsize为文件名最大长度为文件名最大长度w int byt; ∥∥文件大小文件大小w struct CSNode *fch, *nsib; ∥∥ 第一子女，兄弟第一子女，兄弟w }CSNode, *CSTree;wint num; ∥∥计算子目录下的文件大小计算子目录下的文件大小wint ByteNumber(CSTree t)w {if(t)w {ByteNumber(t->fch);w num+=t->byt;w ByteNumber(t->nsib;w }∥∥if w }∥∥结束结束 2024/8/25185wvoid InOrder(CSTree t)w {if(t)w {InOrder(t->fch);w if(t->fch==null) w printf(“%s(%d)\n”,t->name,t->byt); ∥∥t是叶子，直接输出是叶子，直接输出w else {num=0; num=ByteNumber(t); ∥∥计算子目录下文件大小计算子目录下文件大小w printf(“%s(%d)\n”,t->name,num);∥∥输出子目录大小输出子目录大小w }w InOrder(t->nsib);w }∥∥if w }∥∥算法举例6.19 树的应用的算法（续） 。
