第4单元非线性结构一

第4单元非线性结构一内容摘要：

指针 数据 父结点 右指针 A B C D E F G C 特点 : 找子、找父都易 leftp A B D E G F 2. 三叉链表 18 /41 三 .特殊二叉树 满二叉树  1. 满二叉树  若深度为 k的二叉树 T中共有 2k1个结点 (k≥ 1),则称 T为满二叉树。 （ a） 满二叉树 （ b） 非满二叉树 O O O O O O O O O O O O O 19 /41 三 .特殊二叉树 满二叉树  满二叉树的性质  对满二叉树从第 1层开始 ,自上而下 、 从左至右对每个结点由 1开始编号 ， 则深度为 k的满二叉树结点编号 i(1≤i≤ 2k11),满足以下关系： – 1) i的左子树根编号为 2*i， 右子树根编号为 2*i+1 – 2) i的父结点编号为 int(i/2)  应用 : 用一维数组存储满二叉数的结点 ,由一个结点的编号 ， 计算出左 、 右子树的根及父结点的编号 20 /41 满二叉树存储举例 1 4 3 2 5 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 •第 i个结点存放在第 i个位置； •第 i个结点的父结点在第 i/2个位置。 •第 i个结点的左子结点就存放在 第 2*i的个位置。 右子存放在第 2*i+1位置 . 21 /41 三 .特殊二叉树 完全二叉树  深度为 k的二叉树 T,每层结点数目若满足 : •第 i层 (1≤ i≤k 1)的结点个数均为 2i1 •第 k层从右边连续缺若干个结点 这样的树称为完全二叉树。  特点 : 叶结点只能出现在层次最大的两层上 .  （ a） 完全二叉树 （ b） 非完全二叉树 O O O O O O O O O O O 22 /41 完全二叉树的性质  设完全二叉树的结点总数为 n， 深度为 k， 某结点编号为 i(1≤ i≤k 1),则有： – 1) 若 i1,则 i的双亲结点编号为 int(i/2) – 2) 若 2*i≤ n,则 i的左子结点的编号为 2*i,否则 i为叶结点。 – 3) 若 2*i+1≤ n,则 i 的右子结点的编号为2*i+1,否则 ,i为叶结点 .  完全二叉树也可以采用一维树组作为存储结构 ,且方法完全同满二叉树 . 23 /41 三 .特殊二叉树 平衡二叉树  : 二叉树上任一结点的左子树深度减去右子树深度的差值。  : 二叉树中 ,每个结点的平衡因子的绝对值都不大于 1。  （ a） 平衡二叉树 （ b） 非平衡二叉树 O O O O O O O O O O O O O O 24 /41。