L2数据结构第1415课树的 [复制链接]

一颗曾经砸中牛顿的苹果树

「树（Tree）」是n(n=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中，有且仅有一个特定的称为根的结点。当n1时，其余结点可分为m(m0)个互不相交的有限集T1、T2、……、Tm。其中每一个集合本身又是一棵树，并且称为根的「子树（SubTree）」，如下图所示：

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的的子树数称为结点的度。度为0的称为叶结点或者终端结点；度不为0的结点称为非终端结点或者分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点.

结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，其双亲在同一层的结点互为堂兄弟。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

「双亲（parentnode）」：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。根结点没有双亲结点。

「祖先（ancestor）」：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。

「子结点（childnode）」：如果

是

的父亲，那么

是

的子结点。子结点的顺序一般不加以区分，二叉树是一个例外。

「兄弟（sibling）」：同一个父亲的多个子结点互为兄弟。

「后代（descendant）」：子结点和子结点的后代。或者理解成：如果

是

的祖先，那么

是

的后代。

「子树（subtree）」：删掉与父亲相连的边后，该结点所在的子图。

结点n的高度:n结点到叶子结点所有路径上包含结点个数的最大值。叶子结点的高度为1，往上结点的高度依次递增。

结点n的深度:从根结点到结点n唯一的路径的长，根结点深度为1

层数：根结点为第一层，往下依次递增。

树中结点的最大层数称之为树的深度或者高度，所以在基数为1时树的深度=树的高度=最大层数

但是结点的深度和高度并没有必然的关系

结点的度：结点拥有的子树的个数，度为0的结点称之为叶子结点

树的度：是树内所有结点度的最大值

树的深度：树内所有结点深度的最大值，也就是所有叶子结点深度的最大值，也就是树的层数

树的高度：树内所有结点高度的最大值，也就是根结点的高度，也就是数的层数

「链（chain/pathgraph）」：满足与任一结点相连的边不超过

条的树称为链。

「菊花/星星（star）」：满足存在

使得所有除

以外结点均与

相连的树称为菊花。

「有根二叉树（rootedbinarytree）」：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。

大多数情况下，「二叉树」一词均指有根二叉树。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里.

/*树的双亲表示法的结点结构定义*/constintMAX_TREE_SIZEstructNode//结点结构{intdata;//数据域intparent;//父结点位置};Nodetree[MAX_TREE_SIZE];//把结点存在数组中

这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为〇(1)，直到parent为-1时，表示找到了树结点的根。

「总结」

「优点：」该存储方式根据结点的parent指针很容易找到它的双亲结点，时间复杂度为O(1)。

「缺点：」如果需要知道某个结点的所有孩子，需要遍历整棵树。

/*树的孩子表示法结构定义*/constintm=3;structNode{intdata;Node*chile[m];}Node*tree;

「总结」

「缺点：」如果需要知道某个结点的双亲，需要遍历整棵树

「改进：」孩子兄弟表示法

constintm=10;structNode{intdata;//数据域intparent;//父亲结点Node*child[m];//指针域,指向孩子结点}孩子兄弟表示法

strcutNode{intdata;intfirstchild;intnext;}Node*tree;

「总结」

「优点：」可以把一棵复杂的树变成一棵二叉树，这样就可以充分利用二叉树的特性和算法来处理这棵树了。

给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子

第一行：n（结点数=），m（边数=）。

以下m行；每行两个结点x和y，

表示y是x的孩子(x,y=0)。

第一行：树根：root。

第二行：孩子最多的结点max。

第三行：max的孩子。

输出样例

参考程序

#includeiostreamusingnamespacestd;constintN=;intn,m,x,y,tree[N],root,maxn,maxroot;intmain(){cinnm;for(inti=1;i=m;i++){cinxy;tree[y]=x;}for(inti=1;i=n;i++){if(tree==0){root=i;break;}}for(inti=1;i=n;i++){intsum=0;for(intj=1;j=n;j++){if(tree[j]==i)sum++;}if(summaxn){maxn=sum;maxroot=i;}}coutrootendl;coutmaxrootendl;for(inti=1;i=n;i++){if(tree==maxroot)couti"";}return0;}单词查找树题目描述

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：

1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；

2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；

3．在满足上述条件下，该单词查找树的结点数最少。

4．例如下图左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。