数据结构——树

《数据结构——树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章树树与图属于非线性结构4.1树的概念4.1树的概念——树型结构应用举例“资源管理器”界面。4.1树的概念——树的结构定义树(Tree)是n(n>=0)个结点的有限集合。当n=0时，称为空树；当n>0时，称为非空树。在任意一棵非空树中：（1）有且仅有一个特定的结点，称为树根(root)，它没有直接前驱，但有零个或多个直接后继（2）当n>1时，其余结点被划分成m个互不相交的子集，每个子集又是一棵树，被称为子树(subtree)。4.1树的概念——树的表示方法（层次）abcdghijfemlk4.1树的概念——树的表示方法（集合）abcdeklfghm

2、ij4.1树的概念——树的表示方法（凹凸图）abeklfcgdhmij4.1树的概念——树的表示方法（广义表）(a(b(e(k,l),f),c(g),d(h(m),i,j)))4.1树的概念——基本术语结点结点的度，树的度叶子(终端结点)非终端结点结点的层次树的深度有序树，无序树森林abcdghijfemlk4.1树的概念——基本术语孩子双亲兄弟祖先子孙堂兄弟abcdghijfemlk4.2二叉树的基本概念和主要性质二叉树定义二叉树由n(n>=0)个元素组成。当n=0时，为空二叉树；当n>0时，有且仅有一个元素为根，其余结点分成最多两个互不相交的子集，子

3、集有左右顺序，每个子集又是一个二叉树。4.2二叉树的概念和性质——定义4.2二叉树的概念和性质——二叉树的五种形态RLLR例画出具有3个结点的树和二叉树的所有不同形态。如图所示：(1)具有3个结点的树有2种不同的形态。(2)具有3个结点的二叉树有5种不同的形态。3个结点的所有树的不同形态3个结点的所有二叉树的不同形态二叉树性质（性质1）在二叉树的第i层上至多有2i-1个结点。证明：(数学归纳法)i=1，只有根结点，2i-1=20=1成立设1j

4、——二叉树性质二叉树性质（性质2）深度为h的二叉树至多有2h-1个结点。证明:利用性质120+21+22+23+...+2h-1=2h-14.2二叉树的概念和性质——二叉树性质二叉树性质（性质3）对于一个非空的二叉树，若其具有n0个叶子结点，有n2个度为2的结点，则有:n0=n2+1证明:n=n0+n1+n2(1)B=n1+2n2;n=B+1n=n1+2n2+1(2)(2)-(1)得:n0=n2+14.2二叉树的概念和性质——二叉树性质二叉树性质（性质4）具有n个结点的完全二叉树的深度为log2n+1。证明:设深度为k,则有:2k-1-1

5、-12k-1<=n<2kk-1<=log2n1，则序号为i的结点的双亲结点序号为i/2；如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i；如2×i＋1>n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。123454.2二叉树的概念和性质——二叉树性质满二叉树深度为k，且有2k-1个结点的二叉树。4.2二叉

6、树的概念和性质——满二叉树完全二叉树:一棵深度为h，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树。满二叉树完全二叉树1234567123454.2二叉树的概念和性质——完全二叉树另外，还有两种特殊的二叉树，平衡二叉树和二叉排序树。二叉排序树将在后面介绍，这里只介绍平衡二叉树的概念。二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。例下图中有两棵二叉树，试判定其是否是平衡二叉树？解：二叉树(a

7、)是平衡二叉树。二叉树(b)中结点C的平衡因子为2，大于1，故不是平衡二叉树。两棵二叉树4.3二叉树的存储顺序存储结构：顺序存储就是用一组地址连续的存储单元来存放一棵二叉树的结点。适用于存储完全二叉树或满二叉树。12345123454.3二叉树的存储——顺序存储结构二叉树顺序存储结构定义==================#defineMaxSize100typedefintDataType;typedefstruct{DataTypedata[MaxSize];intnum；}BTree;4.3二叉树的存储——顺序存储结构lchilddatarchil

8、dlchilddataparentrchild链式存储结构：二叉树的链式存储结构