习题五和上机答案VIP免费

习题五5.1已知一棵树边的集合为(I,M),(I,N),(E,I),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(TABLE,L),(C,TABLE),(A,C)，画出这棵树，并回答下列问题：⑴哪个是根结点？⑵哪些是叶子结点？⑶哪个是结点Ｇ的双亲？⑷哪些是结点Ｇ的祖先？⑸哪些是结点Ｇ的孩子？⑹哪些是结点Ｅ的子孙？⑺哪些是结点Ｅ的兄弟？哪些是结点Ｆ的兄弟？⑻结点Ｂ和Ｎ的层次号分别是什么？⑼树的深度是多少？⑽以结点Ｃ为根的子树的深度是多少？解：依题意，树的表示如图8.23所示。（1）根结点是：a（2）叶子结点是：d，m，n，f，j，k，l（3）g的双亲是：c（4）g的祖先是：a，c（5）g的孩子是：j，k（6）e的子孙是：i，m，n（7）e的兄弟是d，f的兄弟是g，h（8）b的层次是2，n的层次是5（9）树的深度是5（10）以结点c为根的子树的深度是3（11）树的度数是35.2一棵度为2的树与一棵二叉树有何区别？解：二叉树的度也可以为1。5.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。解：二叉树：5.4一棵深度为N的满Ｋ叉树有如下性质：第N层上的结点都是叶子结点，其余各层上每个结点都有Ｋ棵非空子树。如果按层次顺序从１开始对全部结点编号，问⑴各层的结点数目是多少？⑵编号为n的结点的父结点（若存在）的编号是多少？⑶编号为n的结点的第i个儿子（若存在）的编号是多少？⑷编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？解：（1）第i层的结点数为ki-1。（2）编号为n的结点的双亲点为：「(n-2)/k」+1。（3）编号为n的结点的第i个孩子结点为：(n-1)*k+i+1。（4）编号为n的结点有右兄弟的条件是(n-1)%k≠0，其右兄弟的编号是n+1。5.5已知一棵度为m的树中有n1个度为１的结点，n2个度为２的结点，．．．，nm个度为m的结点，问该树中有多少个叶子结点？解：依题意：设n为总的结点个数，n0为叶子结点（即度为0的结点）的个数，则有：n=n+n+n+...+n①又有：n-1=度的总数，即：n-1=n*1+n*2+...+n*m②①-②式得：1=n-n-2n-...-(m-1)n则有：n=1+n+2n+...+(m-1)n=1+5.6试列出下列二叉树的终端结点、非终端结点以及每个结点的层次题5.6解：终端结点：E、G、H非终端结点：A、B、C、D、F结点ABCDEFGH层次122333445.7对于5.6题中给出的二叉树，分别列出先根次序、中根次序、后根次序的结点序列。解：先根次序：ABDGCEFH中根次序：DGBAECHF后根次序：GDBEHFCA5.8在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占４个字节的存储空间，每个信息占Ｋ个字节的存储空间。试问对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比二叉链表更节省空间？解：（K+4）*n<(m+1)*45.9假定用两个一维数组L(1:n)和R(1:n)作为有n个结点的二叉树的存储结构，L(i)和R(i)分别指示结点i的左孩子和右孩子，0表示空。⑴试写一个算法判别结点u是否为结点v的子孙；⑵先由L和R建立一维数组T(1:n)，使T中第i(i=1,2,...,n)个分量指示结点i的双亲，然后写判别结点u是否为结点v的子孙的算法。解：（1）、intIs_Descendant_C(intu,intv)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0{if(u==v)return1;else{if(L[v])if(Is_Descendant(u,L[v]))return1;if(R[v])if(Is_Descendant(u,R[v]))return1;//这是个递归算法}return0;}//Is_Descendant_C（2）、intIs_Descendant_P(intu,intv)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0{for(p=u;p!=v&&p;p=T[p]);if(p==v)return1;elsereturn0;}//Is_Descendant_P5.10假设n和m为二叉树中的两结点，用“１”、“０”“Φ”（分别表示肯定、恰恰相反和不一定）填写下表：前序遍历时中序遍历时后序遍历时已知n在m前？n在m前？n在m前？n在m的左方111n在m的右方000n是m的祖先1Φ0n是m的子孙0Φ1注：⑴如果离a和b最近的共同祖先p存在，且⑵a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。5.11假设以二叉链表作存储结构，试分别写出前序和后序遍历的非递归算法,可直接利用栈的基本运算。解：前序遍历：依题意，使用一个栈stack实现非递归的前序遍历。voidpreorde...