数据结构——树与二叉树

作者：几冬雪来

时间：2023年3月22日

内容：数据结构树与二叉树的讲解（介绍）

目录

前言： 

1.树的概念：

2.树与非树：

3.树的定义： 

4.树的应用：

二叉树：  

1. 特殊的二叉树：

2.二叉树结点的数量：

结尾： 

---

前言： 

在上一篇博客中我们讲解完毕了栈和队列的基本内容，而在栈与队列之后的每一个板块对于我们来说都是一个不小的挑战，而今天我们要讲解的就是数据结构中的——树。 

1.树的概念：

 要学习一个板块的知识，我们就要先去了解它，那么什么是树呢？

对比起我们之前学习的线性数据结构的栈和队列不同，树是一种非线性的数据结构，同时由n个结点组成的一个有层次关系的集合。 

而且这个树上有一个特殊的结点，我们称之为根结点，它没有前驱结点。

在这里我们树也有很多需要认识的知识点。

这些我们都要有所了解。

2.树与非树：

但是在我们刚刚进入数据结构树这个板块的学习中，我们已经会被一些看起来像树但是实际上却不是树的结构误导。那么这些非树的图是怎么样的？

以上就是3种非树的情况，在这里判断一个看起来像树的数据结构究竟是不是树，我们有几种方法。 

1. 子树不相交

2.除根结点外，每个结点有且只有一个父结点

3.一棵N结点的树有N-1条边

3.树的定义： 

既然知道了树的构成及概念，那么为我们的树进行定义也是在所难免的？

那这里我们要怎么定义树呢？定义树的话，我们可以用我们以前学习过的数组定义和链表定义。 

可是这里用数组和普通链表存储的话不是很方便。要定义树的话，我们就要用到一种奇特的存储方式。

这里我们定义两个结构体指针，第一个指针指向的是我们根的第一个结点，第二个指针则是我们树中的兄弟结点。 

这种结构又被我们叫做——“左孩子右兄弟”表示法。 

4.树的应用：

虽然如此，但是实际上我们的树在我们日常生活中并不经常使用。在平常我们更多的使用二叉树来解决问题。

在我们的日常中，运用数最多的地方就是在电脑里面开辟文件等操作。

二叉树：  

简单的介绍完树后，接下来我们就要在树的基础上来开始讲解二叉树了。 

1. 特殊的二叉树：

在我们的二叉树中有两种特殊的二叉树。

第一种除了最后一行的根没有结点以外，其余的每个根都对应两个结点。这一种二叉树被我们称为——满二叉树。

第二种最后一行的结点没有满，但是它们符合从左到右依次排列连续的被我们称为——完全二叉树。

同时满二叉树也是一种特殊的完全二叉树。

2.二叉树结点的数量：

接下来就是来计算我们二叉树结点的数量。在高度为h的满二叉树中结点的数量为多少。 

这就类似我们在数学所学习到的等差数列，最后满二叉树结点的数量为2^h - 1。

那么接下来就是我们可能是完全二叉树，这里我们就要求二叉树结点的取值范围。因为是完全二叉树，所以我们的前h-1行的结点都是满的。 

因为前h-1行都是满结点，因此这里我们的结点数量为2^(h-1)-1。又因为我们最后一行最少也要一个结点，因此这里的结点就变为2^(h-1)个。

在计算结点数量的时候我们也要知道一个小知识点。

对任意一棵二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0= n2 + 1，度为0的永远比度为2的多一个。

同时在满二叉树中只有度为0和度为2的，在完全二叉树中有度为1的N1，在完全二叉树中N1不是1就是0。 

结尾： 

到这里我们的树和二叉树就介绍的差不多了，但是二叉树的用法并没有就此结束，在后面我们将会介绍运用二叉树来实现我们的堆等一系列操作与题目的方法。最后希望这篇博客能让大家稍微了解一下树和二叉树。