【数据结构】树（Tree）

✨✨✨专栏：数据结构     

          🧑‍🎓个人主页：SWsunlight

目录

 一、基本概念：

1、定义：

​编辑

​编辑

2、树的成分：

3、树的性质：

二、存储方式：

​编辑

双亲表示法：

孩子表示法：

孩子兄弟表示法（左孩子右兄弟）：

 三、二叉树：

概念：

存储方式：

1、顺序存储（顺序表） 

2、链式存储（链表）

遍历方式：

前言：

​编辑

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

1、前序遍历：

2、中序遍历：

3、后序遍历：

4、层序遍历：

二叉树链式结构的实现链接：

 一、基本概念：

1、定义：

        树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。为了使其抽象变得具体、易理解，且 因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的树

如下图：可以将最上面想象成树根，开始发散，然后就分化枝条 👉到最后没有枝条（黑色线）连接的是叶子(叶子节点)  

下图就是典型的树结构，树枝是不会有叶子的，所以只有分到最后一步了才是叶子；

注意：你看见过树的枝条会和另一根枝条相交么？？正常情况的树不会的；换一个思路：可以理解为这是一个家族族谱，最上面的节点就是老祖，他生了孩子，孩子又继续生孩子，到你这一代即（叶子）  你想一下：家庭关系能乱掉么？？要是随便一个祖先都能相交，岂不是伦理问题了！！！乱了，一切都乱了！！！！恐怕这个世界都疯了！！！

图中文字很好理解吧！一个人肯定只有一个爹，当然有个例外——老祖，它的父亲我们找不到，暂且没有

总结：

树是一种非线性的数据结构，它表现的关系是一对多

它是由n（n>=0）个结点组成的有限集，当n = 0时此时只有一个根节点，称为空树。

在任意一棵非空树中应满足：

1.有且仅有一个特殊的根节点，根节点没有前驱结点

2.每一个非根结点有且只有一个父亲结点

   除了根结点外，每个子结点可以分为多个不相交的子树，并且子树是不相交的

3.树是递归定义的

4.一颗N个结点的树有N-1条

2、树的成分：

前言：接下里讲述的各种名称是根据选则参考系来说的（例子为开头那张树的图）我们可以选整体一颗树来论，然后在树里面又有许多子树

总结：任何一棵树包含：根和子树——>{根+N棵子树（N>=0）};

1. 根节点：类比树根，，没有前驱节点，即没有父亲节点的节点，有且只有一个。所有节点通过直接或间接方式都能找到此根节点。如：A就是这颗树的根节点
2. 节点的度：一个节点含有孩子的个数（或者说子树的个数，是我生的孩子（二代），即这个节点有几个孩子）。         如：A的度为3 、B的度为2、E的度为0、J的度为0；
3. 叶节点/终端节点：度为0的节​，类比树叶​​​​​​ 。            ​​​​​如：J、F、K、L、H、I
4. 非终端节点/分支节点：度不为0的节点。           如：B、C、D、E、G
5. 父亲节点/双亲节点：若一个节点含有子节点。    如：A是B和C、D的父亲
6. 子节点/孩子节点：一个节点含有子树的根节点（有父亲）。       如：B是A的孩子（子）节点，若是将B看成一颗子树的根节点 那么 E是B的孩子节点
7. 兄弟节点：具有同一个父亲节点（亲兄弟）。           如：E和F是兄弟节点
8. 堂兄弟节点：双亲节点在同一成的节点互为堂兄弟。              如：E与G、H、I节点互为堂兄弟
9. 节点的祖先：从根节点到该节点所径分支上（唯一路径上）的所有节点（“直系亲属”）如下：红色圈就是一个路径，J的祖先就是E、B、A ；  而A是所有节点的祖
   1. 
10. 子孙：以某个节点为根的子树种，任意一个节点都是该节点（根）的子孙。                 如：B的子孙包括E、F、J
11. 树的度：一颗树中，最大的