第6章树与森林 Type& Get Data()const i return data: 1 GetLeft(const return leftChild; j BinTreeNode<Type>* GetRight ()const( return right Child; 3 void SetData( const Type& item )i data=item; j void SetLeft( BinTreeNode<Type>*L)(leftChild=L;) void SetRight( BinTreeNode<Type> *R )RightChild =R; j int IsEmpty (i return root==NULL? 1: 0; BinTreeNode<Type>"Parent( BinTreeNode<Type> *current f return root=NULL I root rent NULL Parent( root, current ); BinTreeNode<Type>" LeftChild( BinTreeNode<Type>*currer i return current I= NULL current-> leftChild: NULL; J BinTreeNode<Type>*RighttChild( Bin TreeNode<Type> *current i return current != NULL? current->right Child NULL int Insert( const Type& item ) BinTreeNode<Type>* Find( const Type& item ) friend istream& operator >> istream& in, Binary Tree<Type>& Tree ) 输入二叉树 friend ostream& operator<<( ostream&out, Binary Tree<Type>&Tree;输出二叉树 6-5在结点个数为n(m>1)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多少个分支结 点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点? 【解答】 结点个数为n时,高度最小的树的高度为1,有2层;它有n-1个叶结点,1个分支结点;高度最 大的树的高度为n1,有n层:它有1个叶结点,n-1个分支结点 6-6试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态 【解答】 具有3个结点的树 具有3个结点的二叉树 6-7如果一棵树有n个度为1的结点,有n个度为2的结点,…,mm个度为m的结点,试问有多少个度 为0的结点?试推导之 【解答】 总结点数n=n+n1+n2 总分支数e=n-1=n+n1+n2+…+nm-1 m*nm+(m-1)*nm-1+…+2°n2+n1 则有n=(5-m)+1第 6 章 树与森林 71 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; } void SetRight ( BinTreeNode<Type> *R ){ RightChild =R; } int IsEmpty ( ) { return root == NULL ? 1 : 0; } BinTreeNode<Type> *Parent ( BinTreeNode<Type> *current ) { return root == NULL|| root == current ? NULL : Parent ( root, current ); } BinTreeNode<Type> * LeftChild ( BinTreeNode<Type> *current ) { return current != NULL ? current->leftChild : NULL; } BinTreeNode<Type> * RighttChild ( BinTreeNode<Type> *current ) { return current != NULL? current->rightChild : NULL; } int Insert ( const Type& item ); BinTreeNode<Type> * Find ( const Type& item ); BinTreeNode<Type> * GetRoot ( ) const { return root; } friend istream& operator >> ( istream& in, BinaryTree<Type>& Tree ); //输入二叉树 friend ostream& operator << ( ostream& out, BinaryTree<Type>& Tree ); //输出二叉树 } 6-5 在结点个数为 n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结 点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】 结点个数为 n 时，高度最小的树的高度为 1，有 2 层；它有 n-1 个叶结点，1 个分支结点；高度最 大的树的高度为 n-1，有 n 层；它有 1 个叶结点，n-1 个分支结点。 6-6 试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。 【解答】 具有 3 个结点的树 具有 3 个结点的二叉树 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 则有 ( 1) 1 2 0  +      =  − = m i ni n i