第六章。树和二叉树.pptVIP

第六章 树和二叉树 第一节 树的定义和基本术语 一、树的概念 树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是n个结点的有限集合，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。 二、树的基本术语 树的结点：包含一个数据元素及若干指 向子树的分支；孩子结点：结点的子树的根称为该结点 的孩子；双亲结点：B 结点是A 结点的孩子，则A 结点是B 结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；祖先结点: 从根到该结点的所经分支上的所有结点 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙 结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度： 树中最大的结点度。叶子结点：也叫终端结点，是度为 0 的结点；分枝结点：度不为0的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序； 森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根 ，其子树构成一个森林；一个森林增加一个根结点成为树。 三、树的应用 例如：单位行政机构的组织关系。计算机的文件系统不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。家族族谱。 第二节 二叉树 一、二叉树的定义 二叉树（Binary Tree）或为空树，或是每个点至多只有两棵子树（即二叉树中不存在度大于2的结点）并且，二叉树的子树在左右之分，其次序不能任意颠倒。 二叉树的5种基本形态： 二、二叉树的性质 性质1 在二叉树的第i 层上最多有2i-1个结点 性质2 深度为k的二叉树最多有 2k-1 个结点 性质3 设二叉树终端结点数为n0，度为2的结点为n2，则n0 = n2 +1 二种特特殊的二叉树：满二叉树和完全二叉树 满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树； 对满二叉树进行编号，约定从根结点开始，自左向右编号，自上向下编号，可得出完全二叉树定义。 完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树； 三、二叉树的存贮结构 1 二叉树的顺序结构 满二叉树或完全二叉树的顺序结构 用一组连续的内存单元，按编号顺序依 次存储完全二叉树的元素.例如，用一维 数组bt[ ]存放一棵完全二叉树，将标号 为 i 的结点的数据元素存放在分量 bt[i-1]中。存储位置隐含了树中的关系，树中的关系是通过完全二叉树的性质实现的。例如，bt[5]（i=6)的双亲结点标号是k=trunc(i/2)=3,双亲结点所对应的数组分量bt[k-1]=bt[2] 2、二叉树的链式存储结构 二叉链表中每个结点包含三个域：数据域、左指针域、右指针域 第三节 二叉树的遍历 遍历：按某种有哪些信誉好的足球投注网站路径访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。 一、二叉树的三种遍历方式 先序遍历、中序遍历、后序遍历 先序遍历（即按根、左、右方式遍历） 若二叉树为空，则空操作，否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树； 2.中序遍历（即按左、根、右方式遍历） 若二叉树为空，则空操作，否则 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 例：用先序遍历、中序遍历、后序遍历下图所示的二叉树 课堂练习 第四节 树的存贮 3 哈夫曼树的构造 例：构造以W=（5，15，40，30，10）为权的哈夫曼树。 构造哈夫曼树的步骤： 1．根据给定的n个权值 ，构造n棵只有一个根结点的二叉树， n个权值分别是这些二叉树根结点的权。设F是由这n棵二叉树构成的集合 2．在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和； 3．从F中删除这两颗树，并将新树加入F； 4．重复 2、3，直到F中只含一颗树为止； 40 30 60 15 5 10 15 30 30 5 10 15 40 40 30 15 5 10 15 40 30 30 15 5 10 15 40 100 30 60 15