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

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

📚️1.树

🎥 1.1树型结构概念

树是一种非线性 的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。 把

它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的 。

🎥 1.2特点

1.有一个特殊的结点，称为根结点，根结点没有前驱结点 2.除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继 3.树是递归定义的。

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

如下图：

​

注意：

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.二叉树存储和遍历

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

🔥🔥遍历（重点）

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

遍历 (Traversal) 是指沿着某条搜索路线，依次对树中每个结 点均做一次且仅做一次访问 。 访问

结 点所做的操作依赖于具体的应用问题 ( 比如：打印节点内容、节点内容加 1) 。 遍历是二叉树上最

重要的操作之一，是二叉树上进行其它运算之基础。

~~~前序遍历：

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.📚️总结

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

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

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

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

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