二叉树的基本操作 第六章树和三叉树 (6)Create (X, LBTRBT 建树操作。生成一棵以结点x为根,二叉树LBT和RBT分别为 左、右子树的二叉树。 ⑦7) schIld(BTyx)和 scHild(BTyx) 插入子树操作。将以结点x为根且右子树为空的二叉树分别置 为二叉树BT中结点y的左子树和右子树。若结点y有左子树/右子树 ,则插入后是结点x的右子树。 (8)DelL Child(BT, x) FA DelRChild(BT,x) 删除子树操作。分别删除二叉树BT中以结点x为根的左子树或 右子树。若结点x无左子树或右子树,则为空操作。 (9)Traverse(BT) 树的遍历操作。按某个次序依次访问二叉树BT中各个结点, 并使每个结点只被访问一次。 (10)Clear(BT) 清除二叉树的结构操作。 注.与树类似,用户可根据操作需要设定二叉树的抽象数据类 型 第21页
第六章 树和二叉树 第21页 二叉树的基本操作 (6) Create (x,LBT,RBT) 建树操作。生成一棵以结点x为根，二叉树LBT和RBT分别为 左、右子树的二叉树。 (7) InsLChild(BT,y,x) 和 InsRChild(BT,y,x) 插入子树操作。将以结点x为根且右子树为空的二叉树分别置 为二叉树BT中结点y的左子树和右子树。若结点y有左子树/右子树 ，则插入后是结点x的右子树。 (8) DelLChild(BT,x) 和 DelRChild(BT,x) 删除子树操作。分别删除二叉树BT中以结点x为根的左子树或 右子树。若结点x无左子树或右子树，则为空操作。 (9) Traverse (BT) 树的遍历操作。按某个次序依次访问二叉树BT中各个结点， 并使每个结点只被访问一次。 (10) Clear(BT) 清除二叉树的结构操作。 注. 与树类似，用户可根据操作需要设定二叉树的抽象数据类 型
二叉树的性质 第六章树和三叉树 二叉树与一般树既有联系,又有区别,它是有序树的一个特例 。用于一般树上的术语也可用于二叉树。二叉树有若干重要性质 性质1在二叉树的第i层上至多有2个结点(1)。 证用归纳法 1,只有一个根结点。21=20=1。正确 设命题对成立,即有第层上至多有21个结点。由于二叉树每 结点的度至多为2,故在最大结点数的2倍, 212=2=201}1。故命题对j+1亦成立。证毕 一性质2深度为的二叉树至多有21个结点(k 证]由性质1,深度为k的二叉树的最大结点数为 (第层上的最大结点数) ∑=∑22=1+2+22+…+24+1=2-1 第22页
第六章 树和二叉树 第22页 ⚫ 二叉树的性质 二叉树与一般树既有联系，又有区别，它是有序树的一个特例 。用于一般树上的术语也可用于二叉树。二叉树有若干重要性质。 性质1 在二叉树的第i层上至多有2 i-1个结点(i≥1)。 [证] 用归纳法。 i=1，只有一个根结点。2 i-1=20=1。正确。 设命题对j成立，即有第j层上至多有2 j-1个结点。由于二叉树每 个结点的度至多为2，故在最大结点数的2倍，即 2 j-1 .2=2j=2(j+1)-1。故命题对j+1亦成立。证毕。 性质2 深度为k的二叉树至多有2 k -1个结点(k ≥1)。 [证] 由性质1，深度为k的二叉树的最大结点数为 （第i层上的最大结点数）
二叉树的性质 第六章树和三叉树 性质3二叉树T的叶结点数等于度为2的结点数加1。 证]若记二叉树T的终端结点数为n,度为2的结点数为 则欲证 +1 设n1为二叉树T中度为1的结点数,n为二叉树T中的总结一 点数。由于二叉树中所有结点的度均小于或等于2,故有 n=notntn 再看二叉树的分支数。除根结点外,其余结点都有一个 一分支进入。设B为分支总数,则 n=B+1 (2) 由于这些分支是由度为1或2的结点射出的,所以又有 B=n,+2n (3) 由(2)和(3)知 n=n1+2n2+1 4) 由(1)和(4)可得 no-n 第23页
第六章 树和二叉树 第23页 性质3 二叉树T的叶结点数等于度为2的结点数加1。 [证] 若记二叉树T的终端结点数为n0，度为2的结点数为 n2，则欲证n0=n2+1。 设n1为二叉树T中度为1的结点数，n为二叉树T中的总结 点数。由于二叉树中所有结点的度均小于或等于2，故有 n=n0+n1+n2 (1) 再看二叉树的分支数。除根结点外，其余结点都有一个 分支进入。设B为分支总数，则 n=B+1 (2) 由于这些分支是由度为1或2的结点射出的，所以又有 B=n1+2n2 (3) 由(2)和(3)知 n=n1+2n2+1 (4) 由(1)和(4)可得 n0=n2+1. ⚫ 二叉树的性质
二又树的性质 第六章树和三叉树 定义5一棵深度为k且具有2k1个结点的二又树称为满 叉树。 定义6深度为k有n个结点的二叉树,当且仅当该二叉树 一的n个结点与深度为k的满二叉树中编号从1至n的结点位置 对应时,则称为亚满二叉树或完全二又树。 示例 ① 8(9⑩0⑩2 8⑨ (a)满二叉树 (b)完全二叉树一 注,完全二叉树的另一种定义:深度为k的完全二叉树,其k-1 层是一棵满二叉树,最后第k层结点都尽量排在靠左的位置上 即第k层的所有叶子结点占据树的最左边的位置) 第24页
第六章 树和二叉树 第24页 定义5 一棵深度为k且具有2 k -1个结点的二叉树称为满 二叉树。 注. 完全二叉树的另一种定义：深度为k的完全二叉树，其k-1 层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上 （即第k层的所有叶子结点占据树的最左边的位置）。 ⚫ 二叉树的性质 定义6 深度为k有n个结点的二叉树，当且仅当该二叉树 的n个结点与深度为k的满二叉树中编号从1至n的结点位置 一一对应时，则称为亚满二叉树或完全二叉树。 示例 1 2 3 4 5 8 9 10 11 6 7 12 13 14 15 (a) 满二叉树 1 2 3 4 5 8 9 10 6 7 (b)完全二叉树
又树的性质 第六章树和三叉树 对完全二叉树的几点说明: (1)度小于2的结点(包括度等于0的叶结点)只可能在最下两 个层次上出现; (2)对任一结点,其左子树的层次≥右子树的层次。以下两个二 叉树都非完全二叉树 2) 3 (2 3 4 5 4 5 6 6)⑦7 3)有的书中定义只有度为0或2的二叉树称为完全二叉 树。则上页(b)就为非完全二又树;但若去掉结点10或增加 结点11,则为完全二叉树; (4)满二叉树亦是完全二叉树,但反之不然 第25页
第六章 树和二叉树 第25页 对完全二叉树的几点说明： (1) 度小于2的结点（包括度等于0的叶结点）只可能在最下两 个层次上出现； (2) 对任一结点，其左子树的层次≥右子树的层次。以下两个二 叉树都非完全二叉树 (3) 有的书中定义只有度为0或2的二叉树称为完全二叉 树。则上页(b)就为非完全二叉树；但若去掉结点10或增加 结点11，则为完全二叉树； (4) 满二叉树亦是完全二叉树，但反之不然。 1 2 3 4 5 6 7 1 2 3 4 5 6 ⚫ 二叉树的性质