第6章 树与森林
一、复习要点
本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。特别是二叉树的遍历算法，它们与许多以此为基础的递归算法都必须认真学习。因为树的先根遍历次序与对应二叉树表示的前序遍历次序一致，树的后根遍历次序与对应二叉树的中序遍历次序一致，因此可以据此得出树的遍历算法。线索化二叉树是直接利用二叉链表的空链指针记入前驱和后继线索，从而简化二叉树的遍历。堆是一种二叉树的应用，可以用它作为优先级队列的实现。它的存储表示是完全二叉树的顺序存储方式，它的定义不要求堆中的数据有序，但要求双亲结点与子女结点必须满足某种关系。本章最后讨论霍夫曼树。这种树是扩充二叉树，要求在外结点上带有权值，在构造霍夫曼树时必须注意一个新结点的左子女上所带的权值小于右子女上所带的权值，这不是霍夫曼树必须这样，而是实现算法造成这种结果。此外，作为霍夫曼树的应用，引入霍夫曼编码。通常让霍夫曼树的左分支代表编码“0”，右分支代表编码“1”，得到霍夫曼编码。这是一种不等长编码，可以有效地实现数据压缩。
本章复习的要点是： 1、基本知识点
要求理解树和森林的定义，树的抽象数据类型，二叉树的定义，二叉树的性质，二叉树的抽象数据类型，二叉树的数组表示和链表存储表示。要求掌握二叉树的遍历，包括中序遍历、前序遍历、后序遍历方法，要求理解二叉树的计数方法及从二叉树遍历结果得到二叉树的方法。对于线索化二叉树，要求理解什么是线索，中序线索化二叉树的结构特性及寻找某结点的前驱和后继的方法。此外，需要理解堆的定义及其实现的方法，本章只考虑用完全二叉树的顺序存储来实现。还需要理解堆的建立，插入与删除过程。要求掌握树/森林与二叉树的转换，树的遍历方法。最后要求掌握霍夫曼树的实现方法及霍夫曼编码的概念。
2、算法设计
? 建立二叉树的递归算法。
? 前序、中序、后序遍历二叉树的递归算法。 ? 使用栈的前序、中序、后序遍历的非递归算法。
? 统计二叉树结点个数，二叉树叶结点个数，二叉树高度的递归算法。 ? 自左向右链接二叉树叶结点的递归算法。
? 判断两棵二叉树相等和交换二叉树左、右子女指针的递归算法。
? 通过二叉树的遍历建立前序线索化二叉树和中序线索化二叉树的算法。 ? 中序线索化二叉树上的中序遍历算法。 ? 前序线索化二叉树上的前序遍历算法。 ? 后序线索化二叉树上的后序遍历算法。 ? 利用堆实现优先级队列的操作。
? 堆的自上向下和自下向上的调整算法。 ? 堆的插入与删除算法。
? 树的先根、后根、层次遍历算法（基于树的二叉树表示）。
二、难点与重点
108
1、树：树的定义、树的基本运算
? 树的分层定义是递归的 ? 树中结点个数与高度的关系
2、二叉树：二叉树定义、二叉树的基本运算
? 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数 ? 完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置 ? 二叉树的前序·中序·后序遍历的递归算法和使用栈的非递归算法 ? 二叉树的层次遍历算法
? 中序线索化二叉树、前驱与后继的查找方法、建立中序线索化二叉树的算法 3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
? 霍夫曼树是带权路径长度最小的扩充二叉树
? 构造霍夫曼树时，按构造算法，每次具最小关键码的子树是根的左子树，具次小关键码的子树是根的右子树
? 在构造过程中，新二叉树按根的权值加入到森林的最后 4、树与森林
? 树的广义表表示、树的双亲表示、树的左子女-右兄弟表示 ? 树、森林与二叉树的对应关系 ? 树的先根·后根·层次遍历算法 5、堆：堆的定义、堆的插入与删除算法
? 形成堆时用到的向下调整算法
? 形成堆时的调整过程及比较次数的上界估计 ? 堆插入时用到的向上调整算法
三、教材中习题的解析
6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现： (1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示； (2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树； (3) operator == ( ) 测试用广义表表示的两棵树是否相等； (4) operator << ( ) 用广义表的形式输出一棵树； (5) 析构函数 清除一棵用广义表表示的树。 【解答】
#include
class GenTreeNode { friend class GenTree; private: int utype;
//结点标志：=0, 数据; =1, 子女 //utype=0, 指向第一个子女; //utype=1或2, 指向同一层下一兄弟 //联合
//utype=0, 根结点数据
GenTreeNode * nextSibling; union {
//广义树结点类的声明
//最大子树(子表)个数 //GenTree类的前视声明
char RootData;
109
char Childdata;
//utype=1, 子女结点数据 //utype=2, 指向第一个子女的指针
GenTreeNode *firstChild;
} public:
GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL)
{ if ( tp == 0 ) RootData = item; else ChildData = item; }
//构造函数：构造广义表表示的树的数据结点 //构造函数：构造广义表表示的树的子树结点
//返回结点的数据类型 //返回数据结点的值 //返回子树结点的地址
//返回下一个兄弟结点的地址 //将结点中的子树指针修改为ptr //将结点中的值修改为item
GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) { }
int nodetype ( ) { return utype; } char GetData ( ) { return data; }
GenTreeNode * GetFchild ( ) { return firstChild; }
GenTreeNode * GetNsibling ( ) { return nextSibling; } void setInfo ( char item ) { data = item; }
class GenTree { private:
GenTreeNode *first; char retValue;
void setFchild ( GenTreeNode * ptr ) { firstChild = ptr; } };
void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr; }
//广义树类定义 //根指针
//建树时的停止输入标志 //复制一个ptr指示的子树 //对ptr为根的子树遍历并输出 //将以ptr为根的广义树结构释放
//比较以s和t为根的树是否相等
GenTreeNode *Copy ( GenTreeNode * ptr ); void Traverse ( GenListNode * ptr ); void Remove ( GenTreeNode *ptr ); public:
GenTree ( ); GenTree ( GenTree& t ); ~GenTree ( );
friend int Equal ( GenTreeNode *s, GenTreeNode *t );
//构造函数 //复制构造函数 //析构函数
//判两棵树t1与t2是否相等
//输入 //输出
friend int operator == ( GenTree& t1, GenTree& t2 );
friend istream& operator >> ( istream& in, GenTree& t ); friend ostream& operator << ( ostream& out, GenTree& t ); }
(1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示
istream& operator >> ( istream& in, GenTree& t ) {
//友元函数, 从输入流对象in接受用广义表表示的树，建立广义表的存储表示t。
t.ConstructTree ( in, retValue ); return in; }
void GenTree :: ConstructTree ( istream& in, char& value ) {
//从输入流对象in接受用广义表表示的非空树，建立广义表的存储表示t。 Stack
110
//用于建表时记忆回退地址
cin >> value;
//广义树停止输入标志数据 //建立整个树的根结点 //接着应是?(?, 进栈 //逐个结点加入
//建立子树, p->firstChild = q //从栈中退出前一结点 //插在前一结点r之后 //子树结点及子树根结点进栈 //子树建成, 封闭链, 退到上层 //栈不空, 取上层链子树结点 //栈空, 无上层链, 算法结束
cin >> ch; first = q = new GenTreeNode ( 0, ch ); cin >> ch; if ( ch == ?(? ) st.Push ( q ); cin >> ch;
while ( ch != value ) {
switch ( ch ) {
case ?(? : p = new GenTreeNode
r = st.GetTop( ); st.Pop( ); r->nextSibling = p; break;
st.Push( p ); st.Push( q );
case ?)? : q->nextSibling = NULL; st.pop( );
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) 复制构造函数 用另一棵表示为广义表的树初始化一棵树；
GenTreeNode* 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 = ptr->ChildData; break; }
q->nextSibling = Copy ( ptr->nextSibling ); } return q; }
//复制同一层下一结点为头的表
GenTree :: GenTree ( const GenTree& t ) { first = Copy ( t.first ); }
//共有函数
case 2 : q->firstChild = Copy ( ptr->firstChild ); break;
(3) operator == ( ) 测试用广义表表示的两棵树是否相等
111
int operator == ( GenTree& t1, GenTree& t2 ) {
//友元函数 : 判两棵树t1与t2是否相等, 若两表完全相等, 函数返回1, 否则返回0。 return Equal ( t1.first, t2.first ); }
int Equal ( GenTreeNode *t1, GenTreeNode *t2 ) { //是GenTreeNode的友元函数 int x;
if ( t1 == NULL && t2 == NULL ) return 1;
switch ( t1->utype ) {
//表t1与表t2都是空树, 相等 //比较对应数据 //根数据结点 //子女数据结点 //递归比较其子树
if ( t1 != NULL && t2 != NULL && t1->utype == t2->utype ) { //两子树都非空且结点类型相同
}
case 0 : x = ( t1->RootData == t2->RootData ) ? 1 : 0; }
if ( x ) return Equal ( t1->nextSibling, t2->nextSibling );
break; break;
case 1 : x = ( t1->ChildData == t2->ChildData ) ? 1 : 0; case 2 : x = Equal ( t1->firstChild, t2->firstChild );
//相等, 递归比较同一层的下一个结点; 不等, 不再递归比较
return 0; }
(4) operator << ( ) 用广义表的形式输出一棵树
ostream& operator << ( ostream& out, GenTree& t ) { //友元函数, 将树t输出到输出流对象out。 t.traverse ( out, t.first ); return out; }
void GenTree :: traverse ( ostream& out, GenTreeNode * ptr ) { //私有函数, 广义树的遍历算法 if ( ptr != NULL ) {
if ( ptr->utype == 0 ) out << ptr->RootData << ?(?; else if ( ptr->utype == 1 ) {
out << ptr->ChildData;
if ( ptr->nextSibling != NULL ) out << ?,?; }
//子树结点 //向子树方向搜索
traverse ( ptr->firstChild ); }
traverse ( ptr->nextSibling ); }
else out << ?)?; }
112
//向同一层下一兄弟搜索
//根数据结点 //子女数据结点
else {
if ( ptr->nextSibling != NULL ) out << ?,?;