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

(5) 析构函数 清除一棵用广义表表示的树

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) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 【解答】

0 1 2 3 4 5 6 7 8 9 ① ② ③ ④ ⑤ ⑥ ⑦ 10 11 12 13 14 15 16 17 18 ⑧ ⑨

① 二叉链表表示

② ∧ ③ 顺序表示

∧ ④ ∧ ⑤ ∧ ⑥ ∧

⑦ ∧ ∧ ⑧ ∧

∧ ⑨ ∧

6-4 用嵌套类写出用链表表示的二叉树的类声明。 【解答】

#include

template class BinaryTree { private:

113

template class BinTreeNode {

public: }

Type RefValue;

BinTreeNode * root;

BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode *current, const Type& item ); 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 ); } { return current != NULL ? current->leftChild : NULL; } { return current != NULL ? current->rightChild : NULL; } BinTreeNode * LeftChild ( BinTreeNode *current ) BinTreeNode * RighttChild ( BinTreeNode *current ) 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 << ( ostream& out, BinaryTree& Tree );

int Find ( BinTreeNode *current, const Type& item ) const;

BinTreeNode *leftChild, *rightChild; Type data;

6-5 在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】

结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

6-6 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】

114

115

6-7 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。 【解答】

总结点数 n = n0 + n1 + n2 + … + nm

总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1

m??n?(i?1)n?1??0i? 则有

i?2??

6-8 试分别找出满足以下条件的所有二叉树:

(1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。 【解答】 (1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。

具有3个结点的树 具有3个结点的二叉树

6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (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 ) { }

116

temp = ptr->leftChild;

ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ( ptr->leftChild ); exchange ( ptr->rightChild );

6-10 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系? 【解答】 (1) ki ( i = 0, 1, ……, h )

?i?k?2? (2) ?? ?k? (3) ( i-1)*k + m + 1

i?k?2??*k (4) ( i-1 ) % k ? 0 或 i? 时有右兄弟，右兄弟为i + 1。 ?k???(5) h = logk (n*(k-1)+1)-1 (n = 0时h = -1 )

6-11 试用判定树的方法给出在中序线索化二叉树上： 【解答】

(1) 搜索指定结点的在中序下的后继。 设指针q指示中序线索化二叉树中的指定结点，指针p指示其后继结点。

q->rightThread == 1?

≠ =

q的后继为q的右子树中q->rightChild == NULL ?

中序下的第一个结点 = ≠

q无后继 q的后继为q->rightChild

找q的右子树中在中序下的第一个结点的程序为：

p = q->rightChild;

while ( p->leftThread == 1 ) p = p->leftChild; // p即为q的后继

(2) 搜索指定结点的在前序下的后继。

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->leftChild

q的后继为q->rightChild

(3) 搜索指定结点的在后序下的后继。

( p = parent (q ) ) == NULL ? = q无后继

≠

p->rightThread == 1 || p->rightChild == q ? = ≠ q的后继为p

q的后继为p的右子树中后序下的第一个结点

117