二叉树的相关术语 结点 根结点、子结点、父结点、左 子结点、右子结点 分支结点、叶结点 边 路径、路径长度 B 祖先、后代 深度、高度、层数、宽度 E F 二叉树的高度定义为二叉树中 层数最大的叶结点的层数加1 二叉树的深度定义为二叉树中 GO 层数最大的叶结点的层数 H 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 6
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 二叉树的相关术语 结点 根结点、子结点、父结点、左 子结点、右子结点 分支结点、叶结点 边 路径、路径长度 祖先、后代 深度、高度、层数、宽度 二叉树的高度定义为二叉树中 层数最大的叶结点的层数加1 二叉树的深度定义为二叉树中 层数最大的叶结点的层数 H G E A B C D F I
满二叉树 如果一棵二叉树的任何结点,或者是树叶 或者恰有两橾非空子树,则此二叉树称作 满二叉树 Q B E F GH I 北京大学信息学院张铭编写 @版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 满二叉树 如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作 满二叉树 A B C D E F G H I 树叶 两棵非空子树
完全二叉树 最多只有最下面的两层结点度数可以小于2 最下一层的结点都集中最左边 B C B E F E FgHIJK 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 8
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 完全二叉树 A B G C A B C F G D E I J L D E F H K 最多只有最下面的两层结点度数可以小于2 最下一层的结点都集中最左边
扩充二叉树 所有空子树,都增加空树叶 xa wan ZO wi yo zom wIm wen xul yum wu xem yon ZI 北京大学信息学院张铭编写 @版权所有,转载或翻印必究 Page 9
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 扩充二叉树 所有空子树，都增加空树叶 wen wim xul yum wul xal wan zol wil yo zom xem yon zi
扩充二叉树 ■扩充二叉树是满二叉树 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 ■路径长度 ■外部路径长度E从扩充的二叉树的根到每个外部 结点的路径长度之和 内部路径长度I扩充的二叉树里从根到每个内部 结点的路径长度之和 ·E和两个量之间的关系为E=I+2n 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 扩充二叉树 扩充二叉树是满二叉树 新增加的空树叶(外部结点)的个数等于原来二叉树 的结点(内部结点)个数加1 路径长度 外部路径长度E 从扩充的二叉树的根到每个外部 结点的路径长度之和 内部路径长度I 扩充的二叉树里从根到每个内部 结点的路径长度之和 E和I两个量之间的关系为 E=I+2n