2.二叉树抽象数据类型 数据集合:二叉树的结点集合,每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: (1)创建 MakeTree(T (2)撤消 Destroy tree(T) (3)左插入结点 InsertLeftNode(curr,x) (5)左删除子树 DeleteLeftTree(curr),x) (4)右插入结点 nsertRightNode(cur (6)右删除子树 DeleteRightTree(curr) (7)遍历二叉树 Traverse(T,Ⅴ isto
数据集合：二叉树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合： （1）创建MakeTree(T) （2）撤消DestroyTree(T) （3）左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit()) 2.二叉树抽象数据类型
3二叉树的性质 性质1在一棵非空二叉树的第层上至多有2个结点(0)。 性质2深度为k的二叉树至多有2-1个结点。 说明:深度k=-1,表示没有一个结点;深度k=0,表示只有 一个根结点
3.二叉树的性质 性质1 在一棵非空二叉树的第i层上至多有2 i个结点（i≥0）。 性质2 深度为k的二叉树至多有2 k+1 -1个结点。 说明：深度k=-1，表示没有一个结点；深度k=0，表示只有 一个根结点
性质3对于一棵非空的二叉树,如果叶结点个数为n,度 为2的结点数为n2,则有n=n2+1。 证明:设n为二叉树的结点总数,n为二叉树中度为1的 结点个数,则有:n=no+n1+n2 另外,在二叉树中,除根结点外的所有结点都有一个惟 的进入分支,设M为二叉树中所有结点的进入分支数, 则有: M=n-1 从二叉树的结构可知,二叉树的所有进入分支是由度为 1的结点和度为2的结点发出的,每个度为1的结点发出 个分支,每个度为2的结点发出两个分支,所以又有 M=n1+2 x n2 因此有:n-1=n1+2×n2 再把n=no+n1+n2代入,则可以得到no=n2+1
性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度 为2的结点数为n2，则有 n0= n2+1。 证明：设n为二叉树的结点总数，n1为二叉树中度为1的 结点个数，则有： n = n0 + n1 + n2 另外，在二叉树中，除根结点外的所有结点都有一个惟 一的进入分支，设M为二叉树中所有结点的进入分支数， 则有： M = n - 1 从二叉树的结构可知，二叉树的所有进入分支是由度为 1的结点和度为2的结点发出的，每个度为1的结点发出一 个分支，每个度为2的结点发出两个分支，所以又有： M = n1 + 2 × n2 因此有： n - 1 = n1 + 2 × n2 再把 n=n0+n1+n2 代入，则可以得到 n0 = n2 + 1
性质4具有n个结点的完全二又树的深度k为大于或等于 lb(n+1)-1的最小整数。 证明:由性质2和完全二叉树的定义可知,对于有n个结点的 深度为k的完全二叉树有:2k-1<n≤2k+1-1 移项有:2k<n+1≤2k+1 对不等式求对数,有:k<lb(n+1)≤k+1 因为b(n+1)介于k和k+1之间且大于k,而二叉树的深度又 只能是整数,所以必有k为大于或等于b(n+1)-1的最小整数。 可简写为k=「b(n+1)-1。例如,「201=2,「211=3 若结点个数n=0,则有深度k=-1,满足k=「b(+1)-11= 若结点个数n=1,则有深度k=0,满足k=「|b1+1)-11=0 若结点个数n=2,则有深度k=1,满足k=Tb(2+1)-11 「0.xx1=1; 若结点个数n=3,则有深度k=1,满足k=b(3+1)-1|=1
性质4 具有n个结点的完全二叉树的深度k为大于或等于 lb(n+1)-1的最小整数。 证明：由性质2和完全二叉树的定义可知，对于有n个结点的 深度为k的完全二叉树有：2 k-1 < n ≤ 2k+1-1 移项有：2 k < n+1 ≤ 2k+1 对不等式求对数，有：k < lb(n+1) ≤ k+1 因为lb(n+1)介于k和k+1之间且大于k，而二叉树的深度又 只能是整数，所以必有k为大于或等于lb(n+1)-1的最小整数。 可简写为k=lb(n+1)-1。例如，2.0=2，2.1=3。 若结点个数n=0，则有深度k=-1，满足k=lb(0+1)-1=- 1； 若结点个数n=1，则有深度k=0，满足k=lb(1+1)-1=0； 若结点个数n=2，则有深度k=1，满足k=lb(2+1)-1 =0.xx =1； 若结点个数n=3，则有深度k=1，满足k=lb(3+1)-1=1
性质5对于一棵有n个结点的完全二又树,按照从上至下和从 左至右的顺序对所有结点从0开始顺序编号则对于序号为 结点(0≤i<n),有: (1)如果0,则其双亲是结点(1)2(“”表示整除);如果0, 则结点i是根结点,无双亲。 (2)如果2计1<n,其左孩子是结点2+1;如果2计12n,则结点 无左孩子。 (3)如果2i+2<n,其右孩子是结点2i+2;如果2i+2≥n,则 结点右孩子
性质5 对于一棵有n个结点的完全二叉树，按照从上至下和从 左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的 结点(0≤i < n),有： (1)如果i>0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0， 则结点i是根结点，无双亲。 (2)如果2i+1＜n ，其左孩子是结点2i+1；如果2i+1≥n，则结点 i无左孩子。 (3)如果2i＋2＜n，其右孩子是结点2i＋2；如果2i＋2≥n，则 结点i无右孩子