第6章树与森林 6-8试分别找出满足以下条件的所有二叉树 (1)二叉树的前序序列与中序序列相同; (2)二叉树的中序序列与后序序列相同 (3)二叉树的前序序列与后序序列相同 【解答】 (1)二叉树的前序序列与中序序列相同:空树或缺左子树的单支树; (2)二叉树的中序序列与后序序列相同:空树或缺右子树的单支树 (3)二叉树的前序序列与后序序列相同:空树或只有根结点的二叉树 6-9若用二叉链表作为二叉树的存储表示,试针对以下问题编写递归算法: (1)统计二叉树中叶结点的个数 (2)以二叉树为参数,交换每个结点的左子女和右子女 【解答】 (1)统计二叉树中叶结点个数 int Binary Tree<Type> : leaf BinTreeNode<Type>*ptr)t 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 Binary Tree<Type>: exchange( BinTreeNode<Type>*ptr)i BinTreeNode<Type> *temp if( ptr->leftChild NULL II ptr->rightChild!=NULL ) temp= ptr->leftChild: ptr->left Child= ptr->rightChild: change( 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)k(i=0,1,……,h) k第 6 章 树与森林 72 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 ); } } 6-10 一棵高度为 h 的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结点都有 k 棵 非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在)的编号是多少? (3) 编号为 i 的结点的第 m 个孩子结点(若存在)的编号是多少? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度 h 是 n 的什么函数关系? 【解答】 (1) k i ( i = 0, 1, ……, h ) (2)       + − k i k 2