树和二叉树-数据结构讲义.ppt

一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A．2h B．2h-1 C．2h+1 D．h+1 【南京理工大学2001】 41．对于前序遍历与中序遍历结果相同的二叉树为（）;对于前序遍历和后序遍历结果相同的二叉树为（）。【中科院计算所】 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树 下列是先序遍历二叉树的非递归子程序，请阅读子程序，填充空格，使其成为完整的算法。 【同济大学 2001】 void example(bTree *b) { bTree *stack[20], *p； int top; if (b!=null) { top=1; stack[top]=b; while (top0) { p=stack[top]; top--; printf(“%d”,p-data); if (p-rChild!=null) {(1)___; (2)___;} if (p-lChild!=null) {(3)___; (4)__; } } } } 以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(biTree bt) /*bt为根结点的指针*/ { int hl, hr; if (bt == NULL) return((1)___); hl=depth(bt-lchild); hr=depth(bt-rchild); if((2)___) (3)_____； return(hr+1); } 【西南交通大学 2000 】 设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列：ABDFCEGH 中序遍历序列：BFDAGEHC （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学 1997】 将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）NPGHJMOLIKEDFBAC【南京航空航天大学 1998】 B A C E D F P G H J M O L I K N 算法设计与上机实习： 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 （2）不改变结点结构，仅在作为线索的地址前加一个负号，即： 负的地址表示线索 正的地址表示指针 第四节  树和森林 树的存储结构 双亲表示法 孩子表示法 孩子兄弟表示法 双亲表示法 用一组连续的空间存放结点，每个结点用一个域表示该结点的双亲。 1 2 3 4 5 6 5 3 1 0 2 1 3 1 4 1 6 3 双亲表示法 孩子表示法 多叉链表表示法 多重线性链表表示法 多叉链表表示法：每个结点有多个指针域 1 2 3 4 5 6 多叉链表表示法 data L1 L2 ............. Ln 结点: 1 2 ^ ^ ^ 3 ^ 4 ^ ^ ^ 5 ^ ^ ^ 6 ^ ^ ^ 多重线性链表表示法 把每个结点的孩子组成一个线性链表 1 2 3 4 5 6 多重线性链表表示法 结点: 2 1 2^ 3 4^ 5^ 6^ 3 4 ^ 5 6 ^ data L 孩子兄弟表示法 用二叉树的左指针指向该结点的第一个孩子，右指针指向该结点的下一个兄弟 结点: 1 2 3 4 5 6 孩子兄弟表示法 child data brother ^ 2 1 ^ 3 ^ 5 ^ 4 ^ ^ 6 ^ 森林与二叉树的转换 森林与二叉树的对应关系 森林转化成二叉树的规则 ? 若F为空，即n = 0，则 对应的二叉树B为空二叉树。 ? 若F不空，则 对应二叉树B的根root (B)是F中第一棵树T1的根root (T1)；