数据结构习题解析第6章(3)

可用一段遍历程序来实现寻找p的右子树中后序下的第一个结点：即该子树第一个找到的叶结点。找到后立即返回它的地址。

6-12 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 【解答】

template int n;

cout << \ : \; in >> n; Type *A = new Type[n+1]; for ( int i = 0; i < n; i++ ) in >> A[i];

t. ConstructTree( T, n, 0, ptr ); delete [ ] A; return in; }

//以数组建立一棵二叉树

//建立二叉树

istream& operator >> ( istream& in, BinaryTree& t ) {

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-13 试编写一个算法，把一个新结点l作为结点s的左子女插入到一棵中序线索化二叉树中，s原来的左子女变成l的左子女。 【解答】

template

void ThreadTree :: leftInsert ( ThreadNode *s, ThreadNode * l ) { if ( s != NULL && l != NULL ) { } }

118

l->leftChild = s->leftChild; l->leftThread = s->leftThread; l->rightChild = s; l->rightThread = 1; s->leftChild = l; s->leftThread = 0; if ( l->leftThread == 0 ) {

//预先链接

//新插入结点*l的后继为*s //*l成为*s的左子女 //*l的左子女存在

//找*l的左子树中序下最后一个结点

ThreadNode * p = l->leftChild; while ( p->rightThread == 0 )

p = p->rightChild; p->rightChild = l; }

//该结点的后继为*l

6-14 写出向堆中加入数据4, 2, 5, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。 【解答】 以最小堆为例： 2 4 4 2 2 2

2 4 4 4 4 5 5 5

8 8 3

2 2 2 2

3 5 3 5 3 5 3 5

8 4 8 4 6 8 4 6 10 8 4 6 10

14

6-16 请画出右图所示的树所对应的二叉树。 【解答】

1 1

2 2 对应二叉树 3

4 3 4 5 5 6 7 6 8 8 7

6-17 在森林的二叉树表示中，用llink存储指向结点第一个子女的指针，用rlink存储指向结点下一个兄弟的指针，用data存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag代替llink，用rtag代替rlink。并设定若ltag = 0，则该结点没有子女，若ltag ? 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag ? 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink表示的森林。 【解答】 A A F H B F 对应二叉树 C G H B C D G I J

D I E K E K J 0 1 2 3 4 5 6 7 8 9 10

llink

1 -1 -1 4 -1 6 -1 8 9 -1 -1 data

A B C D E F G H I K J 森林的左子女-右兄弟表

rlink 5 2 3 -1 -1 7 -1 -1 10 -1 -1 示的静态二叉链表

119

0 1 2 3 4 5 6 7 8 9 10

ltag 1 0 0 1 0 1 0 1 1 0 0 data A B C D E F G H I K J rtag 森林的双标记表示 1 1 1 0 0 1 0 0 1 0 0

(1) 结构定义

template class LchRsibNode { protected: Type data; public:

LchRsibNode ( ) : llink(-1), rlink(-1) { }

LchRsibNode ( Type x ) : llink(-1), rlink(-1), data(x) { } }

template class DoublyTagNode { protected: Type data; public:

DoublyTagNode ( ) : ltag(0), rtag(0) { }

DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) { } }

template class staticlinkList private:

LchRsibNode *V; int MaxSize, CurrentSize; public:

dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) {

V = new LchRsibNode [Maxsz]; U = new DoublyTagNode [Maxsz];

//存储左子女-右兄弟链表的向量 //存储双标记表的向量

//向量中最大元素个数和当前元素个数

DoublyTagNode *U;

//静态链表类定义

: public LchRsibNode, public DoublyTagNode {

//结点数据

//结点的左子女、右兄弟标记

int ltag, rtag;

//双标记表结点类的定义

//结点数据

//结点的左子女、右兄弟指针

int llink, rlink;

//左子女-右兄弟链表结点类的定义

}

(2) 森林的双标记先根次序表示向左子女-右兄弟链表先根次序表示的转换

void staticlinkList :: DtagF-LchRsibF ( ) { Stack st; int k;

for ( int i = 0; i < CurrentSize; 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;

120

} }

}

case 1 : V[i].llink = -1; V[i].rlink = i + 1; break; } break;

case 0 : V[i].llink = i + 1; V[i].rlink = -1; break; case 1 : V[i].llink = i + 1; st.Push ( i );

case 1 : switch ( U[i].rtag ) {

}

6-18 二叉树的双序遍历(Double-order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。 【解答】

template

if ( current != NULL ) { } }

cout << current->data << ' '; Double_order ( current->leftChild ); cout << current->data << ' '; Double_order ( current->rightChild );

void BinaryTree :: Double_order ( BinTreeNode *current ){

6-19 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。 【解答】

当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示： A A A A EBCD

FHIGJ E B CD F HIGJ E B C D F G HI J E B C D F G H I J

6-20 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。 【解答】

因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根次序遍历结果和后根次序遍历结果能够唯一地确定一棵树。 例如，对于题6-16所示的树

121

1 1 2 2 对应二叉树 3 3 4 5 4

5

6 7 6

8 8 7

对应二叉树的前序序列为1, 2, 3, 4, 5, 6, 8, 7；中序序列为3, 4, 8, 6, 7, 5, 2, 1。 原树的先根遍历序列为 1, 2, 3, 4, 5, 6, 8, 7；后根遍历序列为3, 4, 8, 6, 7, 5, 2, 1。

6-21 给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外部路径长度。 【解答】

F： 15 03 14 02 06 09 16 17 (Ⅰ) 15 14 06 09 16 17 05

02 03 (Ⅱ

) 15 14 09 16 17 11 (Ⅲ) 15 14 16 17 20

05 06 09 11 02 03

05 06 (Ⅳ ) 16 17 20 29 (Ⅴ) 20 29 33 02 03

09 11 14 15 09 11 14 15 16 17

05 06 05 06 02 03 02 03

82 (Ⅵ)

33 49 (Ⅶ) 33 49 16 17 20 29 16 17 20 29 09 11 14 15

09 11 14 15

05 06 05 06 02 03 02 03 此树的带权路径长度WPL = 229。

6-22 假定用于通信的电文仅由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编码为 c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001

122