【数据结构】关于树（二叉树）的基础理论知识，你知道吗？？？

前言：

🌟🌟Hello家人们，这期讲解数据结构关于树的基础知识，希望你能帮到屏幕前的你。

🌈上期博客在这里：http://t.csdnimg.cn/jnP5G

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

                                  那么咱们开始吧 ~~~🎬🎬🎬

📚️1.树

    🎥 1.1树型结构概念

    🎥 1.2特点

💡💡总结来说：树就是递归定义的，并且每个节点只有一个前驱，和非零或者零个后继。 

如下图：

​

 注意：

1.子树是不相交的；

2.除根节点以外，其他每个节点有且只有一个父节点；

3.有N个节点就有N-1条边；

🎥 1.3名称概念

小编就用上图来解释说明：

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

2.树的度 ：一棵树中，所有结点度的最大值称为树的度；如上图：树的度为 6

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

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

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

6.根结点 ：一棵树中，没有双亲结点的结点；如上图： A

7.结点的层次 ：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推

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

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

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

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

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

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

    🎥 1.4树的应用 

文件系统管理（目录和文件）

是不是非常像一棵树呢？😊😊😊

📚️2.二叉树（重点）

     🎥2.1概念 

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

1.空节点；

2.或者由一个根节点链接两个别称为左子树，和右子树的二叉树构成

如下图：

💡💡注意：二叉树任意一个节点的度都不大于二，并且二叉树有左右之分，所以二叉树是有序的

以下的情况都为二叉树：

   🎥2.2两种特殊的二叉树

🌟🌟满儿二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。

🌟🌟完全二叉树：一棵二叉树，从左到右，依次排满（不用达到最大值），则这棵树就是完全二叉树。

如下图：

注意：满二叉树是特殊的完全二叉树。 

   🎥2.3二叉树的性质

1. 若规定 根结点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有2^(i-1) (i>0) 个结点

2. 若规定只有 根结点的二叉树的深度为 1 ，则 深度为 K 的二叉树的最大结点数是2^k-1 (k>=0)

3. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 ＝ n2 ＋ 1

4. 具有 n个结点的完全二叉树的深度k为 ⌈log2(n+1)⌉ 上取整

5. 对于具有 n 个结点的完全二叉树 ，如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 ，则对于 序号为 i 的结点有 ：

若i>0 ， 双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号 ，无双亲结点

若 2i+1<n ，左孩子序号： 2i+1 ，否则无左孩子

若 2i+2<n ，右孩子序号： 2i+2 ，否则无右孩子

   🎥2.4.二叉树存储和遍历

💡💡 二叉树的存储结构分为：顺序存储结构和类似于链表的链式存储结构。

🔥🔥遍历（重点）

小编这期只说明理论上的如何遍历，编程实现在下一期哦~~~~

         ~~~前序遍历：

NLR：前序遍历（访问根节点->访问左子树->访问右子树）

💡💡描述：在前序遍历二叉树时，先打印每个子树的根节点，然后打印左节点，如果左节点下面还有子树，那么左节点就是这棵树的根结点，进行打印，直到最后一个节点后为空，就打印最后一个节点的右树，再返回打印上一个结点的右数，不断递归。

        如上图：A为根结点，打印后，再往A的左子树遍历到B，打印B后，B又是一个子树的根结点，所以在往左子树遍历到D，此时D又为一个根节点，打印D；再往D的左子树遍历，为空那么开始遍历D的右树，为空然后递归到B，遍历B的右树.......按照此递归逻辑进行前序遍历，最终结果为：A B D C E F。

            ~~~中序遍历：

LNR：中序遍历（访问左子树->访问根节点->访问右子树）

💡💡描述：若根结点存在则先遍历左节点，左节点如果是有一个子树的根结点，又递归，直到一个左结点的左子树为空，开始返回，打印每个子树的根结点，在递归右子树，如果为空就返回，如果不为空就继续递归这个节点左子树，不断递归返回。

     如图：从A进入，递归A的左结点B，发现B也存在左节点，再次进行递归，直到D没有左子树然后打印根结点，也就是D本身，然后递归D的右，没有就返回，B的左子树遍历完了，打印B本身，然后递归B的右子数，为空就返回，A的左子树递归完了，就打印A这个根结点，再递归右子树........按此逻辑进行中序遍历，最终结果为：D B A E C F。

         ~~~后序遍历：

LRN：后序遍历（访问左子树->访问右子树->访问根节点）

💡💡描述：若根结点存在左子树和右子树，先递归左子树，直到一个节点的左子树为空后，在递归这个结点的右子数，如果为空就返回值根结点进行打印，反之继续递归这棵树的左子树，不断递归。

如上图：这里先递归到D结点，然后发现D无左右子树，就打印D本身，然后递归B的右子数，发现为空，就返回到B根结点，在递归A根结点的右子树.....按此逻辑进行后序遍历。最终结果：D B E F C A

3.📚️总结

      💬💬小编这期只总结了关于树的基础理论知识，并不涉及到关于树的相关代码，小编将详细讲述关于二叉树的的遍历以及相关代码实现。

      🌅🌅🌅还是那句话，多练！哈哈哈~~~~最后希望与诸君共勉，共同进步！！！

              💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。

                                下期预告：二叉树的遍历🌟🌟

                                       😊😊  期待你的关注~~~
————————————————