|
假设在树中结点x是结点y的双亲时用(xy)来表示树边已知一棵树边的集合为{(im)(in)(ei)(be)(bd)(ab)(gj)(gk)(cg)(cf)(hl)(ch)(ac)}用树形表示法出此树并回答下列问题 ()哪个是根结点? ()哪些是叶结点? ()哪个是g的双亲? ()哪些是g的祖先? ()哪些是g的孩子? ()哪些是e的子孙? ()哪些是e的兄弟?哪些是f的兄弟? ()结点b和n的层次各是多少? ()树的深度是多少? ()以结点c为根的子树的深度是多少? () 树的度数是多少? 答 a是根结点 dmnfjkl是叶结点 c是g的双亲 ca是g的祖先 jk是g的孩子 imn是e的子孙 d是e的兄弟gh是f的兄弟 b的层次是n的层次是 树的深度是 以c为根的子树深度是 树的度数是 一棵度为的有序树与一棵二叉树有何区别? 答 一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的如果有序树中的子树只有一个孩子时这个孩子结点就无须区分其左右次序而二叉树无论其孩子数是否为均需确定其左右次序也就是说二叉树的结点次序不是相对于另一结点而言而是确定的 试分别画出具有个结点的树和个结点的二叉树的所有不同形态 答 三个结点的树如下只有两种形态 ○ ○ / \ | ○ ○ ○ | ○ 三个结点的二叉树如下所示有五种形态 () () () () () ○ ○ ○ ○ ○ / \ / / \ \ ○ ○ ○ ○ ○ ○ / \ / \ ○ ○ ○ ○ 已知一棵度为m的树中有n个度为的结点n个度为的结点nm个度为m的结点问该树中有多少片叶子? 解 设该树中的叶子数为n个该树中的总结点数为n个则有 n=n+n+n+…+nm () 又有除根结点外树中其他结点都有双亲结点且是唯一的(由树中的分支表示)所以有双亲的结点数为 n=*n+*n+*n+…+m*nm () 联立()()方程组可得 叶子数为n=+*n+*n+*n++(m)*nm 一个深度为h的满k叉树有如下性质第h层上的结点都是叶子结点其余各层上每个结点都有k棵非空子树如果按层次顺序(同层自左至右)从开始对全部结点编号问 ()各层的结点数目是多少? ()编号为i的结点的双亲结点(若存在)的编号是多少? ()编号为i的结点的第j个孩子结点(若存在)的编号是多少? ()编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? 解 () 层号为h的结点数目为kh () 编号为i的结点的双亲结点的编号是|_ (i)/k _|+(不大于(i)/k的最大整数也就是(i)与k整除的结果以下/表示整除 () 编号为i的结点的第j个孩子结点编号是k*(i)++j; () 编号为i的结点有右兄弟的条件是(i)能被k整除 右兄弟的编号是i+ 高度为h的完全二叉树至少有多少个结点?至多有多少个结点? 解 高度为h的完全二叉树至少有h个结点至多有h个结点(也就是满二叉树) 在具有n个结点的k叉树(k>=)的k叉链表表示中有多少个空指针? 解 n个结点的K叉树共有n*k个指针域已使用的指针域为n所以空指针的个数为n(k)+; 假设二叉树包含的结点数据为 ()画出两棵高度最大的二叉树 ()画出两棵完全二叉树要求每个双亲结点的值大于其孩子结点的值 解 ()高度最大的两棵二叉树如图 ○ ○ / \ ○ ○ / \ ○ ○ / \ ○ ○ / \ ○ ○ ()两棵完全二叉树如下 ○ ○ / \ / \ ○ ○ ○ ○ / \ / \ ○ ○ ○ ○ 试找出分别满足下面条件的所有二叉树 ()前序序列和中序序列相同 ()中序序列和后序序列相同 ()前序序列和后序序列相同 ()前序中序后序序列均相同 答 () 前序序列和中序序列相同的二叉树是空二叉树或没有左子树的二叉树(右单支树) () 中序序列和后序序列相同的二叉树是空二叉树或没有右子树的二叉树(左单支树) () 前序序列和后序序列相同的二叉树是空二叉树或只有根的二叉树 () 前序中序后序序列均相同的二叉树空树或只有根结点的二叉树 试采用顺序存储方法和链接存储方法分别画也所示各二叉树的存储结构 解 ()顺序存储方法 二叉树(a): 下标 __________________________________________________________________ bt | | | |∮|∮| |∮|∮|∮|∮| |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| | __________________________________________________________________ 二叉树(b): 下标 __________________________________________________________________________________ bt| | |∮| |∮|∮| |∮|∮|∮|∮|∮|∮| |∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮| | __________________________________________________________________________________ 二叉树(c): 下标 ______________________________________________________________________ |
