树和二叉树的存储结构课件

10086510DataStructure树和二叉树3/1/20241树和线性结构对照线性结构树结构存在唯一的没有前驱

的"首元素"存在唯一的没有前驱的

"根结点"存在唯一的没有后继

的"尾元素"存在多个没有后继的

"叶子"其余元素均存在唯一

的"前驱元素"和唯一

的"后继元素"其余结点均存在唯一的

"前驱(双亲)结点"和多

个"后继(孩子)结点"3/1/20242二叉树二叉树的定义是n(n>=0)个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是二叉树。ABCDEIJGH根结点左子树右子树3/1/20243二叉树不是树的特例。特点每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。基本形态A

ABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空3/1/20244斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。

几种特殊形式的二叉树斜树的特点：ABCABC3/1/20245几种特殊形式的二叉树满二叉树深度为k且有2k-1个结点的二叉树。特点每一层上的结点数都是最大结点数；所有的分支结点的度数都为2；叶子结点都在同一层次上。1231145891213671014153/1/20246几种特殊形式的二叉树完全二叉树若对满二叉树的结点从上到下从左至右进行编号，则深度为k且有n个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1到n一一对应时。特点叶子结点只可能在层次最大的两层上出现；前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。1231145891267103/1/20247判断是否为完全二叉树，说明理由。1234567123456思考：满二叉树与完全二叉树的关系？3/1/20248在满二叉树中，从最后一个结点开始，连续去掉任意多个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点3/1/20249二叉树的性质性质1：在二叉树的第i层至多有2i-1个结点(i1)。性质2：深度为k的二叉树至多有2k-1个结点。性质3：对于任何一棵二叉树T，若其终端结点(叶子)数为

n0，度为1的结点数为n1，度为2的结点数n2，

则n0=n2+1。3/1/202410性质4：具有n个结点的完全二叉树的深度是

log2n

+1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序

编号，则对任一结点i(1in)，有：如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2；如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i；如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1。3/1/202411二叉树的存储结构顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素。完全二叉树，只要从根起按层序存储即可。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符(例如填充0)。顺序存储表示

#defineMAX_TREE_SIZE100 //最大结点数

Typedef TElemTypeSqBiTree[MAX_TREE_SIZE]; //0号根结点

SqBiTreebt;3/1/202412FBAGEDCHIJKL例如：bt[3]的双亲为└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。如何反映结点之间的逻辑关系？？A1B2C3D4E5F6G7H8I9J10K11L12完全二叉树的顺序表示3/1/202413一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用Ø表示，Ø表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。A1B2C3D4Ø5E6F7G8H9Ø10Ø11Ø12Ø13I14J15EBAFDCGHIJØØØØØ例如对于B结点而言：bt[2]的双亲为└1/2┘=1，即在bt[1]中(为A)；其左孩子在bt[2i]=bt[4]中(为D)；其右孩子在bt[2i+1]=bt[5]中(为Ø)。一般二叉树的顺序表示3/1/202414这种存储结构适合于完全二叉树和满二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。例如，深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，也需2k-1个单元，即有(2k-1)-k个单元被浪费。12k顺序存储的优缺点3/1/202415深度为4，有12个结点的完全二叉树的顺序存储123451011678912111210987654321123456789101112没有浪费3/1/202416深度为4，有7个结点的一般二叉树的顺序存储abcdefggf0000edcba1234567891011浪费4个3/1/202417深度为4，只有4个右孩子的二叉树的顺序存储0000400030002011234123456789101112131415浪费11个3/1/202418顺序存储结构适用于满二叉树和完全二叉树的存储。3/1/202419所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

链式存储结构3/1/202420^D

AB^C^^E^^F^Tlchilddatarchild结点结构BADCEF二叉链表3/1/202421ABCDEFG^^^^^^^^^三叉链表图示BACDEFG三叉链表lchilddata结点结构parentrchild3/1/202422链式存储结构二叉链表结点除包括元素自身的信息外，还包括指向其左、右子树的指针。即结点要包括数据域，左子树指针域和右子树指针域。二叉链表的存储表示

typedef

struct

BiTNode{

TElemType

data;

struct

BiTNode

*lchild,*rchild;

}BiTNode,*Bitree;

lchilddatarchild3/1/202423试用二叉链表的方法创建二叉树3/1/202424ABCDEFGABCDEFG^^^^^^^^在n个结点的二叉链表中，有n+1个空指针域。3/1/202425三叉链表结点包括数据域，左子树指针域、双亲域和右子树指针域。lchilddataparentrchild三叉链表的存储表示

typedef

struct

TriTNode{

TElemType

data;

struct

TriTNode