树和二叉树的存储结构

《树和二叉树的存储结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、10086510DataStructure树和二叉树8/13/20211树和线性结构对照线性结构树结构存在唯一的没有前驱的"首元素"存在唯一的没有前驱的"根结点"存在唯一的没有后继的"尾元素"存在多个没有后继的"叶子"其余元素均存在唯一　的"前驱元素"和唯一　的"后继元素"其余结点均存在唯一的"前驱(双亲)结点"和多　个"后继(孩子)结点"8/13/20212二叉树二叉树的定义是n(n>=0)个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是二叉树。ABCDEIJG

2、H根结点左子树右子树8/13/20213二叉树不是树的特例。特点每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。基本形态AABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空8/13/20214斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。几种特殊形式的二叉树斜树的特点：ABCABC8/13/2

3、0215几种特殊形式的二叉树满二叉树深度为k且有2k-1个结点的二叉树。特点每一层上的结点数都是最大结点数；所有的分支结点的度数都为2；叶子结点都在同一层次上。1231145891213671014158/13/20216几种特殊形式的二叉树完全二叉树若对满二叉树的结点从上到下从左至右进行编号，则深度为k且有n个结点的二叉树称为完全二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1到n一一对应时。特点叶子结点只可能在层次最大的两层上出现；前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。1

4、231145891267108/13/20217判断是否为完全二叉树，说明理由。1234567123456思考：满二叉树与完全二叉树的关系？8/13/20218在满二叉树中，从最后一个结点开始，连续去掉任意多个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点8/13/20219二叉树的性质性质1：在二叉树的第i层至多有2i-1个结点(i1)。性质2：深度为k

5、的二叉树至多有2k-1个结点。性质3：对于任何一棵二叉树T，若其终端结点(叶子)数为n0，度为1的结点数为n1，度为2的结点数n2，则n0=n2+1。8/13/202110性质4：具有n个结点的完全二叉树的深度是log2n+1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2；如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i；如果2i+1>n，则结点i无右孩子；如果2i+1

6、n，则其右孩子是2i+1。8/13/202111二叉树的存储结构顺序存储结构用一组地址连续的存储单元存储二叉树中的数据元素。完全二叉树，只要从根起按层序存储即可。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符(例如填充0)。顺序存储表示#defineMAX_TREE_SIZE100//最大结点数TypedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号根结点SqBiTr

7、eebt;8/13/202112FBAGEDCHIJKL例如：bt[3]的双亲为└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。如何反映结点之间的逻辑关系？A1B2C3D4E5F6G7H8I9J10K11L12完全二叉树的顺序表示8/13/202113一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用Ø表示，Ø表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。A1B2C3D4Ø5E6

8、F7G8H9Ø10Ø11Ø12Ø13I14J15EBAFDCGHIJØØØØØ例如对于B结点而言：bt[2]的双亲为└1/2┘=1，即在bt[1]中(为A)；其左孩子在bt[2i]=bt[4]中(为D)；其右孩子在bt[2i+1]=bt[5]中(为Ø)。一般二叉树的顺序表示8/13/202114这种存储结构适合于完全二叉树和满二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右