树结构
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为节点）按分支关系组织起来的结构，很象自然界中的树那样。
一棵树（tree）是由 n（n > 0） 个元素构成的有限集合：
- 每个元素称为节点（
node）。 - 有一个特定的节点，称为根节点或根（
root）； - 除根节点外，其余节点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）。
-
只有根节点的也是一棵树。下图中为一般树：
树结构
如上图所示，一棵树有它的高度、深度和层数。
-
层：根节点为第一层，最远叶子节点所在位置为最大层数。如果某一个节点位于第L层，则其子节点位于第L+1层。 -
深度：根节点为1，层数越大，深度越深，相等于层数。 -
高度：高度和深度是相反的表示，深度是从上到下数的，而高度是从下往上数。除根节点以外的同一层子节点的高度可能不一样，这取决于子节点下的最远叶子节点的深度。 -
节点的度：节点的度等于节点拥有子树的个数。如图中的根节点的度为3，B节点的度为2，D节点的度为3。 -
树的度：树的度是树内各节点度的最大值，上图中树的度应该是3。 -
叶子：度为0的节点称为叶子节点或终端节点，例如K,J,F... -
非终端节点：终端节点和根节点之外树内部节点都是非终端节点。 -
有序树和⽆序树:如果将树的结点的各⼦树看成从左到右是有次序的(即不能互换)则称为该树为有序树, 否则是⽆序树。就像赌神家五房太太一样，从大到小是有顺序的。
二叉树（Binary Tree）
二叉树：每个节点最多只能有两棵子树，且有左右之分。逻辑上二叉树有五种基本形态：
- 空二叉树。
- 只有一个根节点的二叉树。
- 只有左子树的二叉树。
- 只有右子树的二叉树。
-
完全二叉树。
二叉树形态
满二叉树
如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0（叶子节点）的节点在同一层上，则这棵二叉树为满二叉树。
满二叉树
完全二叉树
深度为
k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。
完全二叉树
特性：最远的叶子节点只可能存在在最大两层中，像满二叉树那样所有叶子节点都在最大的一层中。
二叉树特性：
- 在二叉树的第 i 层上最多有 2^(i - 1) 个节点。
- 深度为 k 的二叉树最多有（2^k） - 1 个节点（k >= 1）。
- 对于任何一棵二叉树T，如果其叶子节点个数为m，度为2的节点个数为n，则m = n + 1。
- 具有n个节点的完全二叉树深度为 （log2(n)）+ 1;
- 对具有n个节点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有节点从1开始编号，则对于任意的序号为i的节点有:
A.如果i>1，那么序号为i的节点的双亲节点序号为i/2；
B.如果i=1，那么序号为i的节点为根节点，无双亲节点；
C.如果2i<=n，那么序号为i的节点的左孩子节点序号为2i；
D.如果2i>n，那么序号为i的节点无左孩子；
E.如果2i+1<=n，那么序号为i的节点右孩子序号为2i+1；
F.如果2i+1>n，那么序号为i的节点无右孩子。
二叉树的遍历
可根据根节点的访问顺序以及不通同的规则分为以下四种方式：
1、前序遍历
规则：若二叉树为空，则空操作返回；否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。先左后右。
2、中序遍历
规则：若二叉树为空，则空操作返回；否则从根节点（注意不是先访问根节点），中序遍历根节点的左子树，然后再访问根节点，最后中序遍历右子树。
3、后序遍历
规则：若二叉树为空，则空操作返回；否则从左到右先叶子节点的方式遍历左右子树，最后访问根节点。
4、层序遍历
规则：若二叉树为空，则空操作返回；否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，从左到右的顺序对节点逐个访问。
链表实现二叉树
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* 存储空间初始分配量 */
#define MAXSIZE 100
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
#pragma mark--二叉树构造
int indexs = 1;
typedef char String[24]; /* 0号单元存放串的长度 */
String str;
//字符串构建字符数组，T[0]为字符串长度
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
#pragma mark--二叉树基本操作
typedef char CElemType;
CElemType Nil=' '; /* 字符型以空格符为空 */
typedef struct BiTNode /* 结点结构 */
{
CElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
/*7.1 打印数据*/
Status visit(CElemType e)
{
printf("%c ",e);
return OK;
}
/* 7.2 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
/* 7.3 销毁二叉树
初始条件: 二叉树T存在。
操作结果: 销毁二叉树T
*/
void DestroyBiTree(BiTree *T)
{
if(*T)
{
/* 有左孩子 */
if((*T)->lchild)
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
/* 有右孩子 */
if((*T)->rchild)
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T=NULL; /* 空指针赋0 */
}
}
#define ClearBiTree DestroyBiTree
/*7.4 创建二叉树
按前序输入二叉树中的结点值(字符),#表示空树;
*/
void CreateBiTree(BiTree *T){
CElemType ch;
//获取字符
ch = str[indexs++];
//判断当前字符是否为'#'
if (ch == '#') {
*T = NULL;
}else
{
//创建新的结点
*T = (BiTree)malloc(sizeof(BiTNode));
//是否创建成功
if (!*T) {
exit(OVERFLOW);
}
/* 生成根结点 */
(*T)->data = ch;
/* 构造左子树 */
CreateBiTree(&(*T)->lchild);
/* 构造右子树 */
CreateBiTree(&(*T)->rchild);
}
}
/*
7.5 二叉树T是否为空;
初始条件: 二叉树T存在
操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
*/
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
/*
7.6 二叉树T的深度
初始条件: 二叉树T存在
操作结果: 返回T的深度
*/
int BiTreeDepth(BiTree T){
int i,j;
if(!T)
return 0;
//计算左孩子的深度
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
//计算右孩子的深度
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
//比较i和j
return i>j?i+1:j+1;
}
/*
7.7 二叉树T的根
初始条件: 二叉树T存在
操作结果: 返回T的根
*/
CElemType Root(BiTree T){
if (BiTreeEmpty(T))
return Nil;
return T->data;
}
/*
7.8 返回p所指向的结点值;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 返回p所指结点的值
*/
CElemType Value(BiTree p){
return p->data;
}
/*
7.8 给p所指结点赋值为value;
初始条件: 二叉树T存在，p指向T中某个结点
操作结果: 给p所指结点赋值为value
*/
void Assign(BiTree p,CElemType value)
{
p->data=value;
}
#pragma mark--二叉树遍历
/*
7.8 前序递归遍历T
初始条件:二叉树T存在;
操作结果: 前序递归遍历T
*/
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
/*
7.9 中序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
/*
7.10 后序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
//测试代码
BiTree T;
CElemType e1;
InitBiTree(&T);
StrAssign(str,"ABDH#K###E##CFI###G#J##");
CreateBiTree(&T);
printf("二叉树是否为空%d(1:是 0:否),树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
printf("二叉树的根为: %c\n",e1);
printf("\n前序遍历二叉树:");
PreOrderTraverse(T);
printf("\n中序遍历二叉树:");
InOrderTraverse(T);
printf("\n后序遍历二叉树:");
PostOrderTraverse(T);
printf("\n");
