6-5在结点个数为n(m>1)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多少个分支结 点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点? 【解答】结点个数为n时,高度最小的树的高度为1,有2层;它有n1个叶结点,1个分支结点;高度 最大的树的高度为n1,有n层;它有1个叶结点,n1个分支结点 6-7如果一棵树有m个度为1的结点,有m2个度为2的结点,…,m个度为m的结点,试问有多少个度 为0的结点?试推导之。 【解答】总结点数n=m+n+n+…+mm 总分支数e=m1=m+n1+n2+…+nm-1 测有m) 6-8试分别找出满足以下条件的所有二叉树 (1)二叉树的前序序列与中序序列相同 (2)二叉树的中序序列与后序序列相同 (3)二叉树的前序序列与后序序列相同 【解答】 (1)二叉树的前序序列与中序序列相同:空树或缺左子树的单支树 (2)二叉树的中序序列与后序序列相同:空树或缺右子树的单支树 (3)二叉树的前序序列与后序序列相同:空树或只有根结点的二叉树 6-9若用二叉链表作为二叉树的存储表示,试针对以下问题编写递归算法: (1)统计二叉树中叶结点的个数 (2)以二叉树为参数,交换每个结点的左子女和右子女。 【解答】 (1)统计二叉树中叶结点个数 int BinaryTree<Type>: leaf( BinTreeNode<Type>*ptr)t if(ptr== NULL)return 0; nid==NULL) else return leaf( ptr->lefiChild)+leaf(ptr- Child (2)交换每个结点的左子女和右子女 void BinaryTree<Type>: exchange( BinTreeNode<Type>*ptr)i BinTreeNode<Type>x’my; if(pir->lefiChild 1= NULL II ptr->righ Child I=NULL)( ptr->lefiChild= ptr->right Child exchange(ptr->lefichild ) exchange( ptr->righI Child);} 6-5 在结点个数为 n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结 点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】结点个数为 n 时，高度最小的树的高度为 1，有 2 层；它有 n-1 个叶结点，1 个分支结点；高度 最大的树的高度为 n-1，有 n 层；它有 1 个叶结点，n-1 个分支结点。 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 6-8 试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。 【解答】 (1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 6-9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。 (2) 以二叉树为参数，交换每个结点的左子女和右子女。 【解答】 (1) 统计二叉树中叶结点个数 int BinaryTree<Type> :: leaf ( BinTreeNode<Type> * 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<Type> :: exchange ( BinTreeNode<Type> * ptr ) { BinTreeNode<Type> * temp; if ( ptr->leftChild != NULL || ptr->rightChild != NULL ) { temp = ptr->leftChild; ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ( ptr->leftChild ); exchange ( ptr->rightChild );