(3)双亲孩子表示法 data parent head child next 0A|-1 12∧ 1B0 4 5∧ 2 6∧ ∧ 4 CDEFGHI 0111 7 8∧ 567 2 4 ∧∧ 4 双亲孩子表示法存储结构
双亲孩子表示法存储结构 (3)双亲孩子表示法 ∧ H 4 G 2 F 1 E 1 D 1 C 0 B 0 A -1 I 4 data parent head 0 1 2 3 4 5 6 7 8 ∧ ∧ ∧ ∧ child next 7 8 ∧ ∧ ∧ ∧ 1 2 3 4 5 6
(4)孩子兄弟表示法 root A∧ B C∧ ∧D E ∧F∧ ∧G|∧ ∧|H ∧I∧ 常规指针的孩子兄弟表示法
(4)孩子兄弟表示法 常规指针的孩子兄弟表示法 root ∧ B C D E F G H I ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ A
82二叉树 1二叉树的定义 二叉树:是m(n20)个结点的有限集合。n=0的树称为空二 叉树;n>0的二叉树由一个根结点以及两棵互不相交的、 分别称为左子树和右子树的二叉树组成。 逻辑结构:一对二(1:2) 基本特征: ①每个结点最多只有两棵子树(不存在度大于2的结点); ②左子树和右子树次序不能颠倒。所以下面是两棵不同 的树
8.2 二叉树 一、二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二 叉树；n>0的二叉树由一个根结点以及两棵互不相交的、 分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: ① 每个结点最多只有两棵子树（不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。所以下面是两棵不同 的树 1.二叉树的定义
二、满二叉树:在一棵二叉树中,如果所有分支结点都存在左 子树和右子树,并且所有叶子结点都在同一层上,这样的 二叉树称为满二叉树。 三、完全二叉树:如果一棵深度为k,有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示
B A C D E F G B A C D E F G 二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示
00 006006000 (a)满二叉树 (b)完全二叉树 问题:一个高度为h的完全二叉树最多有多少个结点?最 少有多少个结点?
B A C D E F G H I J K L M N O (a)满二叉树 B A C D E F G H I J (b)完全二叉树 问题:一个高度为h的完全二叉树最多有多少个结点?最 少有多少个结点?