1、108第6章 树与森林一、复习要点本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。特别是二叉树的遍历算法，它们与许多以此为基础的递归算法都必须认真学习。因为树的先根遍历次序与对应二叉树表示的前序遍历次序一致，树的后根遍历次序与对应二叉树的中序遍历次序一致，因此可以据此得出树的遍历算法。线索化二叉树是直接利用二叉链表的空链指针记入前驱和后继线索，从而简化二叉树的遍历。堆是一种二叉树的应用，可以用它作为优先级队列的实现。它的存储表示是完全二叉树的顺序存储方式，它的定义不要求堆中的数据有序，但要求双亲结点与子女结点必须满足某种关系。本章最后讨论霍夫曼树。这种树是扩充二叉树，要求在外
2、结点上带有权值，在构造霍夫曼树时必须注意一个新结点的左子女上所带的权值小于右子女上所带的权值，这不是霍夫曼树必须这样，而是实现算法造成这种结果。此外，作为霍夫曼树的应用，引入霍夫曼编码。通常让霍夫曼树的左分支代表编码“0”，右分支代表编码“1”，得到霍夫曼编码。这是一种不等长编码，可以有效地实现数据压缩。本章复习的要点是：1、基本知识点要求理解树和森林的定义，树的抽象数据类型，二叉树的定义，二叉树的性质，二叉树的抽象数据类型，二叉树的数组表示和链表存储表示。要求掌握二叉树的遍历，包括中序遍历、前序遍历、后序遍历方法，要求理解二叉树的计数方法及从二叉树遍历结果得到二叉树的方法。对于线索化二叉树，
3、要求理解什么是线索，中序线索化二叉树的结构特性及寻找某结点的前驱和后继的方法。此外，需要理解堆的定义及其实现的方法，本章只考虑用完全二叉树的顺序存储来实现。还需要理解堆的建立，插入与删除过程。要求掌握树/森林与二叉树的转换，树的遍历方法。最后要求掌握霍夫曼树的实现方法及霍夫曼编码的概念。2、算法设计 建立二叉树的递归算法。 前序、中序、后序遍历二叉树的递归算法。 使用栈的前序、中序、后序遍历的非递归算法。 统计二叉树结点个数，二叉树叶结点个数，二叉树高度的递归算法。 自左向右链接二叉树叶结点的递归算法。 判断两棵二叉树相等和交换二叉树左、右子女指针的递归算法。 通过二叉树的遍历建立前序线索化二
4、叉树和中序线索化二叉树的算法。 中序线索化二叉树上的中序遍历算法。 前序线索化二叉树上的前序遍历算法。 后序线索化二叉树上的后序遍历算法。 利用堆实现优先级队列的操作。 堆的自上向下和自下向上的调整算法。 堆的插入与删除算法。 树的先根、后根、层次遍历算法（基于树的二叉树表示）。109二、难点与重点1、树：树的定义、树的基本运算 树的分层定义是递归的 树中结点个数与高度的关系2、二叉树：二叉树定义、二叉树的基本运算 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数 完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置 二叉树的前序中序后序遍历的递归算法和使用栈的非递归算法 二
5、叉树的层次遍历算法 中序线索化二叉树、前驱与后继的查找方法、建立中序线索化二叉树的算法3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算 霍夫曼树是带权路径长度最小的扩充二叉树 构造霍夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树 在构造过程中，新二叉树按根的权值加入到森林的最后4、树与森林 树的广义表表示、树的双亲表示、树的左子女-右兄弟表示 树、森林与二叉树的对应关系 树的先根后根层次遍历算法5、堆：堆的定义、堆的插入与删除算法 形成堆时用到的向下调整算法 形成堆时的调整过程及比较次数的上界估计 堆插入时用到的向上调整算法三、教材中习
6、题的解析6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现：(1) operator ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示；(2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树；(3) operator = ( ) 测试用广义表表示的两棵树是否相等；(4) operator #define maxSubTreeNum 20; /最大子树(子表)个数class GenTree; /GenTree类的前视声明class GenTreeNode /广义树结点类的声明friend class GenTree;private:int utype; /结点标志
7、：=0, 数据; =1, 子女GenTreeNode * nextSibling; /utype=0, 指向第一个子女 ;/utype=1或2, 指向同一层下一兄弟union /联合110char RootData; /utype=0, 根结点数据char Childdata; /utype=1, 子女结点数据GenTreeNode *firstChild; /utype=2, 指向第一个子女的指针 public:GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL) if ( tp = 0 ) RootData =
8、 item; else ChildData = item; /构造函数：构造广义表表示的树的数据结点GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) /构造函数：构造广义表表示的树的子树结点int nodetype ( ) return utype; /返回结点的数据类型char GetData ( ) return data; /返回数据结点的值GenTreeNode * GetFchild ( ) return firstChild; /返回子树结点的地址G
9、enTreeNode * GetNsibling ( ) return nextSibling; /返回下一个兄弟结点的地址void setInfo ( char item ) data = item; /将结点中的值修改为itemvoid setFchild ( GenTreeNode * ptr ) firstChild = ptr; /将结点中的子树指针修改为ptrvoid setNsinbilg ( GenTreeNode * ptr ) nextSibling = ptr; ;class GenTree /广义树类定义 private:GenTreeNode *first; /根指针
10、char retValue; /建树时的停止输入标志GenTreeNode *Copy ( GenTreeNode * ptr ); /复制一个ptr 指示的子树void Traverse ( GenListNode * ptr ); /对ptr 为根的子树遍历并输出void Remove ( GenTreeNode *ptr ); /将以ptr 为根的广义树结构释放friend int Equal ( GenTreeNode *s, GenTreeNode *t ); /比较以s和t为根的树是否相等public:GenTree ( ); /构造函数GenTree ( GenTree /复制构
11、造函数 GenTree ( ); /析构函数 friend int operator = ( GenTree /判两棵树t1与t2是否相等friend istream /输入friend ostream return in;void GenTree : ConstructTree ( istream /用于建表时记忆回退地址111GenTreeNode * p, q, r; Type ch; cin value; /广义树停止输入标志数据 cin ch; first = q = new GenTreeNode ( 0, ch ); /建立整个树的根结点cin ch; if ( ch = ( )
12、 st.Push ( q ); /接着应是(, 进栈cin ch;while ( ch != value ) /逐个结点加入switch ( ch ) case ( : p = new GenTreeNode ( q ); /建立子树, p-firstChild = qr = st.GetTop( ); st.Pop( ); /从栈中退出前一结点r-nextSibling = p; /插在前一结点r之后st.Push( p ); st.Push( q ); /子树结点及子树根结点进栈break;case ) : q-nextSibling = NULL; st.pop( ); /子树建成, 封
13、闭链, 退到上层if ( st.IsEmpty ( ) = 0 ) q = st.GetTop( ); /栈不空, 取上层链子树结点else return 0; /栈空, 无上层链, 算法结束break;case , : break;default : p = q; if ( isupper (ch) ) q = new GenTreeNode ( 0, ch ); /大写字母, 建根结点else q = new GenTreeNode ( 1, ch ); /非大写字母, 建数据结点p-nextSibling = q; /链接cin ch; (2) 复制构造函数 用另一棵表示为广义表的树初始
14、化一棵树；GenTree : GenTree ( const GenTreeGenTreeNode* GenTree : Copy ( GenTreeNode *ptr ) /私有函数，复制一个ptr指示的用广义表表示的子树GenTreeNode *q = NULL;if ( ptr != NULL ) q = new GenTreeNode ( ptr-utype, NULL );switch ( ptr-utype ) /根据结点类型utype传送值域case 0 : q-RootData = ptr-RootData; break;/传送根结点数据case 1 : q-ChildData
15、 = ptr-ChildData; break; /传送子女结点数据case 2 : q-firstChild = Copy ( ptr-firstChild ); break; /递归传送子树信息q-nextSibling = Copy ( ptr-nextSibling ); /复制同一层下一结点为头的表return q;112(3) operator = ( ) 测试用广义表表示的两棵树是否相等int operator = ( GenTreeint Equal ( GenTreeNode *t1, GenTreeNode *t2 ) /是GenTreeNode的友元函数int x;if
16、( t1 = NULL /表t1与表t2都是空树, 相等if ( t1 != NULL /根数据结点break;case 1 : x = ( t1-ChildData = t2-ChildData ) ? 1 : 0; /子女数据结点break;case 2 : x = Equal ( t1-firstChild, t2-firstChild ); /递归比较其子树if ( x ) return Equal ( t1-nextSibling, t2-nextSibling );/相等, 递归比较同一层的下一个结点; 不等, 不再递归比较return 0;(4) operator utype =
17、 0 ) out RootData utype = 1 ) /子女数据结点out ChildData;if ( ptr-nextSibling != NULL ) out firstChild ); /向子树方向搜索if ( ptr-nextSibling != NULL ) out nextSibling ); /向同一层下一兄弟搜索else out nextSibling;if ( p-utype = 2 ) Remove ( p-firstChild ); /在子树中删除ptr-nextSibling = p-nextSibling; delete ( p ); /释放结点p6-2 列出
18、右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有、 、。分支结点有、 、。结点 的层次为 0；结点 、的层次为1；结点、 的层次为 2；结点、的层次为3；结点 的层次为4。6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。【解答】6-4 用嵌套类写出用链表表示的二叉树的类声明。【解答】#include 0 1 2 3 4 5 6 7 8 910 11 12 13 14 15 16 17 18 顺序表示 二叉链表表示 114template class BinaryTree private:template class BinT
19、reeNode public:BinTreeNode *leftChild, *rightChild;Type data;Type RefValue;BinTreeNode * root; BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current );int Insert ( BinTreeNode *current, const Typeint Find ( BinTreeNode *current, const Typevoid destroy ( BinTreeNode *current );void Traverse
20、( BinTreeNode *current, ostreampublic:BinaryTree ( ) : root ( NULL ) BinaryTree ( Type value ) : RefValue ( value ), root ( NULL ) BinaryTree ( ) destroy (root); BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL
21、 ) Type BinTreeNode* GetLeft ( ) const return leftChild; BinTreeNode* GetRight ( ) const return rightChild; void SetData ( const Type void SetLeft ( BinTreeNode *L ) leftChild = L; void SetRight ( BinTreeNode *R ) RightChild =R; int IsEmpty ( ) return root = NULL ? 1 : 0; BinTreeNode *Parent ( BinTr
22、eeNode *current ) return root = NULL | root = current ? NULL : Parent ( root, current ); BinTreeNode * LeftChild ( BinTreeNode *current ) return current != NULL ? current-leftChild : NULL; BinTreeNode * RighttChild ( BinTreeNode *current ) return current != NULL ? current-rightChild : NULL; int Inse
23、rt ( const TypeBinTreeNode * Find ( const TypeBinTreeNode * GetRoot ( ) const return root; friend istream /输入二叉树friend ostream /输出二叉树6-5 在结点个数为n (n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1151个分支结点。6
24、-6 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】116具有3个结点的树 具有3个结点的二叉树6-7 如果一棵树有n 1个度为1的结点, 有n 2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。【解答】总结点数 n = n 0 + n1 + n2 + + nm总分支数 e = n-1 = n 0 + n1 + n2 + + nm-1= m*nm + (m-1)*nm-1 + + 2*n2 + n1则有 )(20ii6-8 试分别找出满足以下条件的所有二叉树:(1) 二叉树的前序序列与中序序列相同;(2) 二叉树的中序序列与后序序列相同;
25、(3) 二叉树的前序序列与后序序列相同。【解答】(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数。(2) 以二叉树为参数，交换每个结点的左子女和右子女。【解答】(1) 统计二叉树中叶结点个数int BinaryTree : leaf ( BinTreeNode * ptr ) if ( ptr = NULL ) return 0;else if (
26、ptr-leftChild = NULL else return leaf ( ptr-leftChild ) + leaf ( ptr-rightChild ); (2) 交换每个结点的左子女和右子女void BinaryTree : exchange ( BinTreeNode * ptr ) BinTreeNode * temp;if ( ptr-leftChild != NULL | ptr-rightChild != NULL ) temp = ptr-leftChild;ptr-leftChild = ptr-rightChild;ptr-rightChild = temp;exc
27、hange ( ptr-leftChild );exchange ( ptr-rightChild );1176-10 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1) 各层的结点个数是多少?(2) 编号为i 的结点的父结点(若存在) 的编号是多少?(3) 编号为i 的结点的第m个孩子结点( 若存在)的编号是多少 ?(4) 编号为i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?【解答】(
28、1) ki ( i = 0, 1, , h ) (2) 2(3) ( i-1)*k + m + 1 (4) ( i-1 ) % k 0 或 时有右兄弟，右兄弟为i + 1。k*2i(5) h = logk (n*(k-1)+1)-1 (n = 0时h = -1 )6-11 试用判定树的方法给出在中序线索化二叉树上：【解答】(1) 搜索指定结点的在中序下的后继。设指针q指示中序线索化二叉树中的指定结点，指针p指示其后继结点。找q的右子树中在中序下的第一个结点的程序为：p = q-rightChild;while ( p-leftThread = 1 ) p = p-leftChild; / p即
29、为q的后继(2) 搜索指定结点的在前序下的后继。(3) 搜索指定结点的在后序下的后继。q-rightThread = 1?= q-rightChild = NULL ?=q无后继q的后继为q- rightChildq的后继为q的右子树中中序下的第一个结点q-leftThread = 0 ?=q的后继为q- leftChildq-rightThread = 0 ?=q的后继为q- rightChildp = q;while ( p-rightThread = 1 if ( p-rightChild =NULL ) q无后继;else的后继为p- rightChild( p = parent (q ) ) = NULL ?=q的后继为pp-rightThread = 1 | p-rightChild = q ?= q的后继为p的右子树中后序下的第一个结点q无后继
