【数据结构】树以及二叉树的概念

布满荆棘的人生 2024-03-30 09:29 56阅读 0赞

> 作者：一个喜欢猫咪的的程序员
> 
> 专栏：《数据结构》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![c1dbb8e133db4fb1b75e44e7e53ecf24.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> 树的概念：
> 
> 树的相关概念：
> 
> 树如何表示：
> 
> 兄弟孩子表示法：
> 
> 二叉树的概念及结构：
> 
> 二叉树的概念：
> 
> 现实中的二叉树：
> 
>  特殊的二叉树：
> 
> 二叉树的性质 ：
> 
> --------------------

## 树的概念： ##

> 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。![148465994d3b436195674a82d4b06556.png][]![ff064426955d4dd3bc0a847d522d7cb6.png][]
> 
>  *  有一个特殊的结点，称为根结点，**根节点没有前驱结点，如上图的A**
>  *  除根节点外，**其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm**，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
> 
> ![485edbc8a39f497aaa590c3be308fad3.png][]
> 
>  *  因此，**树是递归定义**的。

**注意：树形结构中，子树之间不能有交集，否则就不是树形结构**

![5e48ac2146624b27a088377509bbeaff.png][]**都不是树**。第一个图是因为子树不能有交集。第二个和第三个图是除了根节点以外都只能有一个父节点。

--------------------

## 树的相关概念： ##

![f9b42365aea34dc59961a19c316dd9f7.png][]

**打√的较为重要。** ![efea4e4e77fe4dbc91d08db4e9a27cbf.png][]

>  *  度就是该节点含有的子树个数，比如A的子树有6个，F的子树有3个。
>  *  叶节点就是就是没有子树的节点，如下图
> 
> ![213beeee462743aba16ed4071139e39c.png][]
> 
>  *  终端节点（分支节点）：有子树的节点。如下图
> 
> ![a354790eedf843f0a8272db82927c2b6.png][]
> 
> 那根节点一定是分支节点吗？
> 
> 那要看根结点的度是不是**0，不是零那就它就是分支结点**，否则就不是。
> 
>  *  父节点就是，节点的上一个节点，比如E就是J的父节点。
>  *  字节就是节点的下一个节点，比如J就是E的子节点。
>  *  兄弟节点就是有相同父节点的两个节点，比如P和Q的父节点都是J，因此P和Q是兄弟节点。
>  *  树的度是整个数中所有节点中，最大度的节点的度数，比如上图这颗数的树的节点是6。
>  *  节点的层次是这样的，根节点的那一层为1，下一层为2，以此类推。
> 
> ![72142133e3c2440ab52a0f7764fc5ca0.png][]
> 
>  *  树的高度：为节点的层数的最大值。
>  *  堂兄弟节点：就是当他们的父节点在同一层的两个节点叫做堂兄弟节点。
> 
> ![33341ad1f35544a5b31cbb975380046b.png][]
> 
>  *  祖先：就是一个节点从他自身一直向上直到根节点，一路上经过的节点都叫祖先。以Q节点为例![ba81ef95a0014ddab99a0f314f491cba.png][]
>  *  子孙：以某一个节点向下走所有的节点都叫子孙，以E为例
> 
> ![6f148695c9c0425b85f979d64b2b54d3.png][]
> 
>  *  森林：互不相交的节点的集合

--------------------

## 树如何表示： ##

### 兄弟孩子表示法： ###

> 我们用一个指针**child**指向孩子，来找到下一级，用一个指针**brother**指向兄弟节点来找到同层的节点。![4657cba966994477afc473e4a761adfd.png][]

--------------------

## 二叉树的概念及结构： ##

### 二叉树的概念： ###

> 一棵二叉树是结点的一个有限集合，该集合:
> 
>  *  或者为空
>  *  由一个根节点加上两棵别称为左子树和右子树的二叉树组成

![dcde5932738c4aafbd4a36725ab31640.png][]

1. 二叉树不存在度大于2的结点  
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

--------------------

### 现实中的二叉树： ###

![94ee6152f3cd4f6a8bf98a23518a2d43.png][]![436ab1301b7d4c70a7b9cd68ef24c927.png][]

--------------------

### 特殊的二叉树： ###

*  满二叉树：一个二叉树，如果**每一个层的结点数都达到最大值**，则这个二叉树就是满二叉树。也就是说，**如果一个二叉树的层数为K，且结点总数是 2^k-1**，则它就是满二叉树。
 *  完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

![ed7bbbefc3364cd785172e19802e309c.png][]

--------------------

### 二叉树的性质 ： ###

>  *  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1） 个结点.
>  *  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 .
>  *  3. **对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1**
>  *  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2（n+1）
>  *  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
> 
> **1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点**
> 
> **2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子**
> 
> **3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子**

性质1： 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^（i-1） 个结点.![1fbb512371c84589b32e1563c3558d8c.png][]

性质二：利用等比数列求和就好了。

![f1df26b8ffd54c7b9beb3d67f4bb485c.png][]

**性质五可以用性质三进行推导。**

--------------------

[c1dbb8e133db4fb1b75e44e7e53ecf24.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/48535c8f4d5a487592b5d36e73198bee.jpeg
[148465994d3b436195674a82d4b06556.png]: https://img-blog.csdnimg.cn/148465994d3b436195674a82d4b06556.png
[ff064426955d4dd3bc0a847d522d7cb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/18176e70e74f4974ab944ccdfca31b9d.png
[485edbc8a39f497aaa590c3be308fad3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8b7ea6744b2a419cbf1dee41ff5ec24b.png
[5e48ac2146624b27a088377509bbeaff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/18a3488c1f4d47c1ae567a4fde467f46.png
[f9b42365aea34dc59961a19c316dd9f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/65be3942240b413395e5d21d48d83031.png
[efea4e4e77fe4dbc91d08db4e9a27cbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/459b8eb880974e4391090eaa07826714.png
[213beeee462743aba16ed4071139e39c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/74c5b5e305dc4c69b2a3d13823406dec.png
[a354790eedf843f0a8272db82927c2b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7c8fc7dab68d4b7f8e5e09ac6331f01f.png
[72142133e3c2440ab52a0f7764fc5ca0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/65980978f96d45ef9a7b8c14d91bd607.png
[33341ad1f35544a5b31cbb975380046b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b5d3ceb80c0343ea9adacab2d0558be0.png
[ba81ef95a0014ddab99a0f314f491cba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0cd229085d3f41e192a474c085799191.png
[6f148695c9c0425b85f979d64b2b54d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bf28c402ba524dab8eb513970b366103.png
[4657cba966994477afc473e4a761adfd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/706ffaf9e929416c91f01a6d022cb7b3.png
[dcde5932738c4aafbd4a36725ab31640.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/02edde4c2db240509fb6cb94682c435c.png
[94ee6152f3cd4f6a8bf98a23518a2d43.png]: https://img-blog.csdnimg.cn/94ee6152f3cd4f6a8bf98a23518a2d43.png
[436ab1301b7d4c70a7b9cd68ef24c927.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0614d0198aa2416a9a084861ff7bdc4b.png
[ed7bbbefc3364cd785172e19802e309c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7ad35e77c7f34f758eb0785cf15a9965.png
[1fbb512371c84589b32e1563c3558d8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f7a54d7ccc9a4fafa9950bde98b3997c.png
[f1df26b8ffd54c7b9beb3d67f4bb485c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7f5221840d9c493d9f14059f6bd468d3.png