1.二叉树的种类

1.满二叉树:

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

2.完全二叉树

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

• 这个是二叉树

• 

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

• 

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

3.二叉搜索树

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

• 

• 二叉搜索树对结点的布局是没有要求的，元素有顺序就可以。

• 平衡二叉搜索树

  • 左子树和右子树的高度差不能超过1。

1.顺序存储

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

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

2.链式存储

一般用的都是链式存储。

扩展：

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

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

中序遍历：左中右。4125768

后序遍历：左右中。1247865

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

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