数据结构树和二叉树 |
您所在的位置：网站首页 › 数据结构第二版ppt › 数据结构树和二叉树 |
数据结构树和二叉树
|
整本书的知识点，点击右方链接：整本书笔记知识点 文章目录 五、树和二叉树5.1、树和二叉树的定义5.1.1、树的定义5.1.2、树的基本术语5.1.3、二叉树的定义 5.2、案例引入5.3、树和二叉树的抽象数据类型定义5.4、二叉树的性质和存储结构5.4.1、二叉树的性质5.4.2、二叉树的存储结构 5.5、遍历二叉树和线索二叉树5.5.1、遍历二叉树5.5.2、线索二叉树 5.6、树和森林5.6.1、树的存储结构5.6.2、森林与二叉树的转换5.6.3、树和森林的遍历 5.7、哈弗曼树及其应用5.7.1、哈弗曼树的基本概念5.7.2、哈夫曼树的构造算法5.7.3、哈夫曼编码 二叉树案例第五章小结第五章习题
五、树和二叉树 5.1、树和二叉树的定义 5.1.1、树的定义 树是一种非线性的数据结构,它是由n个有限结点组成有层次关系的集合. 树具有以下特点，可以根据这些特点来判断一个数据结构是否是树 •每个结点具有0个或多个子结点 •每个子结点只有一个父结点 •没有前驱的结为根结点 •除了根结点外，每个子结点又可以由m棵不相关的子树组成
每个结点最多有一个父结点
树的度：树内各结点度的最大值，即上图 D 结点的度就是此树的度 叶子：度为 0 的节点称为叶子或终端节点 结点的层次和树的深度
二叉树与数主要有以下区别： 二叉树每个结点至多只有两颗子树(即二叉树中不能存在度大于 2 的结点)二叉树的子树有左右之分，其次序不能任意颠倒即使树中某结点只有一棵子树，也要区分它是左子树还是右子树
略 5.3、树和二叉树的抽象数据类型定义 数据对象集：一个有穷的结点集合。 若不为空，则由根结点和其左、右二叉子树组成。 操作集： BT ∈ BinTree, Item ∈ElementType，重要操作有： Boolean IsEmpty( BinTree BT )： 判别BT是否为空； void Traversal( BinTree BT )：遍历，按某顺序访问每个结点； BinTree CreatBinTree( )：创建一个二叉树。常用的遍历方法有： void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；void InOrderTraversal( BinTree BT )： 中序—左子树、根、右子树；void PostOrderTraversal( BinTree BT )：后序—左子树、右子树、根void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右 5.4、二叉树的性质和存储结构 5.4.1、二叉树的性质
性质1：在二叉树的第i层上至多有2i-1个结点（i>=1） 性质2：深度为k的二叉树至多有2k-1个结点（k>=1） 性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则n0 = n2+1 一棵二叉树，除了终端结点（叶子结点），就是度为1或2的结点。假设n1表示度为1的结点数，则树 T 的结点总数 n=n0+n1+n2 ,我们再换个角度，看一下树T的连接线数，除了根节点，其他结点都有一根线表示分支进入，所以连接线数为结点总数减去1。按连接线树算的话：n-1=n1+2n2，可推导出n0+n1+n2-1 = n1+2n2，继续推导可得n0 = n2+1 满二叉树：深度为 k 且含有 2k-1个结点
性质4：具有n个结点的完全二叉树的深度为[log2n ] + 1 性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n ] + 1）的结点按层序编号（从第1层到第[log2n ] + 1层，每层从左到右），对任一结点i(1n,则结点 i 无孩子（结点i为叶子结点）；否则其左孩子是结点 2i 如果2i+1>n,则结点 i 无右孩子；否则其右孩子是结点 2i+1
①、顺序存储结构
二叉树的顺序存储结构缺点很明显：不能反应逻辑关系；对于特殊的二叉树（左斜树、右斜树），浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。 ②、链式存储结构
二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次
如果限定先左后右，则二叉树遍历方式有三种： 先序（根）：DLR； 中序（根）：LDR ；后序（根）：LRD
中序遍历的递归算法： 中序遍历的非递归算法：
根据遍历序列确定二叉树
根据前序可知 A 为根节点，再看中序可知 BC 是在根节点 A 左子树，EDGHFI 是在根节点 A 右子树 再看前序和中序可知，B 为 根节点 A 的左孩子，C为B的右孩子，由此类推。 已知一棵二叉树的后序序列和中序序列，分别是DECBHGFA 和BDCEAFHG 是否可以唯一确定这棵树？ ①由后序遍历特征，根结点必在后序序列尾部（即A）； ②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）； ③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子； 二叉树遍历算法的应用
对于n个结点的二叉树，则在二叉链存储结构中就会有n+1个空链域 对于一个有 n 个结点的二叉链表，每个结点指向左右孩子的两个指针域，故共有 2n 个指针域，而 n 个结点的二叉树共有 n-1 条分支，即存在 2n-(n-1) = n+1 个空链域 如果一个结点的左孩子为空，则指向它的前驱结点。 如果一个结点右孩子为空，则指向它的后继。 怎么理解这句话，我们来看一个例子
它的后序遍历为: DBEFCA 那么它的后序线索二叉树是怎么画的呢？ 我们根据它的后序遍历的结果来画后序线索二叉树 先来看D： D的左孩子为空，则指向它的前驱，它没有前驱。 D的右孩子为空，则指向它的后继，也就是B。
再来看B：B的左孩子为空，则指向它的前驱，它的前驱根据后序遍历的结果是D，所以B的左孩子指向D B的右孩子不为空
再来看E，E的左孩子为空，则指向它的前驱结点B,E的右孩子为空，则指向它的后继结点F
再来看F，它的左孩子为空，则指向它的前驱结点E。它的右孩子为空，则指向它的后继节点C
线索二叉树的结点形式： LTag是在 lchild 不存储指针的时候才有其作用，说到底，是利用那 n-1 个空链域存储LTag和RTag，并没有开辟新的内存空间用来存储前驱和后继
和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
线索二叉树的遍历和构造伪码点超链接 线索二叉树的遍历和构造伪码 5.6、树和森林 5.6.1、树的存储结构双亲表示法
略 孩子兄弟表示法(常用)
（1）转换：把每棵树转换为二叉树。（即根结点没有右孩子的二叉树） （2）连接：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。 （3）旋转
二叉树转换为森林
（1）逆旋转
（2）抹线：从根结点开始，依次抹掉结点与右孩子的连线，直到结点没有右孩子为止
（3）转换：将二叉树转换成树（也可以省略该步骤）
1、树的遍历前面写了 2、森林的遍历 先序遍历森林。 若森林非空，访问森林的第一棵树的根结点。先序遍历第一棵树中根结点的子树先序遍历除去掉遍历过的树的森林中序遍历森林：普通的树构成的森林是不存在中序遍历的，这里的中序遍历必然指代的是化成二叉树的森林。 后序遍历也可以相似定义 5.7、哈弗曼树及其应用 5.7.1、哈弗曼树的基本概念哈弗曼树又被称为最优树 路径：从一个结点到另一个结点之间的分支序列 路径长度：从一个结点到另一个结点所经过的分支数目 结点的权：根据应用的需要可以给树的结点赋权值 带权路径长度：从根到该结点的路径长度与该结点权的乘积 树的带权路径长度：树中所有叶子结点的带权路径之和 哈夫曼树：由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树 哈弗曼树不存在度为 1 的结点。 n个叶子结点的哈弗曼树有 2n-1 个结点 在构造哈弗曼树时，是从叶子结点向根节点的方向进行的，每次都是两个两个成对的结点来形成一个新的分支结点，所以不存在度为1的结点。
其中第三个树的WPL最小，根据验证，其为哈弗曼树。 5.7.2、哈夫曼树的构造算法 初始化：根据给定的n个权值 ，构造n棵只有一个根结点的二叉树， 这n棵二叉树构成森林F找最小树：在F中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值为左、右子树根结点权值之和；删除与加入：从F中删除这两颗树，并将新树加入F；判断：重复 2）和 3），直到F中只含一颗树为止，此时得到的这颗二叉树就是哈夫曼树。示例：w={5,29, 7, 8, 14, 23, 3, 11}
前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀，则称该编码系统中的编码是前缀码。例如，一组编码01,001,010,100,110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。 哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。 哈夫曼编码是最优前缀码
二叉树案例 第五章小结
（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 答案：A 解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。 （2）由3个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 答案：D 解释：五种情况如下： （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A．250 B． 500 C．254 D．501 答案：D 解释：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。 （4）一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 答案：C 解释：若每层仅有一个结点，则树高h为1025；且其最小树高为[ log21025] + 1=11，即h在11至1025之间。 （5）深度为h的满m叉树的第k层有（ ）个结点。(1= |
孩子表示法
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |