52.1二又树的概念 2)完全二又树:如果一颗二叉树只有最下一层结点数可能 未达到最大,并且最下层结点都集中在该层的最左端,则称为完 全二叉树; DEF (b) B (a)、(b)完全二叉树 (c)不是完全二叉树 DE G
2)完全二叉树：如果一颗二叉树只有最下一层结点数可能 未达到最大，并且最下层结点都集中在该层的最左端，则称为完 全二叉树； A D E B C G A D E B C (a) (c) (b) (a)、(b)完全二叉树 (c) 不是完全二叉树 A D E F B C 5.2.1 二叉树的概念
622二叉树的性质 性质1在二叉树的第i层上最多有21个结点 性质2深度为k的二叉树最多有2k-1个结点 性质3设二叉树叶子结点数为no,度为2的结点n2,则n= C. G
性质1 在二叉树的第i 层上最多有2 i-1个结点 性质2 深度为k的二叉树最多有 2 k-1 个结点 性质3 设二叉树叶子结点数为n0，度为2的结点n2，则n0 = n2 +1 A F G D E B C 6.2.2 二叉树的性质
下面是两个关于完全二叉树的性质 性质4具有n个结点的完全二叉树的深度为:|og2n+1 对完全二叉树的结点编号:从上到下,每一层从左到右 性质5:在完全二叉树中编号为i的结点 1)若有左孩子,则左孩编号为2i 2)若有右孩子,则右孩子结点编号为2i+1 3)若有双亲,则双亲结点编号为i122B C 3 4D5EF6
下面是两个关于完全二叉树的性质 性质4 具有n个结点的完全二叉树的深度为：log2 n +1. 对完全二叉树的结点编号：从上到下，每一层从左到右 A D E F B C 1 2 3 4 5 6 性质5：在完全二叉树中编号为i的结点 1）若有左孩子，则左孩编号为2i 2）若有右孩子，则右孩子结点编号为2i+1 3）若有双亲，则双亲结点编号为 i/2
623二叉树的存储结构 1二叉树的顺序结构 适于满二叉树或完全二叉树的存储。 逻辑结构 B c D EF 存储结构 0123456 n-1 AB F
6.2.3 二叉树的存储结构 1 二叉树的顺序结构 适于满二叉树或完全二叉树的存储。 A D E F B C 0 1 2 3 4 5 6 n-1 A B C D E F 逻辑结构 存储结构
B 2 B 3,0 DF40566F7 89 0 2345678910 A BCDE0 F00 G
A F G D E B C 1 6 7 2 4 5 3 8 10 A F G D E B C 9 0 1 2 3 4 5 6 7 8 9 10 m-1 A B C D E 0 F 0 0 G