【数据结构】树

博主：本当迷
发布时间：2021 年 10 月 01 日
1255 次浏览
1 条评论
3796字数
分类：数据结构

# 树：

## 树的定义

树是n个结点的有限集。（一对多的数据结构）

## 树的特点：

* 根节点是唯一的
* 字树的个数没有限制，但是他们一定是互不相交的

### 度的定义：

结点拥有的子树数

### 叶结点（终端结点）：

度为0的结点

### 分支结点（非终端结点）：

度不为0的结点

### 树的度：

树内各结点度的最大值

## 结点之间的关系：

结点的子树称为该结点的孩子，相应的该结点称为孩子的双亲；

同一个双亲的孩子之间互称兄弟；

结点的祖先是从根到该结点所经分支上的所以结点；

以某结点为根的子树中任一结点称为该结点的子孙。

## 树的其他相关概念

结点的层次从根开始定义起，根为第一层，根的孩子为第二层；

双亲在同一层的结点互为堂兄弟；

树中结点的最大层次称为数的深度或高度；

结点左右子树是有序的，称为有序树；反之，称为无序树。

## 线性结构与树结构的不同：

### 线性结构：

第一个数据元素：无前驱

最后一个数据元素：无后继

中间元素：一个前驱一个后继

### 树结构：

根结点：无双亲，唯一

叶结点：无孩子，可以多个

中间结点：一个双亲多个孩子

## 树的抽象数据类型：

```
ADT 数（tree）
Date
	数是由根节点和若干颗子树构成的。树中结点具有相同数据类型及层次关系
Operation
	InitTree（*T）;//构造空树T
	DestroyTree（*T）;//销毁数T
	CreteTree（*T, definition）;//按definition中给出树的定义来构造树
	TreeEmpty（T）;//若树为空，返回tree,否则返回false
	TreeDepth（T）;//返回T的深度
	Root（T）;//返回T的根结点
	Value（T, cur_e）;//cur_e是树T中一个结点，返回此节点的值
	Assign（T, cur_e, value）;//给树T的结点cur_e赋值value
	Parent（T, cur_e）;//若cur_e是树的非根结点，则返回它的双亲；否则返回空
	LeftChild（T, cur_e）;//若cur_e是树非叶结点，则返回它的最左孩子，否则返回空
	RightSibling（T, cur_e, e）;//若cur_e有右兄弟，返回右兄弟；反之，返回空
	InsertChild（*T, *P , i, c）;//插入c为数T中P所指结点的第i颗子树
	DeleteChild（*T, *P, I）;//删除T中P所指结点的第i颗子树
endADT
```

## 双亲表示法：

### 主要特点

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置

### 程序运行结果：

