二叉樹在樹結構的應用中起著非常重要的作用，二叉樹很多操作簡單，并且任何樹都可以與二叉樹進行相互轉換。一個具有n個節點的二叉樹，一共有2n個指針域，其中只有n-1個用來指向節點的左右孩子，其余的n+1個指針為空。
二叉樹具有很多重要特征：
1. 二叉樹的第I層之多有2^(i-1)個節點
2. 具有n個節點的完全二叉樹的深度為[log2(n)] + 1
3. 如果i=1，則節點i就是根節點，無雙親；否則其雙親是節點[i/2]。（i是節點的標號）
二叉樹有幾種存儲結構：
1. 順序存儲結構
2. 鏈式存儲結構(在有n個節點的二叉鏈表中有n+1個空鏈域)
二叉樹的遍歷：
限定先左后右的順序的話，有三種遍歷方法。先序遍歷，中序遍歷，后序遍歷。（DLR，LDR，LRD）
除了這三種方式外，還可從上到下，從左到右按層次進行。
線索二叉樹：
非線性化結構線性化操作，在每個節點增加兩個指針域fwd和bkwd，分別指示節點在依任一次遍歷是得到的前驅和后繼的信息。以這種節點結構構成的叫做線索鏈表。
在一棵非線索二叉樹以某種次序遍歷是其變為一棵線索二叉樹的過程稱為二叉樹的線索化。對于尋找前驅和后繼節點這兩種運算而言，線索樹優于非線索樹。但也有缺點，在進行插入和刪除操時，線索樹比非線索樹的時間開銷大，原因在于線索樹進行插入和刪除操作時，除了修改相應的指針外，還要修改相應的線索。
--------------------華麗滴分割線-----------------------------------
關于二叉樹結構的定義說明：
~~~
typedef char datatype;
typedef struct bitnode
{
datatype data;
int lflag, rflag;
struct bitnode *lchild, *rchild;
}BitNode, *BitTree;
~~~
二叉樹的創建
~~~
BitTree CreatBitTree(void)
{
char ch;
BitTree root;
scanf("%c", &ch);
if(ch == '#')
root = NULL;
else
{
if(!(root = (BitTree)malloc(sizeof(BitNode))))
return 0;
root->data = ch;
root->lflag = 0;
root->rflag = 0;
root->lchild = CreatBitTree();
root->rchild = CreatBitTree();
}
return root;
}
~~~
二叉樹的復制，返回一個指向二叉樹的指針
~~~
BitTree CopyBitTree(BitTree T)
{
BitTree root;
if(!T)
root = NULL;
else
{
if(!(root=(BitTree)malloc(sizeof(BitNode))))
return 0;
root->data = T->data;
root->lflag = T->lflag;
root->rflag = T->rflag;
root->lchild = CopyBitTree(T->lchild);
root->rchild = CopyBitTree(T->rchild);
}
return root;
}
~~~
二叉樹的遍歷，三種方式遍歷，先序、中序和后序遍歷方式
~~~
//先序遍歷
void PreOrderTraverse(BitTree root)
{
if(root)
{
printf("%c->", root->data);
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
}
//中序遍歷
void InOrderTraverse(BitTree root)
{
if(root)
{
InOrderTraverse(root->lchild);
printf("%c->", root->data);
InOrderTraverse(root->rchild);
}
}
//后序遍歷
void PostOrderTraverse(BitTree root)
{
if(root)
{
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%c->", root->data);
}
}
~~~
二叉樹的釋放
~~~
void FreeBitTree(BitTree root)
{
if(root)
{
FreeBitTree(root->lchild);
FreeBitTree(root->rchild);
free(root);
}
}
~~~
//---------------------------線索化二叉樹-----------------------------
~~~
BitTree pre; //記錄上一個節點的指針
//先序線索化二叉樹
void PreThreading(BitTree p);
int PreOrderThreading(BitTree *root, BitTree T) //先序線索化二叉樹
{
if(!((*root) = (BitTree)malloc(sizeof(BitNode))))
exit(1);
(*root)->lflag = 0;
(*root)->rflag = 1;
(*root)->rchild = (*root);
if(!T)
{
(*root)->lchild = *(root);
return 0;
}
else
{
(*root)->lchild = T;
pre = *(root);
PreThreading(T);
pre->rchild = *(root);
pre->rflag = 1;
(*root)->rchild = pre;
return 1;
}
}
void PreThreading(BitTree p) //先序建立節點的搜索化
{
if(p)
{
if(!p->lchild)
{
p->lchild = pre;
p->lflag = 1;
}
if(!pre->rchild)
{
pre->rchild = p;
pre->rflag = 1;
}
pre = p;
if(p->lflag == 0)
PreThreading(p->lchild);
if(p->rflag == 0)
PreThreading(p->rchild);
}
}
//中序線索化二叉樹
void InThreading(BitTree p);
int InOrderThreading(BitTree *root, BitTree T) //中序線索化二叉樹
{
if(!((*root) = (BitTree)malloc(sizeof(BitNode))))
exit(1);
(*root)->lflag = 0;
(*root)->rflag = 1;
(*root)->rchild = (*root);
if(!T)
{
(*root)->lchild = *(root);
return 0;
}
else
{
(*root)->lchild = T;
pre = *(root);
InThreading(T);
pre->rchild = *(root);
pre->rflag = 1;
(*root)->rchild = pre;
return 1;
}
}
void InThreading(BitTree p)
{
if(p)
{
InThreading(p->lchild); //左子樹線索化
if(!p->lchild)
{
p->lchild = pre;
p->lflag = 1;
}
if(!pre->rchild)
{
pre->rchild = p;
pre->rflag = 1;
}
pre = p;
InThreading(p->rchild);
}
}
~~~
//---------------------------遍歷線索化二叉樹-----------------------------
~~~
//先序遍歷線索化二叉樹
void PreOrderTraverse_Threaing(BitTree root) //該root為頭結點
{
BitTree p = root, par;
p = root->lchild;
while(p != root)
{
printf("%c->", p->data);
while(p->lflag == 0)
{
p = p->lchild;
printf("%c->", p->data);
}
while((p->rflag==1) && (p->rchild != root))
{
p = p->rchild;
printf("%c->", p->data);
}
if(p->lflag == 0)
p = p->lchild;
else
p = p->rchild;
}
}
//中序遍歷線索化二叉樹
void InOrderTraverse_Threaing(BitTree root) //該root為頭結點
{
BitTree p = root;
p = root->lchild;
while(p != root)
{
while(p->lflag == 0)
{
p = p->lchild;
}
printf("%c->", p->data);
while((p->rflag==1) && (p->rchild != root))
{
p = p->rchild;
printf("%c->", p->data);
}
p = p->rchild;
}
}
~~~
//---------------------------釋放線索化二叉樹-----------------------------
~~~
//釋放先序線索化二叉樹
void FreePreOrderThreading(BitTree root)
{
BitTree p = root, t;
static int num = 0;
printf("釋放先序線索化鏈表······\n");
t = p;
p = root->lchild;
while(p != root)
{
if(t != root)
{
free(t);
num++;
}
while(p->lflag == 0)
{
t = p;
p = p->lchild;
free(t);
num++;
}
while((p->rflag==1) && (p->rchild != root))
{
t = p;
p = p->rchild;
free(t);
num++;
}
if(p->lflag == 0)
{
t = p;
p = p->lchild;
}
else
{
t = p;
p = p->rchild;
}
}
free(t);
num++;
free(root);
num++;
printf("釋放先序線索化鏈表%d個節點成功\n", num);
}
//釋放中序線索化二叉樹
void FreeInOrderThreading(BitTree root)
{
BitTree p = root, t;
static int num = 0;
printf("\n釋放中序線索化鏈表······\n");
t = p;
p = root->lchild;
while(p != root)
{
while(p->lflag == 0)
{
t = p;
p = p->lchild;
}
while((p->rflag==1) && (p->rchild != root))
{
t = p;
free(t);
num++;
p = p->rchild;
}
t = p;
p = p->rchild;
free(t);
num++;
}
free(root);
num++;
printf("釋放中序線索化鏈表%d個節點成功\n\n", num);
}
~~~
//**********************求解關于二叉樹的一些問題***************************//
1. 遞歸求解二叉樹中葉子節點的數目
~~~
int LeafCount(BitTree root)
{
if(!root)
return 0;
else if(!root->lchild && !root->rchild)
return 1;
else
return (LeafCount(root->lchild) + LeafCount(root->rchild));
}
~~~
2. 遞歸將二叉樹所有節點的左右子樹節點相互交換
~~~
void BitTreeRevolute(BitTree root)
{
BitTree p;
p = root->lchild;
root->lchild = root->rchild;
root->rchild = p;
if(root->lchild)
BitTreeRevolute(root->lchild);
if(root->rchild)
BitTreeRevolute(root->rchild);
}
~~~
