【数据结构】树的概念

博主： Fivk
发布时间：2021 年 07 月 12 日
1694 次浏览
2555字数
分类：数据结构

树是一种非线性的数据结构，用他能很好地描述有分支和层次特性的数据集合。树型结构在实现世界中广泛存在，如社会组织机构关系图就可以用树型结构来表示。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树形结构描述问题的求解过程、所有解的状态和求解的对策等。这些年的国内、国际星系学奥赛、大学生程序设计比赛等竞赛中，树形结构成为参赛者必备的知识之一，尤其是建立在树形结构基础之上的搜索算法。

在树形算法中，二叉树是最常用的结构，它的分支个树确定，又可以为空，并有良好的递归特性，特别适宜于程序设计，因此也常常将一般树转换成二叉树进行处理。

# 一、树的定义

一颗树是由n（n>0）个元素组成的有限集合，其中：

1. 每个元素称为节点（node）；
2. 有一个特定的节点，成为根节点或树根（root）；
3. 除根节点外，其余节点能分成m（m $\geq$ 0）个互不相交的有限集合$t_0$,$t_1$,$t_2$,...,$t_{m-1}$。其中每个子集又是一颗树，这些集合称为这颗树的子树。

![](https://blog.fivk.cn/usr/uploads/2021/06/187234439.png)

# 二、树的基本概念

1. 树是递归定义的。
2. 一颗树中至少有1个节点。这个节点就是根节点，它没有前驱，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点。因此树虽然是非线性结构，但也是有序结构。至于前驱后继节点是那个，还要看树的遍历方法。
3. 一个节点的子树个数，称为这个节点的度（degree，节点1的度为3，节点3的度为0）；度为0的节点称为叶节点（红叶 leaf，如节点 3、5、6、8、9）；度不为0的节点称为分支节点（如节点 1、2、4、7）；根以外的分支节点又称为内部节点（如节点 2、4、7）；树中各节点的度的最大值称为这棵树的度（这颗树的度为 3）。
4. 在用图形表示的树型结构中，对两个用线性段（称为树枝）链接的相关联的节点，称上端节点为下段节点的父节点，称下端节点为上端节点的子节点。称同一个父节点的多个子节点为兄弟节点。如节点 1 是节 2、3、4的父节点，节点 2、3、4是节点 1 的子节点，他们又是兄弟节点，同时节点2又是节点 5、6的父节点。称从根节点到某个子节点所经过的所有节点为这个节点的祖先。如节点 1、4、7是节点 8的祖先。称以某个节点为根的子树的任一节点都是该节点的子孙节点。如节点 7、8、9都是节点4的子孙。
5. 定义一颗树的根节点的层次（level）为0，其他节点的层次等于他父节点层次加 1、如节点 2、3、4的层次为1，节点 5、6、7的层次为2，节点 8、9的层次为3。一颗树中所有的节点的层次最大值称为树的深度（depth）。如这颗树的深度为3。

# 3、数的存储结构

**方法1：**数组，称为“父亲表示法”。

```cpp
const int m=10;		//树的根节点数
struct node
{
	int data,parent;	//数据域，指针域
}；
node tree[m];
```

优缺点：利用了树中除根节点都有唯一的父节点这个性质，很容易找到树根，但找孩子需要遍历整个线性表。

**方法2：**树型单链表结构，称为“孩子表示法”。每个节点包括一个数据域和一个指针域（指向若干子节点），称为“孩子表示发”。假设树的度为10，树的节点仅存放字符，则这颗树的数据结构定义如下：

```cpp
const int m=10;		//树的度
typedef struct node;
typedef node* tree;
struct node
{
	char data;	//数据域
	tree child[m];	//指针域，指向若干孩子节点
};
tree t;
```

缺陷:只能从根(父)结点遍历到子结点,不能从某个子结点返回到它的父结点。但程序中确实需要从某个结点返回到它的父结点时,就需要在结点中多定义一个指针变量存放其父结点的信息。这种结构又叫带逆序的树型结构。

**方法3：**树型双链表结构,称为“父亲孩子表示法”。每个结点包括一个数据域和两个指针域(一个指向若干子结点，一个指向父结点)。假设树的度为10,树的结点仅存放字符,则这棵树的数据结构定义如下:

```cpp
const int m=10;		//树的度
typedef struct node;
typedef node *tree;
struct  node
{
	char data;	//数据域
	tree child[m];	//指针域，指向若干孩子节点
	tree father;	//指针域，指向父亲节点
};
tree t;
```

**方法4：**二叉树型表示法,称为“孩子兄弟表示法”。它是一种双链表结构,但每个结点包括一个数据域和两个指针域(一个指向该结点的第一个孩子结点，一个指向该结点的下一个兄弟结点)。假设树的度为10,树的结点仅存放字符,则这棵树的数据结构定义如下:

```cpp
typedef struct node;
typedef node* tree;
struct node
{
	char data;		//数据域
	tree firstchild,next;	//指针域，分别指向第一个孩子节点和下一个兄弟节点
}
tree t;
```

**例3.1 找树根和孩子**

【问题描述】
给定一棵树,输出树的根root,孩子最多的结点max以及他的孩子。

【输入格式】
第1行:n(结点个数<=100),m(边数≤=200)。
以下m行:每行两个结点x和y,表示y是x的孩子(x,y<=1000)。

【输出格式】
第1行:树根:root。
第2行:孩子最多的结点 max。第3行:max的孩子。
【输入样例】

```cpp
8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8
```

【输出样例】

```cpp
4
2
6 7 8
```

```cpp
#include<iostream>
using namespace std;
int n,m,tree[101]={0};
int main()
{
    int i,x,y,root,maxroot,sum=0,j,Max=0;
    cin>>n>>m;

for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        tree[y]=x;
    }

for(i=1;i<=n;i++)       //找到树根（没有父节点）
        if(tree[i]==0)
        {
            root=i;
            break;
        }

for(i=1;i<=n;i++)       //找孩子最多的节点
    {
        sum=0;
        for(j=1;j<=n;j++)
            if(tree[j]==i) sum++;
        if(sum>Max)
        {
            Max=sum;
            maxroot=i;
        }
    }

cout<<root<<endl<<maxroot<<endl;
    for(i=1;i<=n;i++)
        if(tree[i]==maxroot) cout<<i<<" ";
    cout<<endl;
    system("pause");
    return 0;
}
```

# 四、树的遍历

在应用树结构解决问题时,往往要求按照某种次序获得树中全部结点的信息,这种操作叫作树的遍历。遍历的方法有多种,常用的有:

1. 先序(根)遍历:先访问根结点,再从左到右按照先序思
   想遍历各棵子树。如图先序遍历的结果为:125634789;
2. 后序(根)遍历:先从左到右遍历各棵子树,再访问根结
   点。如图后序遍历的结果为:562389741;
3. 层次遍历:按层次从小到大逐个访问,同一层次按照从
   左到右的次序。如图层次遍历的结果为:123456789 ;
4. 叶结点遍历:有时把所有的数据信息都存放在叶结点中,而其余结点都是用来表示数据之间的某种分支或层次关系,这种情况就用这种方法。如图按照这个思想访问的结果为:56389;

![](https://blog.fivk.cn/usr/uploads/2021/07/2815635983.png)

大家可以看出,1,2两种方法的定义是递归的,所以在程序实现时往往也是采用递归的思想,即通常所说的“**深度优先搜索**”。如用先序遍历编写的过程如下:

```cpp
void tral(tree t,int m)
{
	if(t)
	{
		cout<<t->data<<endl;
		for(int i=0;i<m;i++)
		tral(t->child[i],m);
	}
}
```

C方法应用也较多,实际上是我们讲的“广度优先搜索”。思想如下:若某个结点被访问,则该结点的子结点应记录,等待被访问。顺序访问各层次上结点,直至不再有未访问过的结点。为此,引人一个队列来存储等待访问的子结点,设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下:

```cpp
const int n=100;
int head,tail,i;
tree q[n];
tree p;
void work()
{
	tail=head=1;
	q[tail]=t;
	tail++;			//队尾为空
	while(head<tail)
	{
		p=q[head];
		head++;
		cout<<p->data<<" ";
		for(i=0;i<m;i++)
		if(p->child[i])
		{
			q[tail]=p->child[i];
			tail++;
		}

}

}
```

**例3.2单词查找树**

【问题描述】
在进行文法分析的时候,通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度,通常都画出与单词列表所对应的单词查找树,其特点如下:
1.根结点不包含字母,除根结点外每一个结点都仅包含一个大写英文字母。
2.从根结点到某一结点,路径上经过的字母依次连起来所构成的字母序列,称为该结点对应的单词。单词列表中的每个单词,都是该单词查找树某个结点所对应的单词。
3．在满足上述条件下,该单词查找树的结点数
最少。
4.例如图左边的单词列表就对应于右边的单词查找树。注意,对一个确定的单词列表,请统计对应
的单词查找树的结点数(包含根结点)。

![](https://blog.fivk.cn/usr/uploads/2021/07/2411795685.png)

【输入格式】
输入文件名为word.in,该文件为一个单词列表,每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成,长度不超过63个字母。文件总长度不超过32K,至少有一行数据。
【输出格式】
输出文件名为word.out,该文件中仅包含一个整数,该整数为单词列表对应的单词查找树的结点数。

【输入样例】

```in
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
```

【输出样例】

```out
13
```

【算法分析】
首先要对建树的过程有一个了解。对于当前被处理的单词和当前树:在根结点的子结点中找单词的第一位字母,若存在,则进而在该结点的子结点中寻找第二位…如此下去直到单词结束,即不需要在该树中添加结点;或单词的第n位不能被找到﹐即将单词的第n位及其后的字母依次加入单词查找树中去。但,本问题只是问你结点总数,而非建树方案,且有32K文件,所以应该考虑能不能不通过建树就直接算出结点数?为了说明问题的本质,我们给出一个定义:一个单词相对于另一个单词的差;设单词1的长度为L,且与单词2从第N位开始不一致,则说单词1相对于单词2的差为L一N+1,这是描述单词相似程度的量。可见,将一个单词加入单词树的时候,须加人的结点数等于该单词树中已有单词的差的最小值。
单词的字典顺序排列后的序列则具有类似的特性,即在一个字典顺序序列中,第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是,得出建树的等效算法:

1. 读人文件;
2. 对单词列表进行字典顺序排序;
3. 依次计算每个单词对前一单词的差,并把差累加起来。注意:第一个单词相对于“空”的差为该单词的长度;
4. 累加和再加上1(根结点),输出结果。

就给定的样例,按照这个算法求结点数的过程如下表:

![](https://blog.fivk.cn/usr/uploads/2021/07/3032208833.png)

先确定32K(32 * 10241=32768字节)的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复,所以长度为1的单词(单个字母)最多26个;长度为2的单词最多为26*26=676个;因为每个单词后都要一个换行符(换行符在计算机中占2个字节),所以总共已经占用的空间为:(1＋2)* 26＋(2＋2) * 676=2782字节;剩余字节(32768-2782=29986字节)分配给长度为3的单词(长度为3的单词最多有26*26* 26=17576个)有29986/(3＋2)5997。所以单词数量最多为26+676+5997=6699。
定义一个数组:string a[32768];把所有单词连续存放起来,用选择排序或快排对单词进行排序。

```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

int i,j,n=1,t;
string str[10001];        //数组可到32768
int main()
{
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    while(cin>>str[n])   //读入文件中的单词并且储存到数组中
    {
        n++;
    }

sort(str+1,str+n);    //从小到大排序

t=str[1].length();      //先累加第1个单词的长度

for(i=2;i<n;i++)
    {
        for(j=0;j<str[i-1].length();j++)
        {                           //求出两个单词(str[i-1],str[i])相同部分的长度(j)
            if(str[i-1][j]!=str[i][j])
                break;
        }
                          
        t+=str[i].length()-j;       //累加两个单词的差 str[i].length()-j
    }

cout<<t+1<<endl;
    fclose(stdin);
    fclose(stdout);
    system("pause");
    return 0;   
}
```

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

【数据结构】树的概念

Fivk • 2021 年 07 月 12 日

# 一、树的定义

一颗树是由n（n>0）个元素组成的有限集合，其中：

![](https://blog.fivk.cn/usr/uploads/2021/06/187234439.png)

# 二、树的基本概念

# 3、数的存储结构

**方法1：**数组，称为“父亲表示法”。

```cpp
const int m=10;		//树的根节点数
struct node
{
	int data,parent;	//数据域，指针域
}；
node tree[m];
```

优缺点：利用了树中除根节点都有唯一的父节点这个性质，很容易找到树根，但找孩子需要遍历整个线性表。

```cpp
const int m=10;		//树的度
typedef struct node;
typedef node* tree;
struct node
{
	char data;	//数据域
	tree child[m];	//指针域，指向若干孩子节点
};
tree t;
```

```cpp
typedef struct node;
typedef node* tree;
struct node
{
	char data;		//数据域
	tree firstchild,next;	//指针域，分别指向第一个孩子节点和下一个兄弟节点
}
tree t;
```

**例3.1 找树根和孩子**

【问题描述】
给定一棵树,输出树的根root,孩子最多的结点max以及他的孩子。

【输入格式】
第1行:n(结点个数<=100),m(边数≤=200)。
以下m行:每行两个结点x和y,表示y是x的孩子(x,y<=1000)。

【输出格式】
第1行:树根:root。
第2行:孩子最多的结点 max。第3行:max的孩子。
【输入样例】

```cpp
8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8
```

【输出样例】

```cpp
4
2
6 7 8
```

```cpp
#include<iostream>
using namespace std;
int n,m,tree[101]={0};
int main()
{
    int i,x,y,root,maxroot,sum=0,j,Max=0;
    cin>>n>>m;

for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        tree[y]=x;
    }

for(i=1;i<=n;i++)       //找到树根（没有父节点）
        if(tree[i]==0)
        {
            root=i;
            break;
        }

cout<<root<<endl<<maxroot<<endl;
    for(i=1;i<=n;i++)
        if(tree[i]==maxroot) cout<<i<<" ";
    cout<<endl;
    system("pause");
    return 0;
}
```

# 四、树的遍历

在应用树结构解决问题时,往往要求按照某种次序获得树中全部结点的信息,这种操作叫作树的遍历。遍历的方法有多种,常用的有:

![](https://blog.fivk.cn/usr/uploads/2021/07/2815635983.png)

```cpp
void tral(tree t,int m)
{
	if(t)
	{
		cout<<t->data<<endl;
		for(int i=0;i<m;i++)
		tral(t->child[i],m);
	}
}
```

}

}
```

**例3.2单词查找树**

![](https://blog.fivk.cn/usr/uploads/2021/07/2411795685.png)

【输入样例】

```in
A
AN
ASP
AS
ASC
ASCII
BAS
BASIC
```

【输出样例】

```out
13
```

就给定的样例,按照这个算法求结点数的过程如下表:

![](https://blog.fivk.cn/usr/uploads/2021/07/3032208833.png)

```cpp
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;

sort(str+1,str+n);    //从小到大排序

t=str[1].length();      //先累加第1个单词的长度

cout<<t+1<<endl;
    fclose(stdin);
    fclose(stdout);
    system("pause");
    return 0;   
}
```

【数据结构】树的概念

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【Redis】分布式缓存

【知识总结】最近遇到Mybatis中#和$的细节和应用

【知识总结】微服务基础

【C】链表_链表的逆序

【Java】类与对象

【数据结构】树的概念