写出用广义表表示法表示的树的类声明
6-1 写出用广义表表示法表示的树的类声明，并给出如下成员函数的实现：
(1) operator >> ( ) 接收用广义表表示的树作为输入，建立广义表的存储表示； (2) 复制构造函数 用另一棵表示为广义表的树初始化一棵树； (3) operator == ( ) 测试用广义表表示的两棵树是否相等； (4) operator
#include #define maxSubTreeNum 20; class GenTree;
class GenTreeNode { friend class GenTree; private: int utype;
//结点标志：=0, 数据; =1, 子女 //utype=0, 指向第一个子女; //utype=1或2, 指向同一层下一兄弟
union {
//联合
//utype=0, 根结点数据 //utype=1, 子女结点数据
//utype=2, 指向第一个子女的指针
//广义树结点类的声明
//最大子树(子表)个数 //GenTree类的前视声明
【解答】
GenTreeNode * nextSibling;
char RootData; char Childdata;
GenTreeNode *firstChild;
} public:
GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL)
{ if ( tp == 0 ) RootData = item; else ChildData = item; }
//构造函数：构造广义表表示的树的数据结点
GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) { }
//构造函数：构造广义表表示的树的子树结点
//返回结点的数据类型 //返回数据结点的值 //返回子树结点的地址 //返回下一个兄弟结点的地址 //将结点中的值修改为item //将结点中的子树指针修改为ptr
int nodetype ( ) { return utype; } char GetData ( ) { return data; }
GenTreeNode * GetFchild ( ) { return firstChild; }
GenTreeNode * GetNsibling ( ) { return nextSibling; } void setInfo ( char item ) { data = item; }
void setFchild ( GenTreeNode * ptr ) { firstChild = ptr; }
void setNsinbilg ( GenTreeNode * ptr ) { nextSibling = ptr; } };
class GenTree { private:
GenTreeNode *first; char retValue;
//根指针
//建树时的停止输入标志 //复制一个ptr指示的子树 //对ptr为根的子树遍历并输出
//广义树类定义
GenTreeNode *Copy ( GenTreeNode * ptr ); void Traverse ( GenListNode * ptr );
void Remove ( GenTreeNode *ptr );
//将以ptr为根的广义树结构释放 //比较以s和t为根的树是否相等
friend int Equal ( GenTreeNode *s, GenTreeNode *t ); public:
GenTree ( ); GenTree ( GenTree& t ); ~GenTree ( );
//构造函数 //复制构造函数 //析构函数
//判两棵树t1与t2是否相等 //输入 //输出
friend int operator == ( GenTree& t1, GenTree& t2 );
friend istream& operator >> ( istream& in, GenTree& t ); friend ostream& operator
(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 st (maxSubTreeNum); GenTreeNode * p, q, r; Type ch; cin >> value;
//广义树停止输入标志数据 //建立整个树的根结点 //接着应是‘(’, 进栈
//用于建表时记忆回退地址
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 ( q );
r = st.GetTop( ); st.Pop( ); r->nextSibling = p;
//建立子树, p->firstChild = q //从栈中退出前一结点 //插在前一结点r之后 //子树结点及子树根结点进栈
st.Push( p ); st.Push( q ); break;
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传送值域 //传送根结点数据 //传送子女结点数据 //递归传送子树信息
GenTree :: GenTree ( const GenTree& t ) { first = Copy ( t.first ); }
//共有函数
case 0 : q->RootData = ptr->RootData; break; case 1 : q->ChildData = ptr->ChildData; break;
case 2 : q->firstChild = Copy ( ptr->firstChild ); break; }
q->nextSibling = Copy ( ptr->nextSibling ); } return q; }
//复制同一层下一结点为头的表
(3) operator == ( ) 测试用广义表表示的两棵树是否相等
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;
//表t1与表t2都是空树, 相等 //两子树都非空且结点类型相同 //比较对应数据 //根数据结点
if ( t1 != NULL && t2 != NULL && t1->utype == t2->utype ) {
switch ( t1->utype ) {
case 0 : x = ( t1->RootData == t2->RootData ) ? 1 : 0;
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
ostream& operator
void GenTree :: traverse ( ostream& out, GenTreeNode * ptr ) { //私有函数, 广义树的遍历算法 if ( ptr != NULL ) {
if ( ptr->utype == 0 ) out RootData utype == 1 ) {
out ChildData;
if ( ptr->nextSibling != NULL ) out
}
else {
traverse ( ptr->firstChild );
if ( ptr->nextSibling != NULL ) out
traverse ( ptr->nextSibling );
} else out
GenTree :: ~ GenTree ( ) {
//用广义表表示的树的析构函数, 假定first ≠ NULL
Remove ( first ); }
void GenTree :: Remove ( GenTreeNode *ptr ) { GenTreeNode * p; while ( ptr != NULL ) {
p = ptr->nextSibling;
if ( p->utype == 2 ) Remove ( p->firstChild );
ptr->nextSibling = p->nextSibling; delete ( p );
} }
//根数据结点 //子女数据结点
//子树结点 //向子树方向搜索
//向同一层下一兄弟搜索
//在子树中删除
//释放结点p
6-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】
二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次
为2；结点⑦、⑧的层次为3；结点⑨的层次为4。
6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。
顺序表示
6-3 用嵌套类写出用链表表示的二叉树的类声明。 【解答】
#include
template class BinaryTree { private:
template class BinTreeNode {
public: }
Type RefValue;
BinTreeNode * root;
BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode *current, const Type& item );
BinTreeNode *leftChild, *rightChild; Type data;
int Find ( BinTreeNode *current, const Type& item ) const; void destroy ( BinTreeNode *current );
void Traverse ( BinTreeNode *current, ostream& out ) const; public:
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 ) { } Type& GetData ( ) const { return data; }
BinTreeNode* GetLeft ( ) const { return leftChild; } BinTreeNode* GetRight ( ) const { return rightChild; } void SetData ( const Type& item ){ data = item; } void SetLeft ( BinTreeNode *L ) { leftChild = L; }
6-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】
二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次
为2；结点⑦、⑧的层次为3；结点⑨的层次为4。
6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。
顺序表示
6-3 用嵌套类写出用链表表示的二叉树的类声明。 【解答】
#include
template class BinaryTree { private:
template class BinTreeNode {
public: }
Type RefValue;
BinTreeNode * root;
BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode *current, const Type& item );
BinTreeNode *leftChild, *rightChild; Type data;
int Find ( BinTreeNode *current, const Type& item ) const; void destroy ( BinTreeNode *current );
void Traverse ( BinTreeNode *current, ostream& out ) const; public:
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 ) { } Type& GetData ( ) const { return data; }
BinTreeNode* GetLeft ( ) const { return leftChild; } BinTreeNode* GetRight ( ) const { return rightChild; } void SetData ( const Type& item ){ data = item; } void SetLeft ( BinTreeNode *L ) { leftChild = L; }
void SetRight ( BinTreeNode *R ){ RightChild =R; } int IsEmpty ( ) { return root == NULL ? 1 : 0; }
BinTreeNode *Parent ( BinTreeNode *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 Insert ( const Type& item );
BinTreeNode * Find ( const Type& item ); BinTreeNode * GetRoot ( ) const { return root; }
friend istream& operator >> ( istream& in, BinaryTree& Tree );
//输入二叉树 //输出二叉树
friend ostream& operator & Tree ); }
6-4 在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。
6-5 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。
【解答】 总结点数 n = n0 + n1 + n2 + … + nm
6-6 试分别找出满足以下条件的所有二叉树:
(1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。 【解答】
总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1
= m*nm + (m-1)*nm-1 + … + 2*n2 + n1
m
n0(i1)ni1
i2
则有
(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
6-7 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。
(2) 以二叉树为参数，交换每个结点的左子女和右子女。 【解答】
(1) 统计二叉树中叶结点个数
int BinaryTree :: leaf ( BinTreeNode * ptr ) {
}
if ( ptr == NULL ) return 0;
else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1; 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; exchange ( ptr->leftChild ); exchange ( ptr->rightChild );
6-8 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:
(1) 各层的结点个数是多少?
(2) 编号为i的结点的父结点(若存在)的编号是多少?
(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系? (1) ki ( i = 0, 1, ……, h )
ik2(2)
k
【解答】
(3) ( i-1)*k + m + 1
ik2
(4) ( i-1 ) % k 0 或 i*k 时有右兄弟，右兄弟为i + 1。 k
(5) h = logk (n*(k-1)+1)-1 (n = 0时h = -1 )
6-9 试用判定树的方法给出在中序线索化二叉树上： 【解答】
(1) 搜索指定结点的在中序下的后继。
设指针q指示中序线索化二叉树中的指定结点，指针p指示其后继结点。
q->rightThread == 1?
≠
q的后继为q的右子树中
中序下的第一个结点
q-> ?
≠ q无后继
q的后继为q->rightChild
找q的右子树中在中序下的第一个结点的程序为：
p = q->rightChild;
while ( p->leftThread == 1 ) p = p->leftChild; // p即为q的后继
(2) 搜索指定结点的在前序下的后继。
6-10 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 【解答】
template
//建立二叉树
istream& operator >> ( istream& in, BinaryTree& t ) { int n;
cout > n; Type *A = new Type[n+1]; for ( int i = 0; i > A[i];
t. ConstructTree( T, n, 0, ptr ); delete [ ] A; return in; }
//以数组建立一棵二叉树
q的后继为q->leftChild
=
q->leftThread == 0 ?
≠
q->rightThread == 0 ?
≠
p = q;
while ( p->rightThread == 1 &&
p->rightChild != NULL ) p = p->rightChild; if ( p->rightChild ==NULL ) q无后继; else的后继为p->rightChild
q的后继为q->rightChild
(3) 搜索指定结点的在后序下的后继。
( p = parent (q ) ) == NULL ? = q无后继
≠
p-> 1 || p->rightChild == q ? = ≠ q的后继为p
q的后继为p的右子树中后序下的第一个结点
可用一段遍历程序来实现寻找p的右子树中后序下的第一个结点：即该子树第一个找到的叶结点。
找到后立即返回它的地址。
template
void BinaryTree :: ConstructTree ( Type T[ ], int n, int i, BinTreeNode *& ptr ) {
//私有函数 : 将用T[n]顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的 //以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。
if ( i >= n ) ptr = NULL; else {
ptr = new BinTreeNode ( T[i] ); ConstructTree ( T, n, 2*i+1, ptr->leftChild ); ConstructTree ( T, n, 2*i+2, ptr->rightChild ); } }
//建立根结点
6-11 请画出右图所示的树所对应的二叉树。 【解答】
对应二叉树
6-12 在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替
llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。 【解答】
llink data
森林的左子女-右兄弟表示的静态二叉链表
对应二叉树
rlink
ltag data rtag
森林的双标记表示
(1) 结构定义
template class
LchRsibNode
{ protected: Type data;
//结点数据
//结点的左子女、右兄弟指针 //左子女-右兄弟链表结点类的定义
int llink, rlink; public:
LchRsibNode ( ) : llink(NULL), rlink(NULL) { }
LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) { } }
template class DoublyTagNode { protected:
//双标记表结点类的定义
Type data;
//结点数据
//结点的左子女、右兄弟标记
int ltag, rtag; public:
DoublyTagNode ( ) : ltag(0), rtag(0) { }
DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) { } }
template class staticlinkList
//静态链表类定义
: public LchRsibNode, public DoublyTagNode { private:
LchRsibNode *V; DoublyTagNode *U; int MaxSize, CurrentSize; public:
dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) {
V = new LchRsibNode [Maxsz]; U = new DoublyTagNode [Maxsz];
//存储左子女-右兄弟链表的向量 //存储双标记表的向量
//向量中最大元素个数和当前元素个数
} }
(2) 森林的双标记先根次序表示向左子女-右兄弟链表先根次序表示的转换
void staticlinkList :: DtagF-LchRsibF ( ) { Stack st; int k;
for ( int i = 0; i
switch ( U[i].ltag ) {
case 0 : switch ( U[i].rtag ) {
case 0 : V[i].llink = V[i].rlink = -1;
if ( st.IsEmpty ( ) == 0 )
{ k = st.GetTop ( ); st.Pop ( ); V[k].rlink = i + 1; } break;
case 1 : V[i].llink = -1; V[i].rlink = i + 1; break; } break;
case 1 : switch ( U[i].rtag ) { }
case 0 : V[i].llink = i + 1; V[i].rlink = -1; break; case 1 : V[i].llink = i + 1; st.Push ( i );
}
} }
6-13二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。
52
【解答】
template
void BinaryTree :: Double_order ( BinTreeNode *current ){
if ( current != NULL ) { } }
cout data leftChild ); cout data rightChild );
6-14 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。 【解答】
当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：
6-15 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子
-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。 【解答】
因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树， 能够唯一地确定一棵树。
6-16 给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。
【解答】
(
Ⅳ
)
F：
(Ⅰ)
(Ⅱ
) ((Ⅲ)
53
此树的带权路径长度WPL = 229。
(Ⅵ)
(Ⅶ
)
6-17 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。 【解答】已知字母集 { c1, c2, c3, c4, c5, c6, c7, c8 }，频率 {5, 25, 3, 6, 10, 11, 36, 4 }，则Huffman编码为
电文总码数为 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257
6-18 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?
【解答】权值个数n = 11，扩充4 叉树的内结点的度都为4，而外结点的度都为0。设内结点个数为n4，外结点个数为n0，则可证明有关系n0 = 3 * n4 + 1。由于在本题中n0 = 11≠3 * n4 +1，需要补2个权值为0的外结点。此时内结点个数n4 = 4。
仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。
C3 C8 C1 C4
此树的带权路径长度WPL = 375 + 82 + 169 + 18 = 644。
54