二叉树论文 二叉树的应用.doc

- 1 - 本科本科毕业论毕业论文（文（设计设计）模板）模板 2013 年度本科实践论文 实践题目实践题目： 二叉树的应用二叉树的应用 学生姓名： 杜杜 鑫鑫 学 号： 11052901241105290124 专 业： 软件工程软件工程 班 级： 软件工程软件工程 11011101 完成日期： 2013 年年 0808 月月 2525 日日 - 2 - 序 言 在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为 结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称 作“左子树” （left subtree）和“右子树” （right subtree） 。二叉树常被用于实现二叉查找树 和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图， 并且每一个顶点的度不大于 3。有根二叉树还要满足根结点的度不大于 2。有了根结点后，每个顶 点定义了唯一的根结点，和最多 2 个子结点。 数据结构中二叉树的应用有着很重要的作用，对解决很多程序问题都有很大帮助，因此，我 们更应该深入的学习和了解二叉树的应用，为以后更方便的解决计算机的相关问题做铺垫。只有 详细学习二叉树，了解二叉树的具体应用范围、方法以及针对性，才能很好地完成任务，解决问 题。 - 3 - 内 容 摘 要 本实践论文主要包含以下几个方面：二叉树的定义，二叉树的特点，二叉树的存储结构，二 叉树的排序、查找、插入、删除，平衡二叉树，二叉树的遍历，二叉树的相关应用等内容。由浅 入深的介绍了二叉树的主要内容和结构特性、操作实现，同时介绍了线索二叉树和哈夫曼树的基 本情况。最后简短的引用两个二叉树应用的源程序例子来说明二叉树的具体使用。二叉树结构的 应用非常广泛，特别是在大量数据处理方面，如在文件系统、编译系统、目录组织等方面显得更 加突出。存储结构的不同，二叉树实现的操作也不同。其中，二叉树的遍历运算时一个重要的基 础，对访问根结点操作的理解可包括多种操作。 关 键 词： 二叉树 二叉树特性 二叉树存储结构 二叉树遍历、拓展 哈夫曼树 - 4 - 目目 录录 一、二叉树的基本内容一、二叉树的基本内容.- 4 - （一）二叉树.- 4 - （二）二叉树的存储结构.- 4 - （三）二叉树的遍历.- 5 - 错误！未找到索引项。错误！未找到索引项。 二、二叉树的应用二、二叉树的应用.- 5 - （一）二叉排序树.- 5 - （二）二叉排序树查找.- 6 - （三）二叉排序树插入结点的算法.- 6 - （四）二叉排序树删除结点的算法.- 6 - （五）平衡二叉树.- 6 - （六）判定树.- 7 - （七）二分查找判定树的查找.- 7 - （八）线索二叉树.- 7 - 一、哈夫曼树一、哈夫曼树.- 10 - （一）哈夫曼树的构造算法.- 10 - 参考文献.- 12 - - 5 - 一、二叉树的基本内容一、二叉树的基本内容 （一）二叉树（一）二叉树 二叉树很像一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数 据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间 的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的双亲，结 点的后趋结点称为该结点的子女或孩子，同一结点的子女之间互称兄弟。 二叉树也是递归定义的，其结点有左右子树之分： (1) 完全二叉树若设二叉树的高度为 h，除第 h 层外，其它各层 (1h-1) 的结点数都达 到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。 (2) 满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。 (3) 深度二叉树的层数，就是高度。 （二）二叉树的存储结构（二）二叉树的存储结构 （1）顺序存储结构（适合完全二叉树和满二叉树） （2）链式存储结构（适合非完全二叉树） （三）二叉树的遍历（三）二叉树的遍历 （1）递归遍历（中序遍历、先序遍历、后序遍历） （2）非递归遍历（利用堆栈实现） （四）二叉树的拓展（四）二叉树的拓展 （1）线索二叉树（在节点空指针域存放前驱和后继节点的指针，加上线索标志域区分是 线索指针还是 child 指针；建立线索二叉树，实质上就是遍历一颗二叉树，在相应的指针域进行 操作） - 6 - （2）二叉排序树（可以了解到二叉树生成的过程） （3）最优二叉树（哈夫曼树）：对于一组有确定权值的叶子节点，构造的具有最小带权 路径长度的二叉树（典型应用：哈夫曼编码） （4）平衡树它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两 个子树都是一棵平衡二叉树。 （防止退化为链表，提高搜索效率） （5）排序树特点：所有结点“左小右大 （6）字典树由字符串构成的二叉排序树 （7）判定树特点：分支查找树（例如 12 个球如何只称 3 次便分出轻重） （8）带权树特点：路径带权值（例如长度） 二、二叉树的应用二、二叉树的应用 （一）二叉排序树（一）二叉排序树 或是一棵空树；或者是具有如下性质的非空二叉树： （1）若左子树不为空，左子树的所有结点的值均小于根的值； （2）若右子树不为空，右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 （二）二叉排序树查找（二）二叉排序树查找 在二叉排序树 b 中查找 x 的过程为： 若 b 是空树，则搜索失败，否则： 若 x 等于 b 的根节点的数据域之值，则查找成功；否则： 若 x 小于 b 的根节点的数据域之值，则搜索左子树；否则： 查找右子树。 （三）二叉排序树插入结点的算法（三）二叉排序树插入结点的算法 向一个二叉排序树 b 中插入一个结点 s 的算法，过程为： 若 b 是空树，则将 s 所指结点作为根结点插入，否则： - 7 - 若 s-data 等于 b 的根结点的数据域之值，则返回，否则： 若 s-data 小于 b 的根结点的数据域之值，则把 s 所指结点插入到左子树中，否则： 把 s 所指结点插入到右子树中。 （四）二叉排序树删除结点的算法（四）二叉排序树删除结点的算法 在二叉排序树删去一个结点，分三种情况讨论： 若*p 结点为叶子结点，即 PL(左子树)和 PR(右子树)均为空树。由于删去叶子结点不破坏整 棵树的结构，则只需修改其双亲结点的指针即可。 若*p 结点只有左子树 PL 或右子树 PR，此时只要令 PL 或 PR 直接成为其双亲结点*f 的左子树 即可，作此修改也不破坏二叉排序树的特性。 若*p 结点的左子树和右子树均不空。在删去*p 之后，为保持其它元素之间的相对位置不变， 可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p 的左子树为*f 的左子树，*s 为 *f 左子树的最右下的结点，而*p 的右子树为*s 的右子树；其二是令*p 的直接前驱（或直接后继） 替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继） 。 （五）平衡二叉树（五）平衡二叉树（BalancedBalanced BinaryBinary TreeTree） 性质： 左右子树都是平衡二叉树且所有结点左、右子树深度之差的绝对值 1。 若定义结点的“平衡因子平衡因子” BF（Balance Factor） = 左子树深度 右子树深度 则：平衡二叉树 中所有结点的 BF -1, 0, 1 （六）（六）判定树判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和 右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树 (Decision Tree)或比较树(Comparison Tree)。 判定树的形态只与表结点个数 n 相关，而与输入实例中 R1.n.keys 的取值无关。 （七）二分查找判定树的查找（七）二分查找判定树的查找 二分查找就是将给定值 K 与二分查找判定树的根结点的关键字进行比较。若相等，成功。否 则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。 二分查找的优点和缺点 虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使 采用高效率的排序方法也要花费 O(nlgn)的时间。 - 8 - 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大 量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上 无法实现二分查找。 （八）线索二叉树（八）线索二叉树 线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其 右孩子，否则令 rchild 指示其后继。还需在结点结构中增加两个标志域 LTag 和 RTag。LTag=0 时， lchild 域指示结点的左孩子，LTag=1 时，lchild 域指示结点的前驱；RTag=0 时，rchild 域指示 结点的右孩子，RTag=1 时，rchild 域指示结点的后继。以这种结点结构构成的二叉线索链表，链 表作为二叉树的存储结构，叫做其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树称 为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进 行中序遍历，则所得的线索二叉树称为中序线索二叉树，线索链表称为为中序线索链表。线索二 叉树是一种物理结构。 线索二叉树的存储结构：在中序线索树找结点后继的规律是：若其右标志为 1，则右链为线索， 指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点 前驱的规律是：若其左标志为 1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一 个结点（左子树中最右下的结点）为其前驱。 二叉树的应用编程： #include using namespace std; typedef struct tree/ typedef 定义类型,这里为结构体型; int num; struct tree *left; struct tree *right; ; tree *root; - 9 - tree *creat(int *a,int *b,int n)/用前序历遍和中序历遍得到的数据，确定唯一树 tree *k; int i; for(i=0;inum=bi; k-left=creat(a+1,b,i);/中序历遍中在根节点左边的都是左子树上的 k-right=creat(a+i+1,b+i+1,n-i-1);/在根节点右边的，都是右子树上的，右子 树需要从 i+1 开始； /因为根的左半只有 i 个数，加上自己所有就要把指针指向 a+i+1 的地方了， / printf(%dn,h-data );直接输出于是后续，判断不成立的情况 return k; return NULL;/没有对应找到，返回 NULL void houxu(tree *h) if(h!=NULL) houxu(h-left); houxu(h-right); if(root=h)/后序历遍最后历遍根节点 printf(%dn,h-num); else - 10 - printf(%d ,h-num); int main() tree *h; int a1001,b1001,n,i; while(scanf(%d,in;i+) scanf(%d, for(i=0;in;i+) scanf(%d, h=creat(a,b,n); root=h; houxu(h); 一、哈夫曼树一、哈夫曼树 最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小 带权路径长度的二叉树。 - 11 - （一）哈夫曼树的构造算法（一）哈夫曼树的构造算法 在构造哈夫曼树时，可以设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息，根据 二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n1 个结点，所以数组 HuffNode 的大 小设置为 2n1。 其中，weight 域保存结点的权值，lchild 和 rchild 域分别保存该结点的左、 右孩子结点在数组 HuffNode 中的序号，从而建立起结点之间的关系。为了判定一个结点是否已 加入到要建立的哈夫曼树中，可通过 parent 域的值来确定。初始时 parent 的值为1，当结点 加入到树中时，该结点 parent 的值为其双亲结点在数组 HuffNode 中的序号，就不会是1 了。 构造哈夫曼树时，首先将由 n 个字符形成的 n 个叶结点存放到数组 HuffNode 的前 n 个分量 中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每 次构成的新子树的根结点顺序放到 HuffNode 数组中的前 n 个分量的后面。 哈夫曼树的构造算法： #define MAXVALUE 10000 /*定义最大权值*/ #define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/ #define MAXNODE MAXLEAF*2-1 typedef struct int weight; int parent; int lchild; int rchild; HNodeType; v