软件技术基础_树课件.ppt

《软件技术基础_树课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性结构的逻辑特征：有且只有一个开始数据元素有且只有一个终点数据元素中间元素有且只有一个直接前趋和一个直接后继非线性结构的逻辑特征：一个数据元素可能有多个直接前趋和多个直接后继。非线性数据结构类型：树、二叉树、图1.3非线性结构一、树的基本概念树结构是一种非线性结构最多只有一个直接前趋，可能有多个直接后继。1、树的定义：①由n(n>0)个结点元素组成的有限集合T；②有且仅有一个根结点（root）；③其余结点可分为互不相交的子集，每个子集又是一棵树，称为root的子树（subtree）。1.3.1树ABDKEFLMJIHGCT1T2T3root2、树的术语

2、：●结点：树中的元素。●根结点：唯一的一个无前趋的元素。●叶结点（终端结点）（leaf）：无后继，仅有一个直接前趋。●分支结点（非终端结点）：有且仅有一个直接前趋，一个或多个直接后继。根结点分支结点叶结点●子结点：某结点的直接后继称为该结点的子结点。●父结点：某结点的直接前驱称为该结点的父结点。●孩子、双亲、兄弟、堂兄弟、祖先、子孙孩子兄弟祖先子孙双亲孩子A例：A节点的孩子堂兄弟●结点的度：结点拥有的子树数目。●树的度：树内各结点的度的最大值。●树的深度：树中结点的最大层次数。ABDKEFLMJIHGCT1T2T3root●结点的层次：从根开始计算，根为

3、第一层，根的孩子为第二层，依此类推；若某结点在第n层，则其子树的根在第（n+1）层。●路径：从一个结点出发到另一结点所经历的所有结点序列。例：ADHM；BACG●有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树。反之称为无序树。●森林：(m≥0)棵互不相交的树的集合。森林二、树的存储1、顺序存储结构：依次存放树中的各个结点AFEDCBABCDEF结论：顺序存储无法表示结点之间的逻辑关系∵连续线性的下标不能反映树的分支关系（非线性）2、链式存储结构：①多重链表：……linknlink2link1data子树1子树2子树n问题：指针域的个数？

4、（结点异构型和结点同构型）链点树结点分支关系多个指针，分别描述②孩子兄弟表示法——二叉链表：每个结点有两个指针域：一个指向该结点的第一个孩子，另一个指向该结点的下一个兄弟。link2link1data第一个孩子下一个兄弟一、定义（递归定义法）二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。1.3.2二叉树二、特点●二叉树可为空●二叉树是有序树●结点的度≤2●注意与树的区别三、二叉树的形态a)空树b)仅有一个根结点c)仅有左子树d)仅有右子树e)左、右子树都非空四、二叉树的性质1）在第i层上最多有2i-1个结点2）深

5、度为k的二叉树，最多有2k-1个结点3）设叶子结点个数为n0，度为2的结点数为n2，则：n0＝n2+1证明：设n1为度为1的结点，则结点总数为n=n0+n1+n2；又分支总数为：b=n1+2n2；而n=b+1；所以n0=n2+1。五、几种特殊二叉树1）满二叉树：每一层上的结点数都是最大结点数。特点：所有的分支结点都有2个孩子；所有的叶子结点都在同一层上；若深度为k，则一定有2k－1个结点。2）完全二叉树：深度为k的完全二叉树，前k－1层是满二叉树，第k层的结点个数<2k－1，且第k层的结点都集中在该层最左边的位置上，没有间断。完全二叉树的性质：①n个结点

6、的完全二叉树，其深度为：log2n＋1②n个结点的完全二叉树，对于它的第i个结点（1≤i≤n）（结点编号顺序为从上到下，从左到右）：i=1，该结点为根结点，无双亲i>1，其双亲为2i>n，则i无左孩子；否则，左孩子为2i2i+1>n，则i无右孩子；否则，右孩子为2i+1i/2123456③关于完全二叉树的其他描述形式：如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1满二叉树完全二叉树非完全二叉树六、二叉树的存

7、储1）顺序存储结构：所有结点依次存放在一块连续的内存空间中，结点按照从上到下、从左到右的次序排成线性序列，序列中的相对位置反映结点之间的逻辑关系。特点：只适合满二叉树和完全二叉树一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来，以维持结点编号之间的父子换算关系——会造成空间的浪费。实现：用一维数组2）链式存储结构：结点定义：LchilddataRchild二叉链表构成typedefstructbtnode{elemtypedata;structbtnode*Lchild;structbtnode*Rchild;}bt

8、reenode；结点结构的c语言描述：Lchild(Rchild)：左(右)指针