DS之二叉树
二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树可以分为5种基本形态：
(1)空二叉树。
(2)仅有根结点的二叉树。
(3)左子树为空的二叉树。
(4)右子树为空空的二叉树。
(5)左，右子树均为非空的二叉树。
图示为：
再延伸一下的话就是画出有三个结点的二叉树的基本形态：
满二叉树
一棵深度为k且有(2^K)-1个结点的二叉树称为满二叉树。
完全二叉树
深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
这两种特殊形态的二叉树的图示：
对于满二叉树(a)的深度为4，每一层上的结点数都是最大结点数。对这棵满二叉树进行连续编号，约定编号从根结点起，自上而下，自左至右。
对于完全二叉树(b)的深度为4，叶子结点只可能在层次最大的两层上出现，对任一结点，若其右分支下的子孙的最大层为l，则其左分支的子孙的最大层必为l或l+1。
二叉树性质：
(1)在二叉树的第i层上至多有2^(i-1)(i>=1)个结点。
(2)深度为k的二叉树至多有(2^k)-1(k>=1)个结点。
(3)对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
(4)具有n个结点的完全二叉树的深度为[log2n]+1，其中[log2n]表示取log2n的整数部分。
(5)如果对一棵有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1<=i<=n)，有：
1如果i=1，则结点i是完全二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点[i/2]。
2如果2i>n，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。
3如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。
二叉树的存储结构
顺序存储结构
按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元一次自上而下，自左至右存储完全二叉树的结点元素，即将完全二叉树编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。
顺序存储结构表示：
#define MAX_TREE_SIZE 100 typedef char TElemtype; TElemtype SqBiTree[MAX_TREE_SIZE];
对于上面的满二叉树和完全二叉树的顺序存储结构为：
对于一般的二叉树的顺序存储结构表示需要用到“空”的结点。
对于上面的一般二叉树的顺序存储数字0或字符^代表的是空结点。在最坏的情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)需要长度为(2^k)-1的一维数组。
链式存储结构
由二叉树的定义可知，二叉树的结点是由一个数据元素和分别指向其左，右子树的两个分支构成，因此表示二叉树的链式存储中的结点至少包含3个域：数据域，左，右指针域。最常用的就是二叉树的二叉链表存储结构。
二叉链表的结点结构
二叉链表
为了方便访问某结点的双亲，还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点。每个结点由四个域组成，其结点结构为：
这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。利用这样的结点结构表示的二叉树的链式存储结构被称为三叉链表。
还是来看最常用的二叉树的二叉链表存储表示：
typedef struct BiTNode//重新定义二叉树的二叉链表的结构
{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
二叉链表的基本操作：
Status createBiTree(BiTree &T) 按先序次序输入二叉树额结点的值(一个字符)，#字符表示空字符 构造二叉链表表示的二叉树T Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 采用二叉链表存储结构，Visit是对结点操作的应用函数 先序遍历二叉树T，对每个结点调用Visit一次且仅一次 一旦Visit()操作失败，则操作失败 Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 采用二叉链表存储结构，Visit是对结点操作的应用函数 中序遍历二叉树T，对每个结点调用Visit一次且仅一次 一旦Visit()操作失败，则操作失败 Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 采用二叉链表存储结构，Visit是对结点操作的应用函数 后序遍历二叉树T，对每个结点调用Visit一次且仅一次 一旦Visit()操作失败，则操作失败 Status LeveleOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) 采用二叉链表存储结构，Visit是对结点操作的应用函数 层序遍历二叉树T，对每个结点调用Visit一次且仅一次 一旦Visit()操作失败，则操作失败