5、求二又树B中结点p的左孩子结点: LeftChildBtree(BT,p) 初始条件:二叉树BT已经存在,且p是二叉树BT中的一个结点 操作结果:若结点p不是二叉树BT的叶子结点,则返回结点p的左孩子 结点;否则,返回NUL 6、求二又树BT中结点p的右孩子结点: RightChildBTree(BT,p) 初始条件:二叉树BT已经存在,且结点p是二叉树BT中的一个结点; 操作结果:若结点p不是二叉树BT的叶子结点,则返回结点p的右孩子 结点;否则,返回NULL 7、判断二叉树BT是否为空: Empt yBTree(BT) 初始条件:二叉树BT已经存在; 操作结果:若二叉树BT为空,则返回True;否则,返回 False。 8、求二叉树BT的深度: DepthBTree(BT) 初始条件:二叉树BT已经存在; 操作结果:返回二叉树BT的深度 计算机教研宦 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第11页 5、求二叉树BT中结点p的左孩子结点：LeftChildBTree(BT，p) 初始条件：二叉树BT已经存在，且p是二叉树BT中的一个结点； 操作结果：若结点p不是二叉树BT的叶子结点，则返回结点p的左孩子 结点；否则，返回NULL。 6、求二叉树BT中结点p的右孩子结点：RightChildBTree(BT，p) 初始条件：二叉树BT已经存在，且结点p是二叉树BT中的一个结点； 操作结果：若结点p不是二叉树BT的叶子结点，则返回结点p的右孩子 结点；否则，返回NULL。 7、判断二叉树BT是否为空：EmptyBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：若二叉树BT为空，则返回True；否则，返回False。 8、求二叉树BT的深度：DepthBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：返回二叉树BT的深度
⑨9、将结点p作为二叉树BT中结点的左子树插入 InsertLeftBTree(Bt, p, g) 初始条件:二叉树BT已经存在,且结点q是二叉树BT中的结点; 操作结果:将结点p作为二叉树BT中结点q的左子树插入 10、将结点p作为二叉树BT中结点q的右子树插入: InsertRightBTree(Bt, p, g) 初始条件:二叉树BT已经存在,且结点q是二叉树BT中的结点; 操作结果:将结点p作为二叉树BT中结点q的右子树插入 章和吕风街 的1、在二叉树BT中删除结点p的左子树: DeletelChbtree(BT,p) 初始条件:二叉树BT已经存在,结点p是二叉树BT中的结点 操作结果:在二叉树BT中删除结点p的左子树 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第12页 9、将结点p作为二叉树BT中结点q的左子树插入： InsertLeftBTree(BT，p，q) 初始条件：二叉树BT已经存在，且结点q是二叉树BT中的结点； 操作结果：将结点p作为二叉树BT中结点q的左子树插入。 10、将结点p作为二叉树BT中结点q的右子树插入： InsertRightBTree(BT，p，q) 初始条件：二叉树BT已经存在，且结点q是二叉树BT中的结点； 操作结果：将结点p作为二叉树BT中结点q的右子树插入。 11、在二叉树BT中删除结点p的左子树：DeleteLChBTree(BT，p) 初始条件：二叉树BT已经存在，结点p是二叉树BT中的结点； 操作结果：在二叉树BT中删除结点p的左子树
@12、在二叉树BT中删除结点p的右子树: DeleterChBtree(BT,p) 初始条件:二叉树BT已经存在,结点p是二叉树BT中的结点; 操作结果:在二叉树BT中删除结点p的右子树。 13、给二叉树BT中结点p赋值: AssignNodeBTree(BT,p,x) 初始条件:二叉树BT已经存在,且结点p是二叉树BT中的结点; 操作结果:将x赋值给二叉树BT中的结点p 14、求二叉树BT中结点p的左子树: GetLChBTree(BT,p) 初始条件:二叉树BT已经存在,结点p是二叉树BT中的结点; 操作结果:若p是非叶子结点,则返回结点p的左子树,否则 返回NUI 意15、求二叉树BT中结点p的右子树: GetRChBTree(BT,p) 初始条件:二叉树BT已经存在,结点p是二叉树BT中的结点 操作结果:若p是非叶子结点,则返回结点p的右子树,否则 返回NUL 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第13页 12、在二叉树BT中删除结点p的右子树：DeleteRChBTree(BT，p) 初始条件：二叉树BT已经存在，结点p是二叉树BT中的结点； 操作结果：在二叉树BT中删除结点p的右子树。 13、给二叉树BT中结点p赋值：AssignNodeBTree(BT，p，x) 初始条件：二叉树BT已经存在，且结点p是二叉树BT中的结点； 操作结果：将x赋值给二叉树BT中的结点p。 14、求二叉树BT中结点p的左子树：GetLChBTree(BT，p) 初始条件：二叉树BT已经存在，结点p是二叉树BT中的结点； 操作结果：若p是非叶子结点，则返回结点p的左子树，否则 返回NULL。 15、求二叉树BT中结点p的右子树：GetRChBTree(BT，p) 初始条件：二叉树BT已经存在，结点p是二叉树BT中的结点； 操作结果：若p是非叶子结点，则返回结点p的右子树，否则 返回NULL
16、按前序遍历方式遍历二叉树BT: PreOrder traverseBtree(BT) 初始条件:二叉树BT已经存在; 操作结果:按前序遍历方式遍历二叉树BT,返回前序遍历序列。 17、按中序遍历方式遍历二叉树BT: InOrderTraverseBtree(BT) 初始条件:二叉树BT已经存在; 操作结果:按中序遍历方式遍历二叉树BT,返回中序遍历序列 的18、按后序遍历方式遍历二叉树BT: PostOrderTraverseBTree(bt) 初始条件:二叉树BT已经存在 操作结果:按后序遍历方式遍历二叉树BT,返回后序遍历序列。 19、按层次遍历方式遍历二叉树BT: Leve1OrderTraverseBTree(BT) 初始条件:二叉树BT已经存在; 操作结果:按层次遍历方式遍历二叉树BT,返回层次遍历序列。 计算机教研室 第14页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第14页 16、按前序遍历方式遍历二叉树BT： PreOrderTraverseBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：按前序遍历方式遍历二叉树BT，返回前序遍历序列。 17、按中序遍历方式遍历二叉树BT： InOrderTraverseBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：按中序遍历方式遍历二叉树BT，返回中序遍历序列。 18、按后序遍历方式遍历二叉树BT： PostOrderTraverseBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：按后序遍历方式遍历二叉树BT，返回后序遍历序列。 19、按层次遍历方式遍历二叉树BT： LevelOrderTraverseBTree(BT) 初始条件：二叉树BT已经存在； 操作结果：按层次遍历方式遍历二叉树BT，返回层次遍历序列
@6.12二叉树的性质 性质1:在二叉树的第层上至多有21个结点(i>=1)。 证明: 采用归纳法证明此性质。 当i=1时,只有一个根结点,21=20=1,命题成立。 现在假定对所有的j,1≤ji,命题成立,即第层上至多有21个结 点,那么可以证明j=时命题也成立。由归纳假设可知,第-1层上 至多有212个结点。 由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i 意1层上最大结点数的二倍, 即2×212=21-1 命题得到证明。 计算机教研宦 第15页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第15页 6.1.2 二叉树的性质 性质1： 在二叉树的第i层上至多有2 i-1个结点(i>=1)。 证明： 采用归纳法证明此性质。 当i=1时，只有一个根结点，2 i-1 =20 =1,命题成立。 现在假定对所有的j，1≤j<i,命题成立，即第j层上至多有2 j-1个结 点，那么可以证明j＝i时命题也成立。由归纳假设可知，第i－1层上 至多有2 i-2个结点。 由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i- 1层上最大结点数的二倍， 即2×2 i-2＝2 i-1 。 命题得到证明