清华大学：《数据结构》课程教材PPT教学课件（C语言版）第六章 树和二叉树（6-3）二叉树

二叉树结点的子树要区分左子树和右子树,即 使只有一棵子树也要进行区分,说明它是左子 树,还是右子树。这是二叉树与树的最主要的 差别。图6.8列出二叉树的5种基本形态,图 6.8(C)和图6.8(d)是不同的两棵二叉树。 A A A B B B (a) (b) 根和空的(c) 空二又树左右子树根和左子树根和右子树根和左右子树 图68二叉树的5种形式

(a) 空二叉树 A A B A B A B C (b) 根和空的 左右子树 (c) 根和左子树 (d) 根和右子树 (e) 根和左右子树 图6.8 二叉树的5种形式 二叉树结点的子树要区分左子树和右子树，即 使只有一棵子树也要进行区分，说明它是左子 树，还是右子树。这是二叉树与树的最主要的 差别。图6.8列出二叉树的5种基本形态，图 6.8(C) 和图6.8（d）是不同的两棵二叉树

63二叉树 二叉树的存储结构 顺序存储结构 用一组地址连续的存储单元,以层序顺序存放二叉树 的数据元素,结点的相对位置蕴含着结点之间的关系。 1234567891011 ABC DEFGO 00JO 完全二叉树A bt3的双亲为L3/2=1, B 即在b1中; 其左孩子在bt2=bt|6中 其右孩子在b2+1-b7]中

6.3 二叉树 完全二叉树 D C E F G B A 三、二叉树的存储结构 ⒈ 顺序存储结构 用一组地址连续的存储单元，以层序顺序存放二叉树 的数据元素， 结点的相对位置蕴含着结点之间的关系。 • bt[3]的双亲为└3/2┘=1， 即在b t[1]中； • 其左孩子在bt[2i]=bt[6]中； • 其右孩子在bt[2i+1]=bt[7]中。 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 0

63二叉树 一般二叉树也按完全二叉树形式存储没结点 处用0表示。 二叉树 A 1234567891011 B ABCDEO0 O DoFGoololol I E 这种存储结构适合于完全二叉树,既不浪费存 储空间,又能很快确定结点的存放位置、以及结点 的双亲和左右孩子的存放位置,但对一般二叉树, 可能造成存储空间的浪费

6.3 二叉树 这种存储结构适合于完全二叉树，既不浪费存 储空间，又能很快确定结点的存放位置、以及结点 的双亲和左右孩子的存放位置，但对一般二叉树， 可能造成存储空间的浪费。 D 二叉树 C F G E B A 1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 0 0 0 0 一般二叉树也按完全二叉树形式存储,没结点 处用0表示

63二叉树 例如,深度为k,且只有k个结点的右单枝树(每个 非叶结点只有右孩子),需2k-1个单元,即有2k-1-k 个单元被浪费

6.3 二叉树 例如，深度为k，且只有k个结点的右单枝树(•每个 非叶结点只有右孩子)，需2 k-1个单元，即有2 k-1-k 个单元被浪费。 1 k

63二叉树 2.链式存储结构 设计不同的结点结构,可以构成不同的链式存储 结构。常用的有: 二叉链表 叉链表 ·线索链表用空链域存放指向前驱或后继的线索 二叉树的二叉链表存储表示 Typedef struct BiNOde TelemType data struct binode *lchild. krchild t BiTNode, *BiTree

6.3 二叉树 ⒉ 链式存储结构 设计不同的结点结构，可以构成不同的链式存储 结构。常用的有： • 二叉链表 • 三叉链表 • 线索链表 用空链域存放指向前驱或后继的线索 二叉树的二叉链表存储表示 Typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;

63二叉树 二叉链表的结点结构 Child data rchild 二叉树 二叉链表□A B ∧C∧ B E ∧D∧∧E∧

6.3 二叉树 二叉链表的结点结构 lchild data rchild D 二叉树 C E B A A B C ∧ D ∧ ∧ E ∧ ∧ ∧ 二叉链表

63二叉树 三叉链表的结点结构 Child data parent rchild 二叉树 三叉链表A B B E 入D因B下

6.3 二叉树 三叉链表的结点结构 lchild data parent rchild D 二叉树 C E B A A B C ∧ D ∧ ∧ E ∧ ∧ ∧ 三叉链表 ∧

63二叉树 性质6.含有N个结点的二叉链表中,有N+1个空链域。 证明:设二叉树中度为的结点数为ni,二叉树中总结点数为N,因为二叉 树中所有结点均小于或等于2,所以有: N=n0+n1+n2 又由二叉树的链式存储结构定义可知,度为1的结点的空链域个数为1,度 为2的结点的空链域个数为0,度为0的结点的空链域个数为2,设含有N个结 点的二叉树的二叉链表中空链域的个数为M,则有: M=2*n0+1*n1+0*n2=2米n0+n1 又因为:n0=n2+1③ 由①、②、③可得: M=2*n0+n1 n0+n1+n0 n0+n1+n2+1 =N+1 命题得证

6.3 二叉树 性质6. 含有N个结点的二叉链表中，有N+1个空链域。 证明：设二叉树中度为i的结点数为ni，二叉树中总结点数为N，因为二叉 树中所有结点均小于或等于2，所以有： N＝n0＋n1＋n2 ① 又由二叉树的链式存储结构定义可知，度为1的结点的空链域个数为1，度 为2的结点的空链域个数为0，度为0的结点的空链域个数为2，设含有N个结 点的二叉树的二叉链表中空链域的个数为M，则有： M＝2* n0＋1*n1＋0*n2= 2* n0＋n1 ② 又因为： n0＝n2＋1 ③ 由①、②、③ 可得： M＝2* n0＋n1 ＝n0+n1+n0 ＝n0+n1+n2+1 ＝N+1 命题得证

64遍历二叉树和线索二叉树 遍历二叉树 遍历二叉树是指按一定的规对二叉树的每个结 点,坊应且仅访问一次的处理过程。 访问是一种抽象操作,是对结点的某种处理,例如 可以是求结点的度、或层次、打印结点的信息,或做 其他任何工作。 次遍历后,使树中结点的非线性排列,按访问的 先后顺序变为某种线性排列。 遍历的次序:若设二叉树根为D,左子树为L,右子 树为R,并限定先左后右,则有以下三种遍历次序: LDR中序遍历;LRD后序遍历;DLR先序遍历

6.4 遍历二叉树和线索二叉树 一、遍历二叉树 遍历二叉树是指按一定的规律对二叉树的每个结 点，访问且仅访问一次的处理过程。 • 访问是一种抽象操作，是对结点的某种处理，例如 可以是求结点的度、或层次、打印结点的信息，或做 其他任何工作。 • 一次遍历后，使树中结点的非线性排列，按访问的 先后顺序变为某种线性排列。 • 遍历的次序：若设二叉树根为D，左子树为L，右子 树为R，并限定先左后右，则有以下三种遍历次序： LDR 中序遍历；LRD 后序遍历；DLR 先序遍历