第4单元非线性数据结构树、二叉树主讲：刘志强

第4单元非线性数据结构树、二叉树主讲：刘志强内容摘要：

普通树 二叉树 （ a） （ b） （ c） （ d） （ e） O O O O O O 有两种不同形式 （ a） （ b） O O O O O O O O O O O O O O O 有五种不同形式 下一页 上一页 停止放映 第 33 页 二叉树与树的区别（二）  观念 – 二叉树的子树有顺序关系 ， 分左子树和右子树 ， 而树则无此区分 ； – 二叉树的分支度一定为 0、 1或 2，而树的度可大于 2。 下一页 上一页 停止放映 第 34 页 二叉树的性质  性质一 二叉树的第 i层上至多有 2i1 个结点 （ i  1）。 利用归纳法证明： – i=1时 ， 只有一个结点 ， 对的； – 假设对所有的 j， 1 j  i， 命题成立 ， 即在第 j层上 ， 至多有 2j1 个结点。 – 由归纳假设 ， 第 i1层上至多有 2i2 个结点。 由于二叉树的每个结点的度至多为 2， 故第 i层上的最大结点数为第 i1层上的最大结点数的 2倍 ， 即 2 2i2 = 2i1。 下一页 上一页 停止放映 第 35 页 二叉树的性质（二） 性质二 深度为 k的二叉树上最多含有 2k1个结点 （ k  1）。 由性质一可见 ， 深度为 k的二叉树的最大结点数为： k i=1 i=1 k  （ 第 i层上的最大结点数 ） =  2i1 = 2k1 下一页 上一页 停止放映 第 36 页 验证二叉树的性质 1 2 3 8 6 5 7 4 10 9 11 12 13 14 15 该二叉树的第 3层有 231 个结点。 该二叉树深度为 4,最多有 241 个结点。 下一页 上一页 停止放映 第 37 页 二叉树的存储结构  顺序存储 （ 一维数组 ）  记录数组结构  链式存储结构 – 二叉链表 – 三叉链表 下一页 上一页 停止放映 第 38 页 顺序存储法（一维数组）  若一个二叉树的树高为 n，则对一个满二叉树，其结点个数为 2n1。 存入时按从左到右，从低阶层到高阶层的顺序存放。 A B C D E F G 0 1 2 3 4 5 6 7 A B C D E F G 0 1 2 3 4 5 6 7 A B E A B E 满树 非满树 下一页 上一页 停止放映 第 39 页 顺序存储（一维数组） 存储描述为： define MAXSIZE 100； typedef TElemType SBTree[MAXSIZE]； SBTree bt； 不便查找。 a1 a2 a3 a4 ... an 下一页 上一页 停止放映 第 40 页 记录数组结构  存储结构描述 : define MAXSIZE 100。 typedef struct SBNode { TElemType data。 int Lchild,Rchild。 } SBNode。 typedef struct｛ SBNode nodes[MAXSIZE]。 } SBTree。 下一页 上一页 停止放映 第 41 页 记录数组结构举例 1 2 6 3 4 5 1 2 6 2 3 4 3 0 5 4 0 0 5 0 0 6 0 0 结点 左子 右子 特点 : 找子方便 ,找父结点不便 . 下一页 上一页 停止放映 第 42 页 二叉链表存储结构 data leftp rightp 左指针 数据 右指针 A B C D E F G A B D C E F G ^ ^ ^ ^ ^ ^ ^ ^ 特点 : 找子易 , 找父难 . 下一页 上一页 停止放映 第 43 页 三叉链表存储结构 parent data rightp 左指针 数据 父结点 右指针 A B C D E F G C ^ ^ ^ ^ ^ ^ 特点 : 找子、找父都易。 leftp ^ ^ A B D E G ^ F 下一页 上一页 停止放映 第 44 页 特殊二叉树 满二叉树 完全二叉树 平衡二叉树 二叉排序树 下一页 上一页 停止放映 第 45 页 满二叉树 若 k为二叉树 T的深度 ， 且 T中共有 2k1个结点 （ k  1） ， 则称 T为满二叉树。 （ a） 满二叉树 （ b） 非满二叉树 O O O O O O O O O O O O O 下一页 上一页 停止放映 第 46 页 满二叉树的性质 若对满二叉树从第 1层开始 ,自上而下 、 从左至右给每个结点从 1开始编号的话 ， 则称深度为 k的满二叉树的结点编号满足： – 对某结点 i（ 1 i  2k1 1） ， 其左子树根的编号为 2*i（ 偶数 ） ， 其右子树根的编号为 2*i+1（ 奇数 ） ； （ 非叶结点 ） – 若 i1,则结点 i父结点的编号为 i/2(整除 )。 根据这一性质 ， 可用一维数组存储满二叉数的结点数据。 知道一个结点的编号 ， 经计算就能求出左 、 右子树的根及父结点的编号。 下一页 上一页 停止放映 第 47 页 满二叉树存储举例 1 4 3 2 5 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6。