数据结构第5章 树ppt课件.ppt

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

1、第五章树和二叉树本章要点二叉树的定义与主要性质二叉树顺序存储结构与二叉链表存储结构二叉树的常见算法树、森林与二叉树的转换5.1树的定义及相关术语树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。树形结构应用非常广泛，特别是在大量数据处理方面，如在文件系统、目录组织、人事管理、家谱等方面，显得更加突出。树是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。否则满足下面两个条件：（1）有且仅有一个树的根结点，根结点没有前驱结点。（2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每个子集T1，

2、T2，…，Tm称为这个根结点的子树。5.1.1树的定义下列不是树结构5.1.2基本术语（1）结点的度：一个结点的子树个数称为该结点的度。（2）叶结点：度为0的结点，也称为终端结点。（3）分支结点：度不为0的结点，也称为非终端结点。（4）孩子结点：一个结点的直接后继称为该结点的孩子结点。（5）双亲结点：一个结点的直接前驱称为该结点的双亲结点。（6）兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。（7）祖先结点：一个结点的祖先结点是指从根结点到该结点所经分支上的所有结点。（8）子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。（9）树的度：树中所有结点的度的最大值。（10

3、）结点的层次：从根结点开始定义，根结点的层次为l，根的直接后继的层次为2，依此类推。（11）树的高度(深度)：树中所有结点的层次的最大值。（12）路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列,结点序列为路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。（13）有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。（14）森林：m(m＞0)棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。5.2二叉树5.2.1二叉树的定义和基本操作1.二叉树的定义二叉树也称为二次树

4、或二分树,它是n(n≥0)个结点有限的集合。n=0时，称为空二叉树n≠0时，二叉树由一个根结点及两棵互不相交、分别称为左子树和右子树的二叉树组成。5.2.2二叉树的主要性质性质1二叉树第i层上的结点数目最多有2i-1个（i≥1）。性质2一棵深度为k的二叉树中，最多有2k－1个结点。性质3在二叉树中，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点：叶子结点只能

5、出现在最下层和次下层，且最下层的叶子结点集中在树的左部。一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。1.满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。2.完全二叉树性质5具有n个结点的完全二叉树，按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则任意i的结点有：（1）i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。（2）2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点

6、无左孩子。（3）2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。性质4具有n个结点的完全二叉树的深度k为[log2n]+1。（1）顺序存储结构二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。图5-8给出的完全二叉树的顺序存储示意。5.2.3二叉树的存储结构最坏的情况是右单支树，如图5-10所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。AA二叉树的顺序存储表示可描述为：#defineMaxSize50/*二叉树的最大结点数*/typedefDataTypeBTree[MaxSize]/*

7、0号存根结点*/BTreebt;（2）链式存储结构二叉树的链式存储结构是：用链表来表示一棵二叉树，通常有下面两种形式。1）二叉链表存储链表中每个结点由三个域组成，数据、两个指针域左孩子和右孩子。结点的存储的结构为：2）三叉链表存储每个结点由四个域组成，具体结构为：二叉树的二叉链表存储为：typedefcharTreeData;//结点数据类型typedefstructtnode{//结点定义intdata;structtnode*lChild,*rchild;//左右孩子}tno