性质4具有n个结点的完全二又树的深度为 log2n」+1 证明:设完全二叉树的深度为/,则有 2k-1-1<n≤2k-1→2k-1<n<2k 取对数k-≤log2n<k 因为k为数,所以k=Llog2n」+1 说明:常出现在选择题中
性质4 具有n个结点的完全二叉树的深度为 log2n +1 证明：设完全二叉树的深度为k，则有 2 k-1 - 1 < n 2 k - 1 2 k-1 n < 2 k 取对数 k-1 log2n < k 因为k为整数，所以k = log2n +1 说明：常出现在选择题中
性质5如果将一棵有n个结点的完全二叉树的结 点按层序(自顶向下,同一层自左向右)连续编 号1,2,…,n,然后按此结点编号将树中各结点顺 序地存放于一个一维数组中,并简称编号为的结 点为结点(1≤≤m)则有以下关系 若i==1,则i是二叉树的根,无双亲 着>1,则i的双亲为i2」 若2*≤n,则i的左孩子为2*,否则无左孩子 若2计1≤n,则i的右孩子为2计1,否则无右 孩子 若i为偶数,且i!=n,则其右兄弟为计1 若i为奇数,且i!=1,则其左兄弟为i-1 i所在层次为Llog2i+1
性质5 如果将一棵有n个结点的完全二叉树的结 点按层序(自顶向下，同一层自左向右）连续编 号1, 2, …, n，然后按此结点编号将树中各结点顺 序地存放于一个一维数组中, 并简称编号为i的结 点为结点i (1 i n)。则有以下关系： ◼ 若i == 1, 则 i 是二叉树的根，无双亲 若i > 1, 则 i 的双亲为i /2 ◼ 若2*i ≤ n, 则 i 的左孩子为2*i，否则无左孩子 若2*i+1 ≤ n, 则 i 的右孩子为2*i+1，否则无右 孩子 ◼ 若 i 为偶数, 且i != n, 则其右兄弟为i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1 ◼ i 所在层次为 log2 i +1
二叉树的存储结构 1.顺序存储结袍(数组表示) D (66 05 910/12 13 15 0(2)9)(583 70)(62 123456789101112123456789101112131415 313126910510121495:8]31212610:17n62 (b) 完全二叉树的数组表示一般二叉树的数组表示
完全二叉树的数组表示 一般二叉树的数组表示 二叉树的存储结构 1. 顺序存储结构（数组表示）
由于一般二叉树必须仿照完 全二叉树那样存储,可能会 浪费很多存储空间,单支树 就是一个极端情况。 15 88 31 49 #define MAX TREE SIzE 100 单支树 typedef TElem Type SqBitree[Max TREE Size Sqbitree bt
#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree[MAX_TREE_SIZE]; SqBiTree bt; 由于一般二叉树必须仿照完 全二叉树那样存储，可能会 浪费很多存储空间，单支树 就是一个极端情况。 单支树
2.链式存储结构[ child data parent right child leftChild data right child parent ava data leftchild right child leftchild right child (a)二叉链表 (b)三叉链表 typedef struct BiTNode{∥二叉链表的定义 TElem Type data Struct binode Child. *rchild 3BITNode, *BiTree
2.链式存储结构 typedef struct BiTNode{ //二叉链表的定义 TElemType data; Struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;