二叉树相关术语(1) 口二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root) 口二叉树中的任何非根结点都有且仅有一个前驱结点,称之为该结点的父 结点(或称为双亲, parent)。根结点即为二叉树中唯一没有父结点的结点 口二叉树中的任何结点最多可能有两个后继结点,分别称为左子结点(或左 孩子、左子女, left child)和右子结点(或右孩子,右子女, right child), 具有相同父结点的结点之间互称兄弟结点 sibling) 二叉树中结点的子树数目称为结点的度(d egree)。 口没有子结点的结点称为叶结点(leaf,也称“树叶”或“终端结点”), 叶结点的度为0。 口除叶结点以外的那些非终端结点称为内部结点(或分支结点, internal node) 口父结点k与子结点k之间存在一条有向连线<k,k3>,称作边(edge) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树相关术语（1） 二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root) 二叉树中的任何非根结点都有且仅有一个前驱结点，称之为该结点的父 结点(或称为双亲，parent)。根结点即为二叉树中唯一没有父结点的结点 二叉树中的任何结点最多可能有两个后继结点，分别称为左子结点(或左 孩子、左子女，left child)和右子结点(或右孩子，右子女，right child)， 具有相同父结点的结点之间互称兄弟结点(sibling) 二叉树中结点的子树数目称为结点的度(degree)。 没有子结点的结点称为叶结点(leaf，也称“树叶”或“终端结点”)， 叶结点的度为0。 除叶结点以外的那些非终端结点称为内部结点(或分支结点，internal node) 父结点k与子结点k’之间存在一条有向连线<k, k’>，称作边(edge)
二叉树相关术语(2) 口若二又树中存在结点序列{k0,k1,…,ks},使得kO,k1>,<k1, k2>,,<ks-1,ks>都是二叉树中的边,则称从结点k0到结点ks存在 一条路径(path),该路径所经历的边的个数称为这条路径的路径长度 ( path length)。若有一条由k到达ks的路径,则称k是ks的祖先( ancestor), ks是k的子孙( descendant) 口断掉一个结点与其父结点的连接,则该结点与其子孙构成的树就称为 以该结点为根的子树( subtree6 口从根结点到某个结点的路径长度称为结点的层数(evel),根结点为第0 层,非根结点的层数是其父结点的层数加1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树相关术语（2） 若二叉树中存在结点序列{k0，k1，…，ks}，使得<k0，k1>，< k1， k2>，…，< ks-1，ks>都是二叉树中的边，则称从结点k0到结点ks存在 一条路径(path)，该路径所经历的边的个数称为这条路径的路径长度 (path length)。若有一条由 k到达ks的路径，则称k是ks的祖先(ancestor)， ks是k的子孙(descendant) 断掉一个结点与其父结点的连接，则该结点与其子孙构成的树就称为 以该结点为根的子树(subtree) 从根结点到某个结点的路径长度称为结点的层数(level)，根结点为第0 层，非根结点的层数是其父结点的层数加1
满二叉树与完全二叉树 口如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树, 则这棵二又树称作满二叉树 full binary tree)) 口如果一棵二叉树最多只有最下面的两层结点度数可以小于2,并且最下 面一层的结点都集中在该层最左边的连续位置上,则此二叉树称作完 全二叉树( (complete binary tree) (A)满二叉树 (b)完全二叉树 图52满二叉树和完全二叉树示例 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 满二叉树与完全二叉树 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树， 则这棵二叉树称作满二叉树(full binary tree)。 如果一棵二叉树最多只有最下面的两层结点度数可以小于2，并且最下 面一层的结点都集中在该层最左边的连续位置上，则此二叉树称作完 全二叉树(complete binary tree)。 图5.2 满二叉树和完全二叉树示例 A B C D E F G A B D E H I J K C F G L (A)满二叉树 (b)完全二叉树
完全二叉树 口完全二叉树的特点是: 其叶结点只可能在层次最大的两层出现 完全二叉树中由根结点到各个结点的路径长度总和在具 有同样结点个数的二叉树中达到了最小,即任意一棵 二叉树中根结点到各结点的最长路径一定不短于结点 数目相同的完全二叉树中的路径长度 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 完全二叉树 完全二叉树的特点是： ◼其叶结点只可能在层次最大的两层出现 ◼完全二叉树中由根结点到各个结点的路径长度总和在具 有同样结点个数的二叉树中达到了最小，即任意一棵 二叉树中根结点到各结点的最长路径一定不短于结点 数目相同的完全二叉树中的路径长度
扩充二叉树 ■在二叉树里出现空子树的位置增加空树叶,所形成的 二叉树称为扩充二叉树 extended binary tree) ■构造一棵扩充二叉树只需要在原二叉树里度数为1的 分支结点下增加一个空树叶,在原二叉树的树叶下面 增加两个新的空树叶。 扩充二叉树是满二叉树,新增空树叶(以下称为外部 结点)的个数等于原二叉树的结点(以下称为内部结点) 个数加1 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 扩充二叉树 ◼ 在二叉树里出现空子树的位置增加空树叶，所形成的 二叉树称为扩充二叉树(extended binary tree) ◼ 构造一棵扩充二叉树只需要在原二叉树里度数为1的 分支结点下增加一个空树叶，在原二叉树的树叶下面 增加两个新的空树叶。 ◼ 扩充二叉树是满二叉树，新增空树叶(以下称为外部 结点)的个数等于原二叉树的结点(以下称为内部结点) 个数加1