让二叉树无处可逃

志不立，天下无可成之事。 ——王阳明

---

1、树？什么是树

1、1、基本概念

树也是属于一种数据结构，它是一种非线性的数据结构，与栈，队列和链表是不同的存在。
由n(n>=0)个有限的结点组成的具有层次关系的集合。至于为什么是树呢？其实按照结构图来看，把一颗二叉树的结构图倒过来就像一颗树了。

也就是像这样。
1、树都会有一个特殊的结点，称为根节点，根节点没有父节点
2、除去根节点之后，其余的结点被分为M(M>0)个互不相交的集合T1,T2,Tm，其中每一个集合又是一棵结构类似的子树。
3、因此，树是递归定义的。(在后面的关于树之类的问题上，递归的解决方法占很大一部分)
注意：根据观察，其实真正的树，根和根之间不会相互交错。那计算机的树其实也是，子树也是不能有交集的，否则将不会是树的结构。

1、2、树的相关概念

度：一个节点的子树的个数。(例如A的度就是6)
叶节点或终端节点：度为0的节点称为叶子节点(就例如B,C，等等)
分支节点或非终端节点：度不为0的节点(例如 D,E,J等)
双亲结点或父节点：若一个结点有子节点，则这个结点称为其子节点的父节点：(例如A是B的父节点)
孩子结点或子节点：一个节点含有子树的根结点称为该子节点的父节点：(例如B是A的孩子节点)
兄弟节点：具有相同父节点的节点互称为兄弟节点；(B、C是兄弟节点)
树的度：一棵树中，最大的节点的度称为树的度；(树的度为6)
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； (例如这棵树的高度为4)
堂兄弟节点：双亲在同一层的节点互为堂兄弟；(H、I互为兄弟节点)
节点的祖先：从根到该节点所经分支上的所有节点；(A是所有节点的祖先)
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。(所有节点都是A的子孙)
森林：由m（m>0）棵互不相交的树的集合称为森林；

1、3、树的表示方式

相对于线性表的表示，由于树的不确定的性质，树的存储表示会相对比较麻烦，不只是需要保存树中的数值，还要保证节点和节点之间的关系。由于树的复杂性，所以树的表示方法也会出现多元化，就比如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法等。在这里不方便多说，就简单的介绍几种常用的方法孩子兄弟表示法（也是一个很妙的表示方法）

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

这就是通过孩子找兄弟，让父节点只指向一个节点，而处于同一层的都通过，带头的兄弟来找到。

下面的这个就是我简单的写一下其余的表示方法，因为相对于其余的方法，我对于孩子兄弟法还是更喜欢一点的。

这里的我想到的问题，在这篇文章有详细的讲解，关于指针的，如果不熟悉，可以再看一下

1、4、树的实际运用

2、二叉树？只有两个分支吗？

2、1、基本概念

二叉树也是一棵节点的有限集合
1、可能为空
2、由根节点加上两棵左子树和右子树的二叉树构成。
1、二叉树不存在度大于2的节点
2、二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序的树
二叉树也可以通过递归的方式来组成，二叉树也只能分为这几种情况

2、2、二叉树的相关定义

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

2、3、二叉树的相关性质

二叉树很类似与我们高中学习的生物中的关于细胞分裂的公式。(下面的公式都是相当于根节点的层数是1的情况下)
1、一棵非空的二叉树的第i层上的节点个数最多有2^(k-1)个节点。
2、深度为h的二叉树的最大节点数为2^h-1。
3、如果度为 0 的节点个数为 n0 ，度为 2 的节点个数为 n2 ，那么则有n0=n2+1
4、一个有n个节点的满二叉树，那么它的深度为log(n+1)，log是以2为底
(ps:明天出一个关于树相关的问题集合，感兴趣的记得关注!)

2、4、二叉树的表示方式

看过树的介绍，不难发现，二叉树相对与树的结构多样，规则变化，二叉树相对简单，所以对于二叉树的存储方式来说也是更简单一点
1、顺序存储
顺序结构就是用数组来存储，一般来说，数组的使用**只适合表示完全二叉树，**对于不是完全二叉树时会有空间的浪费。二叉树顺序存储在物理结构上是数组，但是逻辑结构上是一棵二叉树。
正常来说，这种的数组结构都是大部分存储 堆

2、链式存储
用链表来表示一棵二叉树


转换成代码的形式，也就是相当于这样

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

3、总结

对于二叉树其实本质上的基础就只有那么多，下面会推出二叉树的衍生的结构，堆。对于二叉树的问题和操作都会在之后推出，敬请期待。