6-10一棵高度为h的满k叉树有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有k棵 非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进行编号,试问 (1)各层的结点个数是多少? (2)编号为i的结点的父结点(若存在)的编号是多少? (3)编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4)编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少? 【解答】 (1)k(i=0,1,……,h) i+k-2 k (3)(-1)*k+m+1 (4)(-1)modk≠0或i≤ i+k-2 hk时有右兄弟,右兄弟为/+1 6-11试用判定树的方法给出在中序线索化二叉树上 【解答】 (1)搜索指定结点的在中序下的后继。 设指针q指示中序线索化二叉树中的指定结点,指针p指示其后继结点 g->righThread=1? g->righiChild== NULL? q的后继为q的右子树中 中序下的第一个结点 q无后继 q的后继为q-> righIChild 找q的右子树中在中序下的第一个结点的程序为: while(p-> leftThread a=1)p=p-> lefiChild;∥p即为q的后继 (2)搜索指定结点的在前序下的后继 g->leftThread ==0? q的后继为q-> lefichild q的后继为q-> righIChild P= while(p->right Thread== 1&& p->righ/ Child != NULl)P=p->righIChild; if(p-> rightchild==NLL)q无后继; (3)搜索指定结点的在后序下的后继 q无后继 p->rightThread== I >rightchild q的后继为p q的后继为p的右子树中后序下的第一个结点} } 6-10 一棵高度为 h 的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结点都有 k 棵 非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在)的编号是多少? (3) 编号为 i 的结点的第 m 个孩子结点(若存在)的编号是多少? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? 【解答】 (1) k i ( i = 0, 1, ……, h ) (2) i k k  + −      2 (3) ( i-1)*k + m + 1 (4) ( i-1 ) mod k  0 或 i   + −      i k k k 2 * 时有右兄弟，右兄弟为 i + 1。 6-11 试用判定树的方法给出在中序线索化二叉树上： 【解答】 (1) 搜索指定结点的在中序下的后继。 设指针 q 指示中序线索化二叉树中的指定结点，指针 p 指示其后继结点。 找 q 的右子树中在中序下的第一个结点的程序为： p = q->rightChild; while ( p->leftThread == 1 ) p = p->leftChild; // p 即为 q 的后继 (2) 搜索指定结点的在前序下的后继。 (3) 搜索指定结点的在后序下的后继。 q->rightThread == 1? = ≠ q->rightChild == NULL ? = q 无后继 ≠ q 的后继为 q->rightChild q 的后继为 q 的右子树中 中序下的第一个结点 q->leftThread == 0 ? = q的后继为 q->leftChild ≠ q->rightThread == 0 ? = q 的后继为 q->rightChild ≠ p = q; while ( p->rightThread == 1 && p->rightChild != NULL ) p = p->rightChild; if ( p->rightChild ==NULL ) q 无后继; else 的后继为 p->rightChild ( p = parent (q ) ) == NULL ? = q 的后继为 p ≠ p->rightThread == 1 || p->rightChild == q ?= ≠ q 的后继为 p 的右子树中后序下的第一个结点 q 无后继