树结构是现实世界层次关系的抽象。除此之外，将线性结构的数据组织成树型结构，特别是二叉树的结构，可以结合顺序存储和链式存储的优点，能够在O(logn)的时间内完成“增、删、改、查”。
无论是顺序存储，还是链式存储，线性表均有其优缺点。
顺序存储可以在O(1)时间内找到特定次序的元素，但是插入和删除元素需要移动大量元素，需要O(n)时间。
而链式存储插入和删除元素只需要O(1)时间，而找到特定次序的元素需要从链表头部向后查找，需要O(n)时间。
将数据组织为堆（一种数量关系有规律的特殊二叉树），生成的堆可以应用堆排序，堆是优先队列的基础。在STL中，堆以vector为底层结构。
将数据组织为平衡二叉搜索树，用于数据检索。
红黑树是一种特殊的平衡二叉搜索树，是STL map和set的基础。
哈夫曼树也是一种特殊构建的二叉树。
1 树
树形结构就像一棵倒立的树，有唯一的树根，树根可以发出多个分支，每个分支也可以继续发出分支，树枝和树枝之间是不相交的。
类似多维数组是数组的数组，树也是树的树，二叉树也是二叉树的二叉树，可以递归定义。
树（tree）是n（n≥0）个节点的有限集合，当n=0时，为空树；n>0时，为非空树。任意一棵非空树，满足以下两个条件：
1）有且仅有一个称为根的节点；
2）除根节点以外的其余节点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）。
1.1 与树相关的几个术语
● 节点——节点包含数据元素及若干指向子树的分支信息。
● 节点的度——节点拥有的子树个数。
● 树的度——树中节点的最大度数。
● 终端节点——度为0的节点，又称为叶子。
● 分支节点——度大于0的节点。除了叶子都是分支节点。
● 内部节点——除了树根和叶子都是内部节点。
● 节点的层次——从根到该节点的层数（根节点为第1层）。
● 树的深度（或高度）——指所有节点中最大的层数。
● 路径——树中两个节点之间所经过的节点序列。
● 路径长度——两节点之间路径上经过的边数。树中没有环，因此树中任意两个节点之间的路径都是唯一的。
如果把树看作一个族谱，就成了一棵家族树。
● 双亲、孩子——节点的子树的根称为该节点的孩子，反之，该节点为其孩子的双亲。
● 兄弟——双亲相同的节点互称兄弟。
● 堂兄弟——双亲是兄弟的节点互称堂兄弟。
● 祖先——从该节点到树根经过的所有节点称为该节点的祖先。
● 子孙——节点的子树中的所有节点都称为该节点的子孙。
● 有序树——节点的各子树从左至右有序，不能互换位置。
● 无序树——节点各子树可互换位置。
● 森林——由m（m≥0）棵不相交的树组成的集合。
1.2 树的存储结构
1.2.1 顺序存储
分为双亲表示法、孩子表示法和双亲孩子表示法。
数组：存储树的全部节点；
数组的元素：用结构体来描述元素数据及需要的下标；
1.2.2 链式存储
分为双孩子链表表示法和孩子兄弟表示法。
数组：存储树的全部节点；
数组的元素：用结构体来描述元素数据及一个链表指针（指向一个链表（元素为全部子节点））；
2 树与二叉树
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。
通常，树节点的度并不总是相同，在树结构数据处理时，需要将各节点的度统一为树的度，也就是多叉树，这里就有一个存储效率的问题。二叉树相对于其它多叉树，具有最高的存储效率。除此之外，二叉树与二进制、二分查找还有天然的一种联系。
二叉树和树可双相互转换。
树转换为二叉树算法：长子当作左孩子，兄弟关系向右斜。
typedef struct BinaryTreeNode{ struct BinaryTreeNode* leftChild; struct BinaryTreeNode* rightChild; int value;};typedef struct TreeNode{ struct TreeNode* child[5]; int child_count; int value;};BinaryTreeNode* ToBinaryTree(TreeNode*root){ if(root == NULL) return NULL; BinaryTreeNode* binaryRoot = new BinaryTreeNode(); binaryRoot->leftChild = binaryRoot->rightChild = NULL;//注意初始化 binaryRoot->value = root->value; binaryRoot->leftChild = ToBinaryTree(root->child[0]); BinaryTreeNode* brother = binaryRoot->leftChild; for(int i = 1; i < root->child_count;i++){ brother->rightChild = ToBinaryTree(root->child[i]); brother = brother->rightChild; } return binaryRoot;}树转二叉，前提是我们仍要把树的信息保留下来，也就是谁是谁的孩子，谁是谁的兄弟。但是二叉只能保存两个孩子，但我们可以把两个孩子改成两个关系，也就是我们利用二叉来储存关系，一个是孩子，一个是兄弟。当一个节点是另一个节点的孩子时，就放在父亲节点的左孩子上，是兄弟，就该放在右孩子上，也就是所谓的“左儿子，右兄弟”。
森林和二叉树的转换：
把森林中的每棵树的树根看作兄弟关系，把森林中的每一棵树转换成二叉树，然后把每棵树的根节点连接在右斜线上。
3 二叉树
二叉树（binary tree）是n（n≥0）个节点构成的集合，它或为空树（n=0），或为非空树。非空树T满足以下两个条件：
1）有且仅有一个称为根的节点；
2）除根节点以外，其余节点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。
3.1 二叉树第 i 层上的元素个数最多为
3.2 深度为k的二叉树，元素最多为 （二叉树的深度是指所有结点中最深的结点所在的层数）
3.3 满二叉树、完全二叉树、非完全二叉树
如图：
3.3.1 满二叉树（perfect binary tree）
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也就是除了最后一层的叶子结点上没有子结点之外，其余每层结点都有子结点。
3.3.1.1 序号为 i 的元素，双亲的序号为 （序号为0的元素是根）
3.3.1.2 序号为 i 的元素，若，则左孩子的序号为2i+1，否则是叶子；
3.3.1.3 序号为 i 的元素，若，则右孩子的序号为2i+2，否则无右孩子；
3.3.1.4 序号为 i 的元素，若且是偶数，则左兄弟的序号为i-1；
3.3.1.5 序号为 i 的元素，若且是奇数，则右兄弟的序号为i+1；
3.3.2 完全二叉树（complete binary tree）
除了最下面一层，其他层结点都是饱满的，并且最下层上的结点都集中在该层最左边的若干位置上。用层次遍历来理解的话就是层次遍历按顺序来一遍到某一位置停止，遍历过的结点全部存在。（满二叉树也是完全二叉树）
完全二叉树也具有上述元素之间的关系。
具有n个元素的完全二叉树，其深度为
3.3.3 非完全二叉树
非完全二叉树既不是满二叉树，也非完全二叉树。
3.4 二叉查找树与平衡二叉树
二叉查找树（BinarySearchTree）不但二叉树，同时满足一定的有序性：节点的左子节点比自己小，节点的右子节点比自己大。
平衡二叉树指的是，任意节点的子树的高度差的绝对值都小于等于1，并且左右两个子树都是一棵平衡二叉树，常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。
完全二叉树确实平衡（平衡因子绝对值小于等于一），但不一定是平衡二叉树。原因是平衡二叉树本质上是二叉排序树，但完全二叉树不一定是有序的。
反过来，平衡二叉树也不一定是完全二叉树。因为平衡二叉树最底层结点不一定集中在最左边。
4 二叉树应用
数据结构中属二叉树的类别最多，绝大部分都是用来服务于数据检索的。
用得最多的是平衡二叉树，有种特殊的平衡二叉树红黑树，查找、插入、删除的时间复杂度最坏为O(log n)。C++ STL中的set、map都是用红黑树去实现的，unordered_set、unordered_map则用哈希表去实现。
二叉树除数据搜索以外的经典应用是哈夫曼树。在图数据结构中，图可以生成最小生成树。
二分查找的时间效率是，其查找次数相对于n来说就小多了（特别是当数据量巨大时）：
C++的math.h只有以自然数e为底的log()和以10为底的log10()，有对数换底公式：
－End－
