线性数学试题解答6

线性数学试题解答6内容摘要：

inaryTree ( Type value ) : RefValue ( value ), root ( NULL ){ } ~BinaryTree ( ) { destroy (root)。 } BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) { } BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) { } Typeamp。 GetData ( ) const { return data。 } BinTreeNodeType* GetLeft ( ) const { return leftChild。 } BinTreeNodeType* GetRight ( ) const { return rightChild。 } void SetData ( const Typeamp。 item ){ data = item。 } void SetLeft ( BinTreeNodeType *L ) { leftChild = L。 } void SetRight ( BinTreeNodeType *R ){ RightChild =R。 } int IsEmpty ( ) { return root == NULL ? 1 : 0。 } BinTreeNodeType *Parent ( BinTreeNodeType *current ) { return root == NULL || root == current ? NULL : Parent ( root, current )。 } BinTreeNodeType * LeftChild ( BinTreeNodeType *current ) { return current != NULL ? currentleftChild : NULL。 } BinTreeNodeType * RighttChild ( BinTreeNodeType *current ) { return current != NULL ? currentrightChild : NULL。 } int Insert ( const Typeamp。 item )。 BinTreeNodeType * Find ( const Typeamp。 item )。 BinTreeNodeType * GetRoot ( ) const { return root。 } friend istreamamp。 operator ( istreamamp。 in, BinaryTreeTypeamp。 Tree )。 //输入二叉树 friend ostreamamp。 operator ( ostreamamp。 out, BinaryTreeTypeamp。 Tree )。 //输出二叉树 } 65 在结点个数为 n (n1)的各棵树中，高度最小的树的高度是多少。 它有多少个叶结点。 多少个分支结点。 高度最大的树的高度是多少。 它有多少个叶结点。 多少个分支结点。 【解答】结点个数为 n 时，高度最小的树的高度为 1，有 2 层；它有 n1个叶结点， 1个分支结点；高度最大的树的高度为 n1，有 n 层；它有 1 个叶结点， n1 个分支结点。 67 如果一棵树有 n1 个度为 1的结点 , 有 n2 个度为 2 的结点 , … , nm 个度为 m 的结点 , 试问有多少个度为 0 的结点 ? 试推导之。 【解答】 总结点数 n = n0 + n1 + n2 + … + nm 总分支数 e = n1 = n0 + n1 + n2 + … + nm1 = m*nm + (m1)*nm1 + … + 2*n2 + n1 则有 1)1(20   mi inin 68 试分别找出满足以下条件的所有二叉树 : (1) 二叉树的前序序列与中序序列相同。 (2) 二叉树的中序序列与后序序列相同。 (3) 二叉树的前序序列与后序序列相同。 【解答】 (1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 69 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。 (2) 以二叉树为参数，交换每个结点的左子女和右子女。 【解答】 (1) 统计二叉树中叶结点个数 int BinaryTreeType :: leaf ( BinTreeNodeType * ptr ) { if ( ptr == NULL ) return 0。 else if ( ptrleftChild == NULL amp。 amp。 ptrrightChild == NULL ) return 1。 else return leaf ( ptrleftChild ) + leaf ( ptrrightChild )。 } (2) 交换每个结点的左子女和右子女 void BinaryTreeType :: exchange ( BinTreeNodeType * ptr ) { BinTreeNodeType * temp。 if ( ptrleftChild != NULL || ptrrightChild != NULL ) { temp = ptrleftChild。 ptrleftChild = ptrrightChild。 ptrrightChild = temp。 exchange ( ptrleftChild )。 exchange ( ptrrightChild )。 } } 610 一棵高度为 h 的满 k 叉树有如下性质 : 第 h 层上的结点都是叶结点 , 其余各层上每个结点都有 k 棵非空子树 , 如果按层次自顶向下 , 同一层自左向右 , 顺序从 1 开始对全部结点进行编号 , 试问 : (1) 各层的结点个数是多少 ? (2) 编号为 i 的结点的父结点 (若存在 )的编号是多少 ? (3) 编号为 i 的结点的第 m 个孩子结点 (若存在 )的编号是多少 ? (4) 编号为 i 的结点有右兄弟的条件是什么 ? 其右兄弟结点的编号是多少 ? 【解答】 (1) ki ( i = 0, 1, …… , h ) (2) i kk  2 (3) ( i1)*k + m + 1 (4) ( i1 ) mod k  0 或 i    i kk k2 *时有右兄弟，右兄弟为 i + 1。 611 试用判定树的方法给出在中序线索化二叉树上： 【解答】 (1) 搜索指定结点的在中序下的后继。 设指针 q 指示中序线索化二叉树中的指定结点，指针 p 指示其后继结点。 找 q 的右子树中在中序下的第一个结点的程序为： p = qrightChild。 while ( pleftThread == 1 ) p = pleftChild。 // p 即为 q 的后继 (2) 搜索指定结点的在前序下的后继。