二叉树结点的子树要区分左子树和右子树,即 使只有一棵子树也要进行区分,说明它是左子 树,还是右子树。这是二叉树与树的最主要的 差别。图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;