树

在数据库中，树是一种数据结构，用于组织和存储数据，使得可以高效地进行插入、删除和查找操作。它通常用于表示层次关系或者有序集合。

基本概念

节点：树结构中的每个元素都称为节点。
根节点：树的最顶端节点。
子节点：从某个节点延伸出的节点称为该节点的子节点。
父节点：如果一个节点拥有子节点，那么这个节点就是其子节点的父节点。
兄弟节点：共享同一父节点的节点互称为兄弟节点。
叶节点：没有子节点的节点称为叶节点或终端节点。
路径：从一个节点到另一个节点的序列，其中包含从前者到后者的边的集合。
深度：节点的最大路径长度。
高度：节点的最大路径长度，包括节点本身。
度：节点的度是指节点拥有的子节点数。树的度是指树中所有节点的度的最大值。

结构定义

树的定义有很多种，根据不同的逻辑结构有不同的定义方法，在这里我们使用的是：左孩子右兄弟表示法。这种表示法简化了树的结构。

struct TreeNode
{
struct TreeNode FirstChild1;
struct TreeNode pNextBrother;}

二叉树

二叉树是一种特殊的树状数据结构，其主要特点包括：
每个节点最多有两个子节点，通常分别称为左子节点和右子节点。
具有明确的层次结构，从根节点开始逐渐向下扩展。
二叉树有多种类型，比如：
满二叉树：所有非叶子节点都有两个子节点，并且所有叶子节点都在同一层。
设满二叉树的深度为，则满二叉树的节点个数为 2^h-1。

完全二叉树：除了最底层可能不完全填满外，其他各层节点数都达到最大，并且最底层的叶子节点都集中在左侧。
设完全二叉树的深度为，则完全二叉树的节点个数为[2^（h-1）， 2 ^h-1]。

二叉树的存储

二叉树的存储分为数组存储和链式存储，今天这篇文章我们介绍的是数组存储。数组存储的前提是二叉树为完全二叉树或者满二叉树。

堆

根堆是一种完全二叉树，它的每一层节点都填满，除了最后一层可能有部分节点空缺，但空缺位置都集中在最右侧。根堆可分为大根堆和小根堆两种类型：
大根堆：在逻辑上的二叉树结构中，根结点大于子结点，总是最大的，并且在堆的每一个局部都是如此。大根堆的根结点在整个堆中是最大的元素。

小根堆：在二叉树的结构中，根结点小于子结点。例如{1,2,3}为小根堆，{1,3,2}同样也是小根堆。