1、Page 12022-8-410086510Page 22022-8-4树和线性结构对照树和线性结构对照线性结构线性结构树结构树结构存在存在唯一的没有前驱唯一的没有前驱的的 首元素首元素 存在存在唯一的没有前驱的唯一的没有前驱的 根结点根结点 存在存在唯一的没有后继唯一的没有后继的的 尾元素尾元素 存在存在多个没有后继多个没有后继的的 叶子叶子 其余元素均存在其余元素均存在唯一唯一的的 前驱元素前驱元素 和唯一和唯一的的 后继元素后继元素 其余结点均存在其余结点均存在唯一的唯一的 前驱前驱(双亲双亲)结点结点 和和多多个个 后继后继(孩子孩子)结点结点 Page 32022-8-4q 二叉树的
2、定义二叉树的定义v是是n(n=0)n(n=0)个结点的有限集个结点的有限集，其子树分为，其子树分为互不相交的互不相交的两个集合，两个集合，分别称为分别称为左子树和右子树左子树和右子树，左子树和右子树也是二叉树左子树和右子树也是二叉树。ABCDEIJGH根结点根结点左子树左子树右子树右子树Page 42022-8-4v二叉树不是树的特例。二叉树不是树的特例。v特点特点每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2 2的结点的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。二叉树的子树有左、右之分，且其次序不能任意颠倒。v基本形态基本形态AABABABC空二空
3、二叉树叉树只有根结点只有根结点的二叉树的二叉树右子树右子树为空为空左子左子树为树为空空左、右子树左、右子树均非空均非空Page 52022-8-4斜树斜树1.所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树；2.所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1.在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。几种特殊形式的二叉树几种特殊形式的二叉树斜树的特点：斜树的特点：ABCABCPage 62022-8
4、-4几种特殊形式的二叉树几种特殊形式的二叉树q 满二叉树满二叉树v深度为深度为k k且有且有2 2k k-1-1个个结点的二叉树。结点的二叉树。v特点特点每一层上的结点数都是最大结点数；每一层上的结点数都是最大结点数；所有的分支结点的度数都为所有的分支结点的度数都为2 2；叶子结点都在同一层次上。叶子结点都在同一层次上。123114589121367101415Page 72022-8-4几种特殊形式的二叉树几种特殊形式的二叉树q 完全二叉树完全二叉树v若对满二叉树的结点从上到下从左至右进行编号，则深度为若对满二叉树的结点从上到下从左至右进行编号，则深度为k k且有且有n n个结点的二叉树称为
5、完全二叉树，当且仅当其每一个结点都与深度个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度为为k k的满二叉树的编号从的满二叉树的编号从1 1到到n n一一对应时。一一对应时。v特点特点叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；前前k-1k-1层中的结点都是层中的结点都是“满满”的，且第的，且第 k k 层的结点都集中在左层的结点都集中在左边。边。123114589126710Page 82022-8-41234567123456思考：满二叉树与完全二叉树的关系？思考：满二叉树与完全二叉树的关系？Page 92022-8-4在满二叉树中，从最后在满二叉
6、树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意多任意多个结点，即是个结点，即是一棵完全二叉树。一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树中的结点与满二叉树中的结点10不是同一个结点不是同一个结点Page 102022-8-4二叉树的性质二叉树的性质q 性质性质1：在二叉树的第在二叉树的第 i 层至多有层至多有 2i-1 个结点个结点(i1)。q 性质性质2：深度为深度为 k 的二叉树至多有的二叉树至多有 2k-1 个结点。个结点。q 性质性
7、质3 3：对于任何一棵二叉树对于任何一棵二叉树T T，若其终端结点，若其终端结点(叶子叶子)数为数为 n n0 0，度为，度为1 1的结点数为的结点数为n n1 1，度为，度为2 2的结点数的结点数n n2 2，则则n n0 0=n=n2 2+1+1。Page 112022-8-4q 性质性质4 4：具有具有n n个结点的完全二叉树的深度是个结点的完全二叉树的深度是 loglog2 2n n+1+1。q 性质性质5 5：如果对一棵有如果对一棵有n n个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序 编号，则对任一结点编号，则对任一结点i(1i(1 i i n)n)，有：，有：v如果
8、如果i=1i=1，则结点，则结点i i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1i1，则其则其双亲是双亲是 i/2i/2；v如果如果2in2in，则结点，则结点i i无左孩子；如果无左孩子；如果2i2i n n，则其，则其左孩子左孩子是是2 2i i；v如果如果2i+1n2i+1n，则结点，则结点i i无右孩子；如果无右孩子；如果2i+12i+1 n n，则其，则其右右孩子是孩子是2 2i+1i+1。Page 122022-8-4二叉树的存储结构二叉树的存储结构q 顺序存储结构顺序存储结构v用一组用一组地址连续的存储单元存储地址连续的存储单元存储二叉树中的数据元素。二叉树中的数据
9、元素。完全二叉树完全二叉树，只要，只要从根起按层序存储从根起按层序存储即可。将完全二叉树上编即可。将完全二叉树上编号为号为 i i 的结点元素存储在一维数组中下标为的结点元素存储在一维数组中下标为 i-1 i-1 的分量中。的分量中。一般的二叉树一般的二叉树，可，可对照完全二叉树的编号进行相应的存储对照完全二叉树的编号进行相应的存储，但，但在在没有结点的分量中需填充空白字符没有结点的分量中需填充空白字符(例如填充例如填充0)。v顺序存储表示顺序存储表示#define MAX_TREE_SIZE 100#define MAX_TREE_SIZE 100 /最大结点数最大结点数TypedefTyp
10、edef TElemType SqBiTreeMAX_TREE_SIZETElemType SqBiTreeMAX_TREE_SIZE;/0/0号根结点号根结点SqBiTree btSqBiTree bt;Page 132022-8-4FBAGEDCHIJKL例如：例如：bt3的双亲为的双亲为3/2=1，即在，即在bt1中；中；其左孩子在其左孩子在bt2i=bt6中；中；其右孩子在其右孩子在bt2i+1=bt7中。中。如何反映结点之如何反映结点之间的逻辑关系？间的逻辑关系？A1B2C3D4E5F6G7H8I9J10K11L12&完全二叉树的顺序表示完全二叉树的顺序表示Page 142022-8
11、-4 一般二叉树也按完全二叉树形式存储，只有增添一些并不一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点存在的空结点(用用表示，表示，表示该处没有元素存在，仅仅为了表示该处没有元素存在，仅仅为了好理解好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。顺序存储。A1B2C3D45E6F7G8H910111213I14J15EBAFDCGHIJ例如对于例如对于B结点而言：结点而言：bt2的双亲为的双亲为1/2=1，即在，即在bt1中中(为为A)；其左孩子在其左孩子在bt2i=bt4中中(为为D)；其右孩子在其右孩子在bt
12、2i+1=bt5中中(为为)。&一般二叉树的顺序表示一般二叉树的顺序表示Page 152022-8-4 这种存储结构适合于完全二叉树和满二叉树，既不浪这种存储结构适合于完全二叉树和满二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。存储空间的浪费。例如，深度为例如，深度为k，且只有，且只有k个结点的右单枝树个结点的右单枝树(每个非叶每个非叶结点只有右孩子结点只有右孩子)，也需，也需2k-1个个单元，即有单元，即有(2
13、k-1)-k个单元个单元被浪费。被浪费。12k&顺序存储的优缺点顺序存储的优缺点Page 162022-8-412345101167891211 1210987654321 1 2 3 4 5 6 7 8 9 10 11 12没有浪费没有浪费Page 172022-8-4abcdefggf0000edcba 1 2 3 4 5 6 7 8 9 10 11浪费浪费4个个Page 182022-8-400004000300020112341 2 3 4 5 6 7 8 9 10 11 12 13 14 15浪费浪费11个个Page 192022-8-4顺序存储结构适用于满二叉树和完全二叉树的存储。
14、顺序存储结构适用于满二叉树和完全二叉树的存储。Page 202022-8-4 所谓链式存储是指，用链表来表示一棵二叉树，即用链所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有两链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：地址。其定义如下：typedef struct BiTNodetypedef struct BiTNode El
15、emType ElemType data;data;struct BiTNode struct BiTNode*lchild,lchild,*rchildrchild;BiTNode,BiTNode,*BiTreeBiTree;&链式存储结构链式存储结构Page 212022-8-4 D A B C E F Tlchilddatarchild结点结构结点结构BADCEF&二叉链表二叉链表Page 222022-8-4 A B C D E F G三叉链表图示三叉链表图示BACDEFG&三叉链表三叉链表lchild data结点结构结点结构parent rchildPage 232022-8-4链
16、式存储结构链式存储结构q 二叉链表二叉链表v结点除包括元素自身的信息外，还包括指向其左、右子树的指针。结点除包括元素自身的信息外，还包括指向其左、右子树的指针。即结点要包括即结点要包括数据域，左子树指针域和右子树指针域数据域，左子树指针域和右子树指针域。v 二叉链表的存储表示二叉链表的存储表示typedef struct BiTNodetypedef struct BiTNodeTElemTypeTElemType data;data;struct BiTNodestruct BiTNode *lchild,lchild,*rchildrchild;BiTNodeBiTNode,*Bitree
17、Bitree;lchilddatarchildPage 242022-8-4试用二叉链表的方法创建二叉树试用二叉链表的方法创建二叉树Page 252022-8-4ABCDEFG AB C D E F G在在n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空指针域个空指针域。Page 262022-8-4q 三叉链表三叉链表v结点包括结点包括数据域，左子树指针域、双亲域和右子树指针域数据域，左子树指针域、双亲域和右子树指针域。lchilddataparentrchildv三叉链表的存储表示三叉链表的存储表示typedef struct TriTNodetypedef struct TriTNodeTElemTypeTElemType datadata;struct TriTNodestruct TriTNode *lchild,lchild,*rchildrchild,*parentparent;TriTNode TriTNode,*TritreeTritree;Page 272022-8-4 A B C D E F GABCDEFG
