chap6-1树与二叉树解读.ppt

* A B C D A B C D A B C D E F G 三叉链表 A B C D E F G A B C D E F G 二叉链表 证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数(度数),从而可得树中的结点数等于所有结点的度数加1。 * 证明(采用数学归纳法) 对于第一层,因为树中的第一层上只有一个结点,即整个树的根结点,而由i=1代入mi-1,得mi-1=m1-1=1,也同样得到只有一个结点,显然结论成立。 假设对于第(i-1)层(i＞1)命题成立,即度为m的树中第(i-1)层上至多有mi-2个结点,则根据树的度的定义,度为m的树中每个结点至多有m个孩子结点,所以第i层上的结点数至多为第(i-1)层上结点数的m倍,即至多为mi-2×m=mi-1个,这与命题相同,故命题成立。 * * (6) TreeDepth(T); (7) Root(T); (8) Value(T, cur_e); (9) Assign(T, cur_e, value); (10) Parent(T, cur_e); (11) LeftChild(T, cur_e); (12) RightSibling (T, cur_e); (13) InsertChild(T, p, i, c); (14) DeleteChild(T, p, i); (15) TraverseTree (T, visit()) } ADT Tree; 线性结构 树结构 第一个数据元素 根结点（只有一个） 无前驱 无双亲 最后一个数据元素 叶子结点(可以有多个) 无后继 无孩子 其它数据元素 其它结点 一个前驱,一个后继 一个双亲,多个孩子 一对一 一对多 五、树结构和线性结构的比较 数字媒体技术教研室 乐小燕 * 一、二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 每个结点最多有两个子女，分别称为左子女和右子女。 二叉树中不存在度大于2的结点。 二叉树的子树有左、右之分，子树的次序不能颠倒。 6.2 二叉树 一、二叉树的定义 二叉树是分支数最大不超过2的有根有序树。 数字媒体技术教研室 乐小燕 * 二叉树的五种不同形态 L L R R * 思考题： 高度为k的2叉树至多有多少个结点？ 此情况下树的形状是什么样的？试画出来。 k=1，2，3，4…….. * 定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 两种特殊二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 满二叉树的特点： 叶子只能出现在最下一层； 只有度为0和度为2的结点。 A 1 5 2 3 4 6 7 8 9 10 B C D E F G H I J K L M N O 11 12 13 14 15 特殊二叉树——满二叉树 不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。 满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多 A 1 5 2 3 4 6 7 B C D E F G L M 8 9 特殊二叉树——满二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 A 1 5 2 3 4 6 7 8 9 10 B C D E F G H I J K L M N O 11 12 13 14 15 A 1 5 2 3 4 6 7 8 9 10 B C D E F G H I J 特殊二叉树——完全二叉树 若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。 A 1 5 2 3 4 6 7 9 10 B C D E F G H I J K 11 L 12 M 13 N 14 O 15 8 A 1 5 2 3 4 6 7 8 9 10 B C D E F G H I J 不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点 特殊二叉树