第6章树与森林 ptr->nextSibling=p->nextSibling: delete(p); ∥释放结点 6-2列出右图所示二叉树的叶结点、分支结点和每个结点的层次 【解答】 二又树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。④ 结点①的层次为0:结点②、③的层次为1:结点④、⑤、⑥的层次 为2;结点⑦、⑧的层次为3:结点⑨的层次为4 6-3使用(1)顺序表示和(2)二叉链表表示法,分别画出右图所示二叉树的存储表示。 【解答】 01234 6789 ②|③ ⑤⑥⑦ 园內 囚人 顺序表示 回A 叉链表表示 6-4用嵌套类写出用链表表示的二叉树的类声明 【解答】 #include <iostream. h> template <class Type> class Binary Tree t private: template <class Type> class Bin TreeNode i BinTreeNode<Type> *leftChild, *rightChild ata: Type dat Type Revalue; BinTreeNode<Type>*root; BinTreeNode<Type>*Parent( BinTreeNode<Type>*start, BinTreeNode<Type>*current ) int Insert( BinTreeNode<Type>*current, const Type& item )i t Find( BinTreeNode<Type>*current, const Type& item )const; void destroy( BinTreeNode<Type> *current )i void Traverse( BinTreeNode<Type> *current, ostream& out)const public: Binary Tree () root( NULL) Binary Tree( Type value): RefValue( value ) root( NULL Binary Tree(i destroy(root);) BinTreeNode ( leftChild( NUlL ) right Child(NULL)0 BinTreeNode( Type item ) data( item ) left Child( NUll ) rightChild NULL)0第 6 章 树与森林 70 ptr->nextSibling = p->nextSibling; delete ( p ); //释放结点 p } } 6-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为 0；结点②、③的层次为 1；结点④、⑤、⑥的层次 为 2；结点⑦、⑧的层次为 3；结点⑨的层次为 4。 6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 【解答】 6-4 用嵌套类写出用链表表示的二叉树的类声明。 【解答】 #include <iostream.h> template <class Type> class BinaryTree { private: template <class Type> class BinTreeNode { public: BinTreeNode<Type> *leftChild, *rightChild; Type data; } Type RefValue; BinTreeNode<Type> * root; BinTreeNode<Type> *Parent ( BinTreeNode<Type> *start, BinTreeNode<Type> *current ); int Insert ( BinTreeNode<Type> *current, const Type& item ); int Find ( BinTreeNode<Type> *current, const Type& item ) const; void destroy ( BinTreeNode<Type> *current ); void Traverse ( BinTreeNode<Type> *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 ) {} ① ② ③ ④ ⑤ ⑥ ⑦ ⑨ ⑧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 顺序表示 二叉链表表示