排序二叉树的构造过程（一文搞定二叉树）

二叉树很重要

树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。单就面试而言，在 leetcode 中二叉树相关的题目占据了300多道。同时，二叉树在整个算法板块中还起到承上启下的作用：不但是数组和链表的延伸，又可以作为图的基础。

举个例子，比如说我们的经典算法「快速排序」和「归并排序」，对于这两个算法，你有什么理解？如果你告诉我，快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历，那么我就知道你是个算法高手了。

一些概念 结点

结点是数据结构中的基础，是构成复杂数据结构的基本组成单位

树

树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：

有且仅有一个特定的称为根（Root）的结点； 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，树的定义还需要强调以下两点：

n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。 m>0时，子树的个数没有限制，但它们一定是互不相交的。

一颗普通的树

结点的度

结点拥有的子树数目称为结点的度。

结点层次

从根开始定义起，根为第一层，根的孩子为第二层，以此类推

二叉树 定义

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

二叉树特点 1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。 2）左子树和右子树是有顺序的，次序不能任意颠倒。 3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。 斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

二叉搜索树

二叉搜索树又被称为二叉排序树，那么它本身也是一棵二叉树，那么满足以下性质的二叉树就是二叉搜索树：

1、若左子树不为空，则左子树上左右节点的值都小于根节点的值 2、若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值 3、它的左右子树也要分别是二叉搜索树

平衡二叉树

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

满二叉树

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。 满二叉树的特点有：

1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。 2）非叶子结点的度一定是2。 3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

从根往下数，除了最下层外都是全满（都有两个子节点），而最下层所有叶结点都向左边靠拢填满。 构造一颗完全二叉树就是【从上到下，从左往右】的放置节点。

满二叉树和完全二叉树的区别 左侧为满二叉树但不是完全二叉树，要补全的话可以给第二层最左节点下加两个子节点，或删除当前最下层的两个节点。 右侧是一颗完全二叉树但并不是满二叉树，因为最下层最后一个节点没有兄弟节点，即其父节点只有一个子节点，不满，补满的话再加一个右子节点即可【满二叉树的节点要么没孩子，要有就一定得是俩】。

二叉树的存储结构（序列化） 顺序存储

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

当二叉树为完全二叉树时，结点数刚好填满数组。那么当二叉树不为完全二叉树时，采用顺序存储形式如何呢？下图浅颜色的为空

其中，∧表示数组中此位置没有存储结点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。 因此，顺序存储一般适用于完全二叉树。