§5.2二叉树的概念 §5.2.1二叉树的基本概念 若有序树中每个结点的的子树数目不超过2,则称该树为 二叉树。二叉树是树的特例,空集称仍称为空(二叉)树 在树的非递归定义中限制结点的后继个数不超过2,或在 树的递归定义中将m的上限定为2即可得到二叉树的严格 定义 ·在二叉树中,通常分别称第1与第2子树为左子树和右子 树 16
16 •若有序树中每个结点的的子树数目不超过2，则称该树为 二叉树。二叉树是树的特例，空集称仍称为空（二叉）树。 •在树的非递归定义中限制结点的后继个数不超过2，或在 树的递归定义中将m的上限定为2即可得到二叉树的严格 定义。 •在二叉树中，通常分别称第1与第2子树为左子树和右子 树
§5.2.2几种特殊二叉树 (一)满二叉树 只含度为0与度为2的结点,且度为0的结点只出现在最 后一层的二叉树称为满二叉树。 显然,满二叉树中的任一层上结点都结满了结点,无空 缺。空树和只含一个结点的树也是满二叉树。实例见图 5-3(a) (a)满二叉树 17
17 (一) 满二叉树. •只含度为0与度为2的结点，且度为0的结点只出现在最 后一层的二叉树称为满二叉树。 •显然，满二叉树中的任一层上结点都结满了结点，无空 缺。空树和只含一个结点的树也是满二叉树。实例见图 5-3(a). (a) 满二叉树
§5.2.2几种特殊二叉树 一)顺序二叉树 °对任一棵满二叉树,从它的最后一层的最右结点起,按 从下到上、从左到右的次序,去掉若千个结点后所成的 树称为顺序二叉树 显然,顺序二叉树中可含度为1的结点,但它们只连续 出现在倒数第2层上的最右边。空树和只含一个结点的树 也是顺序二叉树 (b)顺序二叉树 18
18 (一) 顺序二叉树 •对任一棵满二叉树，从它的最后一层的最右结点起，按 从下到上、从左到右的次序，去掉若干个结点后所成的 树称为顺序二叉树。 •显然，顺序二叉树中可含度为1的结点，但它们只连续 出现在倒数第2层上的最右边。空树和只含一个结点的树 也是顺序二叉树。 (b) 顺序二叉树
§5.2.2几种特殊二叉树 (一)完全二叉树 不含度为1的结点的二叉树称完全二叉树 显然,完全二叉树与满二叉树的不同是,它的度为0的结 点可出现在任一层上 显然,空树和只含一个结点的树也是完全二叉树 (c)完全二叉树
19 (一) 完全二叉树 •不含度为1的结点的二叉树称完全二叉树。 •显然，完全二叉树与满二叉树的不同是，它的度为0的结 点可出现在任一层上。 •显然，空树和只含一个结点的树也是完全二叉树。 (c) 完全二叉树
§5.2.2几种特殊二叉树 顺序、完全二叉树 (d)顺序、完全二叉树 20
20 • 顺序、完全二叉树 (d) 顺序、完全二叉树