二叉树的概念及结构
二叉树在我们的想象中长这样
下图是满二叉树
二叉树有左右子树
1是根结点，
1的左子树是2，右子树是3；
2是根结点，
2的左子树是4，右子树是5；
3是根结点，
3的左子树是6，右子树是7；
这个满二叉树有3层，则深度/高度为3；
4 和 5为兄弟节点，它们有相同的父节点 2；
4 5 6 7这4个节点都是叶节点，它们没有子节点；
3 的子节点是 6 和 7；
第一层有1个节点，是其他节点的祖先。
第二层有2个节点，
第三层有4个节点，
我们不难发现其规律，那就是在满二叉树中，每一层的节点数成等比数列。
我们可以用等比数列求和公式求出满二叉树的总的结点个数，
还有一种特别的二叉树，叫做完全二叉树
如上图，完全二叉树的特点是，前2层（前n-1层）的结点都是满的，没有空缺；
但是第3层（第n层）的结点有空缺，
第三层的结点从左到右排列，中间不能有空缺的结点，
唯一的空缺只能出现在右边，
下图所示的就 不是 完全二叉树
二叉树的3种遍历方式
我们以这棵树为例，讲解所有遍历的方式
1.前序遍历
前序遍历的顺序是 根 ，左子树， 右子树
最终的遍历结果是 1 2 4 5 3 6 7
观察最下面一行，画出的框框分隔开结点，
可以看出，
1是根结点，2是左子树，3是右子树；
2是根结点，4是左子树，5是右子树；
3是根节点，6是左子树，7是右子树；
4是根节点，N是左子树，N是右子树
(N代表NULL，表示空节点，同理可分析5,6,7作为根结点时的情况)
2.中序遍历
中序遍历的顺序是左子树， 根，右子树
最终遍历的结果是 4 2 5 1 6 3 7
观察最后一行，左子树（2）——根(1)——右子树 （3），
左子树（4）——根(2)——右子树（5） ，
左子树（6）——根(3)——右子树（7） ，
左子树（N）——根(4)——右子树（N） ……
3.后序遍历
后序遍历的顺序是左子树，右子树， 根
最终结果是 4 5 2 6 7 3 1
观察最后一行可以发现，根（1）在最后面
左子树——右子树——根（1）
左子树（4）——右子树（5）——根（2）
左子树（6）——右子树（7）——根（3）
左子树（N）——右子树（N）——根（4）
……
二叉树的代码实现
堆的概念
在二叉树中，堆（Heap）是一种特殊的完全二叉树结构，它满足堆属性（Heap Property）。堆属性分为两种：最大堆（Max Heap）和最小堆（Min Heap）。
-
最大堆（Max Heap）：在最大堆中，每个父节点的值都大于或等于其所有子节点的值。这意味着根节点（树的顶部节点）是树中的最大值。
-
最小堆（Min Heap）：在最小堆中，每个父节点的值都小于或等于其所有子节点的值。这意味着根节点是树中的最小值。
上图是最小堆，每个父节点的值都小于（或等于）其所有子节点的值，根节点1是树中的最小值。
上图是最大堆，每个父节点的值都大于（或等于）其所有子节点的值，根节点7是树中的最大值。
堆的存储通常使用数组来实现，因为完全二叉树的性质允许我们用一个数组来紧凑地表示它，而不需要使用指针或链表。在数组中，对于给定的索引 i，其父节点的索引是 (i-1)/2（对于从0开始的索引），左子节点的索引是 2*i+1，右子节点的索引是 2*i+2。这种表示方法简化了堆的插入和删除操作。
我们继续用这张图来分析一下
变成数组结构如下
满足：在数组中，对于给定的下标 i，其父节点的下标是 (i-1)/2（对于从0开始的索引），左子节点的索引是 2*i+1，右子节点的索引是 2*i+2
代码实现
typedef int HPDataType;typedef struct Heap {HPDataType* a;//用数组存数据int size;//当前数组存放的数量int capacity;//数组容量}HP;具体的建堆过程请阅读我的另一篇博客：http://t.csdnimg.cn/FNBfk