![](https://www.bdmcom.cn/usr/uploads/2021/10/133020498.png)

### 代码示例：

```cpp
#include<iostream>
#include<string>
using namespace std;
#define MAX_TREE_SIZE 100
typedef  string TEleType;//树结点的数据类型

typedef struct PTNode//结点结构
{
	TEleType date;//结点数据
	int parent;//双亲位置
}PTNode;

typedef struct//树结构
{
	PTNode nodes[MAX_TREE_SIZE];//结点数组
	int r, n;//根的位置和结点数
}PTree;

void create_tree(PTree& p, int r, int n)
{
	p.r = r;
	p.n = n;
	for (int i = 0; i < n; i++)
	{
		string data;
		int parent;
		cin >> data>>parent;
		p.nodes[i].date = data;
		p.nodes[i].parent = parent;

}
}

void print_tree(PTree p, int n)
{
	if (n > 0 && p.n != 0)
	{
		for (int i = 0; i < n; i++)
		{
			if (i == 0)
			{
				cout << p.nodes[i].date << endl;
			}
			else
			{
				int Perant = p.nodes[i].parent;
				cout << p.nodes[Perant].date << " -> " << p.nodes[i].date<<"  ";
				if (p.nodes[i].parent != p.nodes[i + 1].parent)
				{
					cout << endl;
				}
			}
		}
	}
	else
	{
		cout << "输出失败！" << endl;
	}
}

int main()
{
	PTree p;
	create_tree(p, -1, 10);
	print_tree(p, 10);
	return 0;
}
```

## 孩子表示法：

### 主要特点：

把每个孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

### 伪代码：

```cpp
#define MAX_TREE_SIZE 100
typedef  string TEleType;//树结点的数据类型

typedef struct CTNode//孩子结点
{
	int child;
	struct CTNode* next;
}*Childptr;

typedef struct//表头结构
{
	TEleType data;
	Childptr firstChild;
	int num_tree;//孩子结点数
}CTBox;

typedef struct//树结构
{
	CTBox node[MAX_TREE_SIZE];//结点数组
	int r, n;//根的位置和结点数
}CTree;
```

## 孩子兄弟表示法：

### 主要特点：

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

### 伪代码：

```cpp
typedef strucr CSNode
{
	TElemType data;
	struct CSNode *firstchild, *right, *rightsib;
}CSNode, *CSTree;
```

# 二叉树：

## 二叉树介绍：

### 二叉树定义：

二叉树是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成。

### 二叉树特点：

* 每个结点最多有两颗子树
* 左子树和右子树是有顺序的，次序不能颠倒
* 即使树中某结点只有一棵树，也要区分它是左子树还是右子树

## 特殊二叉树：

### 斜树：

所有结点都只有左子树的二叉树叫左斜树，所以的结点只有右子树的二叉树称为右斜树。两者统称斜树。

### 满二叉树：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

### 完全二叉树：

对一颗具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树

#### 完全二叉树的特点：

* 叶子结点只能出现在最下两层
* 最下层的叶子一定集中在左部连续位置
* 倒数两层，若有叶子结点，一定都在右部连续位置
* 如果结点度为1，则该结点只有左孩子，即不存在右子树的情况
* 同样结点数的二叉树，完全二叉树的深度最小

## 二叉树性质：

### 性质一：

在二叉树的第i层最多有 `2的 (i - 1)次方` 个结点。

### 性质二：

深度为k的二叉树最多有` 2的 k 次方 - 1` 个结点

### 性质三：

对任何一颗二叉树T，如果其终端结点数为n，度为2的结点数为n1,

则 n = n1 + 1;

### 性质四：

具有n个结点的完全二叉树的深度为[log n]+1（long n 是以2为底的对数，[x]表示不大于x的最大整数）

### 性质五：

如果对一颗有n个结点的完全二叉树（其深度为[logn +1]）的结点按层序编号（从第1层到第[log n] + 1层，每层从左到右），对任一结点i，有：

* 如果 i = 1，则结点i是二叉树的根，无双亲；如果i > 1,则其双亲是结点[ i / 2]
* 如果 2i > n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
* 如果2i + 1 > n，则结点i无右孩子；否则右孩子是结点2i + 1

## 二叉树的链式存储（二叉链表）：

### 概念：

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表为二叉链表

### 二叉链表结点结构定义：

```cpp
typedef struct BiTNod//结点结构
{
	TEleType data;//结点数据
	struct BiTNod* lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;
```

## 遍历二叉树：

概念：二叉树遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

### 前序遍历：

#### 方法：

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

#### 算法：

```cpp
void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
		return;
	cout << T->date;//显示结点数据，可以更改为其他对结点的操作
	PreOrderTraverse(T->lchild);//先序遍历左子树
	PreOrderTraverse(T->rchild);//先序遍历右子树
}
```

### 中序遍历：

#### 方法：

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

#### 算法：

```cpp
void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
		return;
	PreOrderTraverse(T->lchild);//先序遍历左子树
	cout << T->date;//显示结点数据，可以更改为其他对结点的操作
	PreOrderTraverse(T->rchild);//先序遍历右子树
}
```

### 后序遍历：

#### 方法：

规则是若树为空，则空操作返回，否则从左到右先叶子后结点方式遍历访问左右子树，最后是访问根结点。

#### 算法：

```cpp
void PreOrderTraverse(BiTree T)
{
	if (T == NULL)
		return;
	PreOrderTraverse(T->lchild);//先序遍历左子树
	PreOrderTraverse(T->rchild);//先序遍历右子树
	cout << T->date;//显示结点数据，可以更改为其他对结点的操作
}
```

## 二叉树遍历的性质：

* 已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
* 已知中序遍历序列和后序遍历序列，可以唯一确定一颗二叉树
* 但是：已知前序遍历序列和后续遍历序列，不可以确定一颗二叉树

## 二叉树的建立：

### 伪代码：

```cpp
void CreateBiTree(BiTree* T)//按照前序输入二叉树中结点的值， #表示空树
{
	TElemType ch;
	cin>>ch;
	if(ch == "#")
		*T = NULL;
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
			exit(OVERFLOW);
		(*T)->data = ch;//生成根结点
		CreateBiTree(&(*T)->lchild);//构造左子树
		CreateBiTree(&(*T)->rchild);//构造右子树
	}
}
```

## 线索二叉树：

### 概念：

我们把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树称为二叉树；对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

### 线索存储结构：

#### 伪代码：

```cpp
typedef char TElemType;
typedef enum{Link, Thread} PointerTag;//Link = 0表示指向左右孩子指针，Thread = 1表示指向前驱或后继的线索

typedef struct BiThrNode//二叉线索存储结点结构
{
	TElemType data;//结点数据
	struct BiThrNode *lchild, *rchild;//左右孩子指针
	PointerTag LTag;
	PointerTag RTag;//左右标志
}BiThrNode, *BiThTree;
```

### 线索化（中序遍历）：

#### 伪代码：

```cpp
BiThrTree Pre;//全局变量，始终指向刚刚访问过的结点

void InThreading(BiThtTree p)
{
	InThreading(p->lchild);//递归左子树线索化
	if(!p->lchild)//没有左孩子
	{
		p->LTag = Thread;//前驱线索化
		p->lchild = pre;//左孩子指针指向前驱
	}
	if(!p->rchild)//没有右孩子
	{
		pre->RTag = Thread;//后继线索化
		pre->rchild = p;//前驱右孩子指针指向后继（当前结点p）
	}
	pre = p;//保持pre指向p的前驱
	InThreading(p->rchild);//递归右子树线索化
}
```

### 遍历（中序遍历）：

#### 伪代码：

```cpp
Status InOrderTraverse_Thr(BithTree T)
{
	BiThrTree p;
	p = T->lchild;//p指向根结点
	while(p!=T)//空树或遍历结束时，p = T
	{
		while(p->LTag == Link)//当LTag = 0时循环到中序序列第一个结点
			p = p->lchild;
		cout<<p->data;//显示结点数据，可以更改为对其他结点的操作
		while(p->RTag == Thread && p->rchild != T)
		{
			p = p->rchild;
			cout<<p->data;
		}
		p = p->rchild;//p进至其右结点
	}
	return OK;

}
```

### 使用场合：

如果所用的二叉树需要经常遍历或者查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉树的存储结构是个不错的选择！

最后修改：2021 年 10 月 04 日

如果文章有用，请随意打赏。

1 条评论

梦一帆
October 1st, 2021 at 10:41 pm

你们卷，那我也卷 →_→

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【数据结构】树

本当迷 • 2021 年 10 月 01 日

# 树：

## 树的定义

树是n个结点的有限集。（一对多的数据结构）

## 树的特点：

* 根节点是唯一的
* 字树的个数没有限制，但是他们一定是互不相交的

### 度的定义：

结点拥有的子树数

### 叶结点（终端结点）：

度为0的结点

### 分支结点（非终端结点）：

度不为0的结点

### 树的度：

树内各结点度的最大值

## 结点之间的关系：

结点的子树称为该结点的孩子，相应的该结点称为孩子的双亲；

同一个双亲的孩子之间互称兄弟；

结点的祖先是从根到该结点所经分支上的所以结点；

以某结点为根的子树中任一结点称为该结点的子孙。

## 树的其他相关概念

结点的层次从根开始定义起，根为第一层，根的孩子为第二层；

双亲在同一层的结点互为堂兄弟；

树中结点的最大层次称为数的深度或高度；

结点左右子树是有序的，称为有序树；反之，称为无序树。

## 线性结构与树结构的不同：

### 线性结构：

第一个数据元素：无前驱

最后一个数据元素：无后继

中间元素：一个前驱一个后继

### 树结构：

根结点：无双亲，唯一

叶结点：无孩子，可以多个

中间结点：一个双亲多个孩子

## 树的抽象数据类型：

## 双亲表示法：

### 主要特点

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置

### 程序运行结果：

![](https://www.bdmcom.cn/usr/uploads/2021/10/133020498.png)

### 代码示例：

```cpp
#include<iostream>
#include<string>
using namespace std;
#define MAX_TREE_SIZE 100
typedef  string TEleType;//树结点的数据类型

typedef struct PTNode//结点结构
{
	TEleType date;//结点数据
	int parent;//双亲位置
}PTNode;

typedef struct//树结构
{
	PTNode nodes[MAX_TREE_SIZE];//结点数组
	int r, n;//根的位置和结点数
}PTree;

}
}

int main()
{
	PTree p;
	create_tree(p, -1, 10);
	print_tree(p, 10);
	return 0;
}
```

## 孩子表示法：

### 主要特点：

### 伪代码：

```cpp
#define MAX_TREE_SIZE 100
typedef  string TEleType;//树结点的数据类型

typedef struct CTNode//孩子结点
{
	int child;
	struct CTNode* next;
}*Childptr;

typedef struct//表头结构
{
	TEleType data;
	Childptr firstChild;
	int num_tree;//孩子结点数
}CTBox;

typedef struct//树结构
{
	CTBox node[MAX_TREE_SIZE];//结点数组
	int r, n;//根的位置和结点数
}CTree;
```

## 孩子兄弟表示法：

### 主要特点：

### 伪代码：

```cpp
typedef strucr CSNode
{
	TElemType data;
	struct CSNode *firstchild, *right, *rightsib;
}CSNode, *CSTree;
```

# 二叉树：

## 二叉树介绍：

### 二叉树定义：

### 二叉树特点：

* 每个结点最多有两颗子树
* 左子树和右子树是有顺序的，次序不能颠倒
* 即使树中某结点只有一棵树，也要区分它是左子树还是右子树

## 特殊二叉树：

### 斜树：

所有结点都只有左子树的二叉树叫左斜树，所以的结点只有右子树的二叉树称为右斜树。两者统称斜树。

### 满二叉树：

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

### 完全二叉树：

#### 完全二叉树的特点：

## 二叉树性质：

### 性质一：

在二叉树的第i层最多有 `2的 (i - 1)次方` 个结点。

### 性质二：

深度为k的二叉树最多有` 2的 k 次方 - 1` 个结点

### 性质三：

对任何一颗二叉树T，如果其终端结点数为n，度为2的结点数为n1,

则 n = n1 + 1;

### 性质四：

具有n个结点的完全二叉树的深度为[log n]+1（long n 是以2为底的对数，[x]表示不大于x的最大整数）

### 性质五：

如果对一颗有n个结点的完全二叉树（其深度为[logn +1]）的结点按层序编号（从第1层到第[log n] + 1层，每层从左到右），对任一结点i，有：

## 二叉树的链式存储（二叉链表）：

### 概念：

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表为二叉链表

### 二叉链表结点结构定义：

```cpp
typedef struct BiTNod//结点结构
{
	TEleType data;//结点数据
	struct BiTNod* lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;
```

## 遍历二叉树：

概念：二叉树遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

### 前序遍历：

#### 方法：

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

#### 算法：

### 中序遍历：

#### 方法：

#### 算法：

### 后序遍历：

#### 方法：

规则是若树为空，则空操作返回，否则从左到右先叶子后结点方式遍历访问左右子树，最后是访问根结点。

#### 算法：

## 二叉树遍历的性质：

## 二叉树的建立：

### 伪代码：

## 线索二叉树：

### 概念：

### 线索存储结构：

#### 伪代码：

```cpp
typedef char TElemType;
typedef enum{Link, Thread} PointerTag;//Link = 0表示指向左右孩子指针，Thread = 1表示指向前驱或后继的线索

### 线索化（中序遍历）：

#### 伪代码：

```cpp
BiThrTree Pre;//全局变量，始终指向刚刚访问过的结点

### 遍历（中序遍历）：

#### 伪代码：

}
```

### 使用场合：

如果所用的二叉树需要经常遍历或者查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉树的存储结构是个不错的选择！

【数据结构】树

1 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【修仙之路】JAVA学习路线

对于异或运算的初步认识与auto用法

【JAVA经典例题】生产者/消费者问题

最近某音挺火的代码实现爱心形状

再见Swagger！拥抱smart-doc无侵入生成接口文档

【java】springboot入门核心配置

C语言-利用结构体数组实现投票计数

C语言-链表结点的插入

【java】springboot开启定时器任务

蓝桥杯竞赛题目

【数据结构】树

1 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【数据结构】树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款