第6章树与森林 6-2列出右图所示二叉树的叶结点、分支结点和每个结点的层次 【解答】 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为0:结点②、③的层次为1:结点④、⑤、⑥的层次 为2:结点⑦、⑧的层次为3:结点⑨的层次为 6-3使用(1)顺序表示和(2)二叉链表表示法,分别画出右图所示二叉树的存储表示。 ②③④ ⑥ a 101112131415 Al△ E△ 顺序表示 回人 叉链表表示 6-3用嵌套类写出用链表表示的二叉树的类声明 【解答】 #include <iostream. h> template <class Type> class Binary Tree i private plate <class Type> class BinTreeNode i public: BinTreeNode<Type> *leftchild, *right Child; Type RevAlue; BinTreeNode<Type>*root; BinTreeNode<Type>"Parent( BinTreeNode<Type> * start, BinTreeNode<Type>"current )i int Insert( BinTreeNode<Type> current, const Type& item ) int Find( BinTreeNode<Type> *current, const Type& item )const void destroy( BinTreeNode<Type>*current )i void Traverse( Bin TreeNode<Type> *current, ostream& out)const Binary Tree(: root(NULL)0 Binary Tree( Type value ) RefValue( value ) root( NULL Binary Tree()i destroy(root);j BinTreeNode(): leftChild( NULL ) right Child(NULL)J BinTreeNode( Type item ) data( item ) leftChild NULL ) right Child NULL)0 BinTreeNode<Type>* GetLeft (const( return leftChild; j Right const( return right Child; 3 oid SetData( const Type& item )i data=item; 3 id SetLeft( BinTreeNode<Type>"L)leftChild =L;)第 6 章 树与森林 47 6-2 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为 0；结点②、③的层次为 1；结点④、⑤、⑥的层次 为 2；结点⑦、⑧的层次为 3；结点⑨的层次为 4。 6-3 使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出右图所示二叉树的存储表示。 6-3 用嵌套类写出用链表表示的二叉树的类声明。 【解答】 #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 ) {} Type& GetData ( ) const { return data; } BinTreeNode<Type>* GetLeft ( ) const { return leftChild; } BinTreeNode<Type>* GetRight ( ) const{ return rightChild; } void SetData ( const Type& item ){ data = item; } void SetLeft ( BinTreeNode<Type> *L ) { leftChild = L; } ① ② ③ ④ ⑤ ⑥ ⑦ ⑨ ⑧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 顺序表示 二叉链表表示