个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：简单认识树

  希望大家每天都心情愉悦的学习工作。 

             目录     

树的概念：

树中的概念：

树的表示：

树的实际应用：

二叉树的概念：

特殊的二叉树：

二叉树的性质：

二叉树的存储结构：

1. 顺序存储

2. 链式存储

树的概念：

树都见过吧！下面是一个树。

周树人也算树吧（开玩笑的） 

在数据结构中的数，和上面的不太一样哦，我们来看下都什么不一样的地方吧！

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

1. 有一个特殊的结点，称为根结点，根节点没有前驱结点 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。

2. 每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

3.因此，树是递归定义的。

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

 就是不可以指向逻辑上的水平方向的节点，要指向父亲或者孩子，也不可以成环状结构。

 树中的概念：

下面我们说下树中的概念，我们用这张图来认识下上述的概念。

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

上述的就是树中的概念了。（红色字体是关键）。

树这个数据结构是我们现实中的树逆置，再结合上人类的亲缘关系结合的结果。

树的表示：

树常见的表示方式是左孩子，右兄弟的表示方法。

struct Tree{int val;struct Tree* child;struct Tree* brother;};

我们使用一个 child 指针，指向孩子，然后使用一个 brother 指向它的兄弟，如果没有兄弟和孩子，那么就指向NULL。

比如下面一个树：

我们画一下示意图吧。

没有指向的都是指向NULL，我们只需要把 Kid 指向第一个孩子，Bro 指向兄弟（相同父亲结点的兄弟） 其他的没有孩子，没有兄弟的指向为NULL，就可以得到一颗相匹配的数。

树的实际应用：

树可以表示文件系统的目录：

 这个就是一个树，它就很好表示了文件系统,树的根是   /  。

二叉树的概念：

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 

我们得到了两个性质：

1. 二叉树不存在度大于2的结点 （二叉树，每个节点最多有两个孩子）

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 

二叉树也分为下面几种情况：

特殊的二叉树：

树都见过吧，这么标准的树见过没？

 我们在数据结构中叫他二叉树，而上图中的刚好是二叉树中特殊的一个树，叫做满二叉树。

下面我们看下特殊的树： 

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。
要注意的是满二叉树是一种特殊的完全二叉树

区分下满二叉树和完全二叉树：

二叉树的性质：

              

 上述的性质，都是通过数学证明得到的，可以自己证明，也可以记住性质。

二叉树的存储结构：

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; // 当前节点值域}；

祝大家端午节快乐！ 吃粽子吧！