二叉树难理解？不妨来看看这个（二叉树逐步刨析 一）

​

    大家好，这里是小张，上次已经把c++中类的继承（大家可以进我空间看我的上面的几篇博客）说完了，今天我们就开始来更新**二叉树系列**，希望能给大家带来帮助，废话不多说，我们现在就开始。
     在大学中常常流传着这样一段话：**大学里有一棵树，上面挂着好多人，这棵树叫做高数，再继续往前走，又有一棵树上面挂着好多人，这棵树就叫做二叉树**。可是二叉树真的很难理解吗，可能只是你理解错了方向，下面就让我来带着大家逐步刨析二叉树，来看看二叉树的真面目：

二叉树

性质

首先我们为什么要研究二叉树，而不去研究三叉树，四叉树，五叉树，甚至n叉数呢？
是因为：
1.二叉树的结构最为简单，规律性最强；
2.可以证明，所有的树都可以转化为唯一对应的二叉树，不失一般性；
3.多叉树若不转化为二叉树，进行其他运算会很难实现；

    这就是一个典型的二叉树，我们大家不难看出在这个二叉树的第一层上有（2的零次方）=1个结点，第二层上有（2的1次方）=2个结点，第三层上有（2的2次方）=4个结点，所以说在二叉树的第i层最多有2的（i-1）次方个结点。
     接下来我们来说说二叉树的深度，一个二叉树有几层就说明它的深度有多少，比如说上面的这个二叉树有三层，那么它的深度就为三，那么它最多有（2的3次方）-1=7个结点，所以说一个深度为n的二叉树至多有（2的n次方）-1个结点。

二叉树的分类

二叉树的一些重要的性质说完了，接下来我们来说说两种特殊形式的二叉树：
1.满二叉树

如果一个二叉树的结点数为（2的n次方）-1个，那么它就是满二叉树，如上图所示，满二叉树的编号是从最上面的根节点开始，自上而下，自左而右，每一个结点都有元素。
2.完全二叉树

如果从一个满二叉树中，从最后一个结点开始，连续的去掉任意个结点，即是一颗完全二叉树（一定得是连续的去掉，去掉之后，必须得与满二叉树的编号对应）

像这样子的就是非完全二叉树，是因为它并没有连续的去掉结点
所以说

二叉树的存储结构

接下来我们来说说，二叉树的存储结构，二叉树也分为顺序存储结构和链式存储结构，其中链式存储结构又分为二叉链表和三叉链表。
首先我们先来说说而二叉树的顺序存储结构，二叉树的顺序存储是按照满二叉树的结点编号，依次存放二叉树中的数据元素（实际上就是一个数组，完全可以把顺序二叉树理解成一个数组），如下图所示：

详细代码如下（跟个数组一样）：

//二叉树的顺序存储//代码如下typedefstructbitree{char data[1000];//里面的1000可以进行更改}biTreeNode,*strTree;

但是按照二叉树的顺序存储的话，有可能会造成存储空间的浪费，如下图所示：

如上图我们只是想存储8个元素可是已经用掉了12个元素的空间，造成了4个空间的浪费，如果此时我们要存储更多更加稀疏的元素的话，将会浪费到更多的内存，所以此时我们就需要引入链式存储结构，来使我们存储的空间利用率变大。

下面我们来说说二叉树的链式存储结构
• 链式存储由三部分构成，指向左孩子结点的指针（Lchild）；
• 结点存储的数据（data）；
• 指向右孩子的指针Rchild）；

下面为一个二叉树ABCDEFG的链式存储结构

下面是二叉树链式存储结构的代码：

//二叉树的顺序存储//代码如下typedefstructnode{char data;structnode*leftchild,*rightchile;//左孩子，右孩子}biTreeNode,*strTree;

接下来说说三叉链表，三叉链表的示意图如下：

    为什么有了二叉链表，还要有三叉链表呢，是因为三叉链表可以通过指针找到自己的上一个元素即双亲结点，这样的话当一个二叉链表很长的时候，通过将二叉链表改变成三叉链表可以大大的提高遍历链表中元素（遍历元素在接下来的博客中会有详细的介绍）的速度，同时也会大大的减少时间复杂度。

下面进行代码的实现

//三叉树的链式存储（三叉链表）//代码如下typedefstructnode{char data;structnode*leftchild,*rightchile,*parent;//左孩子，右孩子,双亲，多了一个指向双亲的指针}biTreeNode,*strTree;

    到了这里今天关于二叉树的一些知识点就全部说完了，以后这个系列还会**持续的进行更新**，希望大家可以多多**关注一下小张,多多支持一下小张**，这是小张第一次用MD编辑器进行写的博客如果有**不对或者不好的地方，还望大家多多指教**，小张在这里**提前谢谢大家啦！**