特殊二叉树 ◆满二叉树:一棵深度为k且有2k-1个结点的二叉树。 ◆完全二叉树:深度为k,有n个结点的二叉树,当且仅当其 每一个结点都与深度为k的满二叉树中编号从1到m的结点 对应。 7 15 8)(9 )a2④3)(4 图7-6满二叉树
特殊二叉树 满二叉树：一棵深度为k且有2 k -1个结点的二叉树。 完全二叉树：深度为k，有n个结点的二叉树，当且仅当其 每一个结点都与深度为k的满二叉树中编号从1到n的结点一 一对应
二叉树的性质 ◆性质1:在二叉树的第i层上至多有21-1个结点(i≥1。) ◆性质2:深度为k的二叉树至多有2k-1个结点(k≥1)。 ◆性质3:对任何一棵二叉树T,如其叶子结点数为n0,度为 2的结点数为n2,则n0=n2+1。 ◆性质4:具有n个结点的完全二叉树的深度为「logn」+1 ◆性质5:如果对一棵有n个结点的完全二叉树的结点按层编 号,则对任一结点(1≤i≤n)有: 如果i=1,结点是根结点,无双亲;如果i>1,则其 双亲结点的编号i/2。 0如果2>n,则结点远左孩子,为叶子结点;否则其 左孩子是结点2i。 0如果2i+1>n,则结点i右孩子;否则其右孩子结点 2i+1
二叉树的性质 性质1：在二叉树的第 i层上至多有2 i–1个结点（i≥1。） 性质2：深度为k的二叉树至多有2 k -1个结点（k≥1）。 性质3：对任何一棵二叉树T，如其叶子结点数为n0，度为 2的结点数为n2，则n0= n2+1。 性质4：具有n个结点的完全二叉树的深度为「log2n」+1。 性质5：如果对一棵有n个结点的完全二叉树的结点按层编 号，则对任一结点i（1≤i≤n）有： 如果i＝1，结点i是根结点，无双亲；如果i＞1，则其 双亲结点的编号i/2。 如果2i>n，则结点i无左孩子，为叶子结点；否则其 左孩子是结点2i。 如果2i+1>n，则结点i无右孩子；否则其右孩子结点 2i+1
二叉树的存储结构 ◆顺序存储结构: 0概念:把二叉树的所有结点,按照一定的次序顺序, 存储到一片连续的存储单元中 0完全二叉树的结点编号与线性序列的关系:编号为i 的结点是T(1≤i≤n),则有: ◆i>1,则T的双亲编号为i/2;若=1,则们为根结点。 ◆若2i≤n,则T的左孩子的编号是2i;否则,T无左孩子。 ◆若2计+1≤n,则T的右孩子的编号是2i+1;否则,T无右孩 子。 ◆若i为奇数且不为1,则T的左兄弟的编号为-1;否则,T没 有左兄弟。 ◆若i为偶数且小于n,则T的右兄弟的编号为i1;否则,Ti 没有右兄弟
二叉树的存储结构 顺序存储结构： 概念：把二叉树的所有结点，按照一定的次序顺序， 存储到一片连续的存储单元中。 完全二叉树的结点编号与线性序列的关系：编号为i 的结点是Ti(1≤i≤n)，则有： i>1，则Ti的双亲编号为 i/2；若i=1，则Ti为根结点。 若2i≤n，则Ti的左孩子的编号是2i；否则，Ti无左孩子。 若2i+1≤n，则Ti的右孩子的编号是2i+1；否则，Ti无右孩 子。 若i为奇数且不为1，则Ti的左兄弟的编号为i-1；否则，Ti没 有左兄弟。 若i为偶数且小于n，则Ti的右兄弟的编号为i+1；否则，Ti 没有右兄弟
0二叉树顺序存储结构实例1一完全二叉树: T: 01234 89101112131415|161 结点 ABCD G|HI丁K|L|M|N|0PQ a)完全二叉树 B GN 18 19 Q(R
二叉树顺序存储结构实例1 — 完全二叉树：
二叉树顺序存储结构实例2一一般二叉树: 2 4|56789101112131415 结点|11 口口口56口7 (b)一般二叉树 _白(6(7
二叉树顺序存储结构实例2 — 一般二叉树：