关于二叉树，你应该了解这些。（二叉树的理论基础）

推荐视频——关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

理论基础，这些都是我们平时刷题应该掌握的内容。

把基础打牢了，有了逻辑基础，学的才会更好一些。

1.二叉树的种类

1.满二叉树:

• 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树叫做满二叉树。
• 结点数量2^k-1

在这里插入图片描述

2.完全二叉树

• 除了底层以外，其它层都是满的，底层是从左到右连续的。
• 这个是二叉树

在这里插入图片描述

• 这个就不是二叉树，底层不连续。

在这里插入图片描述

满二叉树一定是一棵完全二叉树，但完全而二叉树不一定是满的。

3.二叉搜索树

• 在它里面的结点顺序，左子树的所有结点都小于中间结点，右子树的所有结点都大于中间结点。

在这里插入图片描述

• 二叉搜索树对结点的布局是没有要求的，元素有顺序就可以。
• 平衡二叉搜索树
  • 左子树和右子树的高度差不能超过1。

2.二叉树的存储方式

1.顺序存储

在这里插入图片描述

用这个字符数组来保存二叉树。

在这里插入图片描述

**2*i+1——左孩子，2 *i+2——右孩子。 **

2.链式存储

一般用的都是链式存储。

在这里插入图片描述

3.二叉树的遍历

扩展：

• 深度优先搜索：一般都是用递归的方式来实现的，前序遍历，中序遍历，后序遍历，都是深度优先搜索。(迭代法也可以实现前中后序，非递归的方式。)
• 广度优先搜索：一层一层的去遍历，或者是一圈一圈的去遍历。层序遍历就是广度优先搜索的一种。

在这里插入图片描述

前序遍历：**中左右。**5412678

中序遍历：左中右。4125768

后序遍历：左右中。1247865

4.二叉树结点的定义

将二叉树理解为一个链表就会简单很多。

struct TreeNode
{
   int val;//放数值
   TreeNode* left;
   TreeNode* right;
    //实现一个构造函数，在new一个结点的时候，方便对其进行初始化。
   TreeNode(t):val:t,left(NULL),right(NULL);	
}