第3章--第1-3节-树、二叉树、堆及其应用(c++版)

第一二节 树及二叉树,简介,树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如社会组织机构的组织关系图就可以用树型结构来表示。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。在这些年的国内、国际信息学奥赛、大学生程序设计比赛等竞赛中，树型结构成为参赛者必备的知识之一，尤其是建立在树型结构基础之上的搜索算法。 在树型结构中，二叉树是最常用的结构，它的分支个数确定、又可以为空、并有良好的递归特性，特别适宜于程序设计，因此也常常将一般树转换成二叉树进行处理。,第一节 树的概念-树的定义,一棵树是由n（n0）个元素组成的有限集合，其中： （1）每个元素称为结点(node)； （2）有一个特定的结点，称为根结点或树根（root）； （3）除根结点外，其余结点能分成m（m=0）个互不相交的有限集合T0,T1,T2,Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。 如下图是一棵典型的树：,树的基本概念,树是递归定义的； 一棵树中至少有1个结点。这个结点就是根结点，它没有前驱，其余每个结点都有唯一的一个前驱结点。每个结点可以有0或多个后继结点。因此树虽然是非线性结构，但也是有序结构。至于前驱后继结点是哪个，还要看树的遍历方法，我们将在后面讨论； 一个结点的子树个数，称为这个结点的度（degree，结点1的度为3，结点3的度为0）；度为0的结点称为叶结点（树叶leaf，如结点3、5、6、8、9）；度不为0的结点称为分支结点（如结点1、2、4、7）；根以外的分支结点又称为内部结点（结点2、4、7）；树中各结点的度的最大值称为这棵树的度（这棵树的度为3）。 在用图形表示的树型结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端结点为下端结点的父结点，称下端结点为上端结点的子结点。称同一个父结点的多个子结点为兄弟结点。如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点，同时结点2又是结点5、6的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点1、4、7是结点8,的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点7、8、9都是结点4的子孙。 E.定义一棵树的根结点的层次（level）为0，其它结点的层次等于它的父结点层次加1。如结点2、3、4的层次为1，结点5、6、7的层次为2，结点8、9的层次为3。一棵树中所有的结点的层次的最大值称为树的深度（depth）。如这棵树的深度为3。 F.对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。如上图中，结点1和结点8之间存在着一条路径，并可用（1、4、7、8）表示这条路径，该条路径的长度为3。注意，不同子树上的结点之间不存在路径，从根结点出发，到树中的其余结点一定存在着一条路径。 G.森林（forest）是m(m=0)棵互不相交的树的集合。,树的存储结构,方法1：数组，称为“父亲表示法”。 const int m = 10; /树的结点数 struct node int data, parent; /数据域，指针域 ; node treem; 优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质。很容易找到树根，但找孩子时需要遍历整个线性表。,方法2：树型单链表结构，称为“孩子表示法”。每个结点包括一个数据域和一个指针域（指向若干子结点）。称为“孩子表示法”。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下： const int m = 10; /树的度 typedef struct node; typedef node *tree; struct node char data; /数据域 tree childm; /指针域，指向若干孩子结点 ; tree t; 缺陷：只能从根（父）结点遍历到子结点，不能从某个子结点返回到它的父结点。但程序中确实需要从某个结点返回到它的父结点时，就需要在结点中多定义一个指针变量存放其父结点的信息。这种结构又叫带逆序的树型结构。,方法3：树型双链表结构，称为“父亲孩子表示法”。每个结点包括一个数据域和二个指针域（一个指向若干子结点，一个指向父结点）。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下： const int m = 10; /树的度 typedef struct node; typedef node *tree; /声明tree是指向node的指针类型 struct node char data; /数据域 tree childm; /指针域，指向若干孩子结点 tree father; /指针域，指向父亲结点 ; tree t;,方法4：二叉树型表示法，称为“孩子兄弟表示法”。也是一种双链表结构，但每个结点包括一个数据域和二个指针域（一个指向该结点的第一个孩子结点，一个指向该结点的下一个兄弟结点）。称为“孩子兄弟表示法”。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下： typedef struct node; typedef node *tree; struct node char data; /数据域 tree firstchild, next; /指针域，分别指向第一个孩子结点和下一个兄弟结点 ; tree t;,【例3-1】找树根和孩子 【问题描述】 给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子 【输入格式】 第一行：n（结点数=100），m（边数=200）。 以下m行；每行两个结点x和y， 表示y是x的孩子(x,y=1000)。 【输出格式】 第一行：树根：root。 第二行：孩子最多的结点max。 第三行：max的孩子。,【输入样例】 8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8,【输出样例】 4 2 6 7 8,【参考程序】 #include using namespace std; int n,m,tree101=0; int main() int i,x,y,root,maxroot,sum=0,j,Max=0; cinnm; for(i=1;ixy; treey=x; for(i=1;i=n;i+) /找出树根 if(treei=0) root=i;break; for(i=1;i=n;i+) /找孩子最多的结点 sum=0;,for(j=1;jMax) Max=sum;maxroot=i; coutrootendlmaxrootendl; for(i=1;i=n;i+) if(treei=maxroot) couti“ “; return 0; ,树的遍历,在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，常用的有： A、先序（根）遍历：先访问根结点，再从左到右按照先序思想遍历 各棵子树。 如上图先序遍历的结果为：125634789； B、后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。如 上图后序遍历的结果为：562389741； C、层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的 次序。 如上图层次遍历的结果为：123456789； D、叶结点遍历：有时把所有的数据信息都存放在叶结点中，而其余 结点都是用来表示数据之间的某种分支或层次关系，这种情况就 用这种方法。如上图按照这个思想访问的结果为：56389；,大家可以看出，AB两种方法的定义是递归的，所以在程序实现时往往也是采用递归的思想。既通常所说的“深度优先搜索”。如用先序遍历编写的过程如下： void tral(tree t, int m) If (t) cout data childi, m); C方法应用也较多，实际上是我们讲的“广度优先搜索”。思想如下：若某个结点被访问，则该结点的子结点应记录，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：,const int n = 100; int head, tail, i; tree qn; tree p; void work() tail = head = 1; qtail = t; tail+; /队尾为空 while(head data childi) qtail = p-childi; tail+; ,【例3-2】单词查找树 【问题描述】 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下： 1根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母； 2从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词； 3在满足上述条件下，该单词查找树的结点数最少。 4例如图左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。,【问题输入】 输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。 【问题输出】 输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。,【样例输入】 A AN ASP AS ASC ASCII BAS BASIC,【样例输出】 13,【算法分析】 首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加入单词查找树中去。但，本问题只是问你结点总数，而非建树方案，且有32K文件，所以应该考虑能不能不通过建树就直接算出结点数？为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则说单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中已有单词的差的最小值。 单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是，得出建树的等效算法：, 读入文件； 对单词列表进行字典顺序排序； 依次计算每个单词对前一单词的差，并把差累加起来。注意：第 一个单词相对于“空”的差为该单词的长度； 累加和再加上1（根结点），输出结果。 就给定的样例，按照这个算法求结点数的过程如下表：,【数据结构】 先确定32K（32*1024=32768字节）的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复，所以长度为1的单词（单个字母）最多26个；长