二叉樹(Binary Tree)相關算法的實現
寫在前面：
二叉樹是比較簡單的一種數據結構，理解並熟練掌握其相關算法對於復雜數據結構的學習大有裨益
一.二叉樹的創建
[不喜歡理論的點我跳過>>]
所謂的創建二叉樹，其實就是讓計算機去存儲這個特殊的數據結構（特殊在哪裡？特殊在它是我們自定義的）
首先，計算機內部存儲都是線性的，而我們的樹形結構是一種層級的，計算機顯然無法理解，計算機能夠接受的原始數據類型並不能滿足我們的需求
所以，只好自定義一種數據結構來表示層級關系
實際上是要定義結構 + 操作，結構是為操作服務的，舉個例子，我們要模擬買票的過程，現有的數據結構無法滿足我們的需求（不要提數組...），我們需要的操作可能是:
1.獲取站在買票隊伍最前面的人
2.把買好票的人踢出隊伍
3.第一個人買完票後，他後面的所有人都要“自覺”地向前移動
明確了這三個操作，再根據操作來定義結構，最後我們得到了隊列（數組/鏈表 + 對應的函數）
二叉樹也是這樣，計算機看到的只是結構 + 操作，結構是Node集合（二叉鏈表），操作是創建、遍歷、查找等等函數
結點：
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
結點就是一個桶，兩只手（桶裡裝數據，兩只手伸出去抓左右兩個孩子）
操作：
//createBT();
//printBT();
//deleteNode(Node node);
//...
-------上面是對二叉樹的理解，下面是創建二叉樹具體實現-------
二叉樹的創建過程其實就是遍歷過程（此處指遞歸方式），我們知道二叉樹的任何一種遍歷方式都可以把樹形結構線性化（簡單的說就是一組遍歷結果可以唯一的表示一顆二叉樹），因此可以根據遍歷結果來還原一顆二叉樹
先序遍歷遞歸建樹的具體思路：
1.讀入當前根結點的數據
2.如果是空格，則將當前根置為空，否則申請一個新結點，存入數據
3.用當前根結點的左指針和右指針進行遞歸調用，創建左右子樹
語言描述可能不太好懂，代碼如下：
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;//若為空格則置空
else
{
*root=(struct bt *)malloc(sizeof(struct bt));//申請新結點
(*root)->data=c;//存入數據
createBT(&((*root)->left));//建立當前結點的左子樹
createBT(&((*root)->right));//建立當前結點的右子樹
}
}
例如，如果我們要建立一個二叉樹a(b, c)，只要輸入它的先序遍歷結果ab××c××即可（×表示空格），其余兩種建樹方式於此類似，不再詳述，至於非遞歸的建樹方法參見下面的非遞歸遍歷，非常相似
二.遍歷
遍歷在實現方式上有遞歸與非遞歸兩種方式，所謂的非遞歸其實是由遞歸轉化而來的（手動維護一個棧），開銷（內存/時間）上可能非遞歸的更好一些，畢竟操作系統的棧中維護的信息更多，現場的保存與恢復開銷都要更大一些
在遍歷順序上有3種方式：
1.先序遍歷（根-左-右）
2.中序遍歷（左-根-右）
3.後序遍歷（左-右-根）
舉個例子，二叉樹a(b, c(d, e))的三種遍歷結果分別是：
1.abcde
2.badce
3.bdeca
-------下面看看後序遍歷的遞歸與非遞歸實現，其余的與之類似-------
後序遍歷遞歸：
void postOrder(struct bt * root)
{
if(root == NULL)return;
else
{
postOrder(root->left);
postOrder(root->right);
putchar(root->data);
}
}
後序遍歷非遞歸：
void postOrder(struct st* root)
{
struct st* stack[100];//聲明結點棧
int top=-1;//棧頂索引
struct bt* p=root;//當前結點（present）
struct bt* q=NULL;//上一次處理的結點
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;//遍歷左子樹
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)//無右孩子，或右孩子已經遍歷過
{
putchar(p->data);//輸出根結點
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;//遍歷右子樹
}
}
}
為了描述地更清晰，上面直接實現了棧的操作，當然，更規范的做法是將棧作為一個獨立的數據結構封裝起來，在我們的函數中調用棧提供的操作函數來進行相關操作
三.輸出葉結點
檢索特定結點的一系列操作都是建立在遍歷的基礎上的，輸出葉結點就是一個例子，葉結點滿足的條件是左右孩子都為空，我們只要在遍歷中添加這樣的判斷條件就可以了
//此處采用先序遍歷
void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}
於此類似的操作有，輸出二叉樹中滿足一定條件的結點，刪除指定結點，在指定位置添加結點（子樹）...都是在遍歷的基礎上做一些額外的操作
四.計算樹的深度
計算樹深有多種方式，例如：
1.分別計算根下左右子樹的高度，二者中的較大的為樹深
2.最大遞歸深度為樹深
...
我們采用第一種方式，更清晰一些
int btDepth(struct bt* root)
{
int rd,ld;
if(root==NULL)return 0;//空樹深度為0
else
{
ld=1+btDepth(root->left);//遞歸進層，深度加1
rd=1+btDepth(root->right);//遞歸進層，深度加1
return ld > rd ? ld : rd;//返回最大值
}
}
五.樹形輸出
所謂樹形輸出，即對自然表示的二叉樹逆時針旋轉90度，其實仍然是在遍歷的過程中記錄遞歸層數，以此確定輸出結果
//depth表示遞歸深度，初始值為0
void btOutput(struct bt* root,int depth)
{
int k;
if(root==NULL)return;
else
{
btOutput(root->right,depth+1);//遍歷右子樹
for(k=0;k<depth;k++)
printf(" ");//遞歸層數為幾，就輸出幾個空格（縮進幾位）
putchar(root->data);printf("\n");
btOutput(root->left,depth+1);//遍歷左子樹
}
}
//“右-中-左”的遍歷順序被稱為“逆中序”遍歷，采用這種順序是為了符合輸出規則（逆時針90度）
六.按層縮進輸出
按層縮進輸出就像代碼編輯器中的自動縮進，從根結點開始逐層縮進，只需要對上面的代碼稍作改動就可以實現
//k仍然表示遞歸深度，初始值為0
void indOutput(struct bt* root,int k)
{
int i;
if(root!=NULL)
{
for(i=1;i<=k;i++)
putchar(' ');
putchar(root->data);putchar('\n');
indOutput(root->left,k+1);
indOutput(root->right,k+1);
}
else return;
}
//按層縮進輸出與樹形輸出的唯一區別就是遍歷方式不同，前者是先序遍歷，後者是逆中序遍歷
七.按層順序輸出
按層順序輸出與前面提及的兩種輸出方式看似相似，實則有著很大不同，至少，我們無法簡單地套用任何一種遍歷過程來完成這個目標
所以，只能維護一個隊列來控制遍歷順序
void layerPrint(struct bt* root)
{
struct bt* queue[100];//聲明結點隊列
struct bt* p;//當前結點
int amount=0,head,tail,j,k;//隊列相關屬性（元素總數，對頭、隊尾索引）
queue[0]=root;
head=0;
tail=1;
amount++;
while(1)
{
j=0;
for(k=0;k<amount;k++)
{
p=queue[head++];//取對頭元素
if(p->left!=NULL)
{
queue[tail++]=p->left;//如果有則記錄左孩子
j++;
}
if(p->right!=NULL)
{
queue[tail++]=p->right;//如果有則記錄右孩子
j++;
}
putchar(p->data);//輸出當前結點值
}
amount=j;//更新計數器
if(amount==0)break;
}
}
八.計算從根到指定結點的路徑
要記錄路徑，當然不宜用遞歸的方式，這裡采用後序遍歷的非遞歸實現
為什麼選擇後序遍歷？
因為在這種遍歷方式中，某一時刻棧中現有的結點恰恰就是從根結點到當前結點的路徑（從棧底到棧頂）。嚴格地說，此時應該用隊列來保存路徑，因為棧不支持從棧底到棧頂的出棧操作（這樣的小細節就把它忽略好了...）
//參數c為指定結點值
void printPath(struct bt* root,char c)
{
struct st* stack[100];//聲明結點棧
int top=-1;//棧頂索引
int i;
struct bt* p=root;//當前結點
struct bt* q=NULL;//上一次處理的結點
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;//遍歷左子樹
if(top!=-1)
{
p=stack[top];//獲取棧頂元素
if(p->right==NULL||p->right==q)//如果當前結點沒有右孩子或者右孩子剛被訪問過
{
if(p->data==c)//如果找到則輸出路徑
{
for(i=0;i<=top;i++)
{
p=stack[i];
putchar(p->data);
}
printf("\n");
//此處不跳出循環，因為可能存在不唯一的結點值，遍歷整個樹，找出所有路徑
}
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;//遍歷右子樹
}
}
}
九.完整源碼與截圖示例
源碼：#include<stdio.h>
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;
else
{
*root=(struct bt *)malloc(sizeof(struct bt));
(*root)->data=c;
createBT(&((*root)->left));
createBT(&((*root)->right));
}
}
void preOrder(struct bt * root)
{
if(root == NULL)return;
else
{
putchar(root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(struct bt * root)
{
if(root == NULL)return;
else
{
inOrder(root->left);
putchar(root->data);
inOrder(root->right);
}
}
void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}
int btDepth(struct bt* root)
{
int rd,ld;
if(root==NULL)return 0;
else
{
ld=1+btDepth(root->left);
rd=1+btDepth(root->right);
return ld > rd ? ld : rd;
}
}
void btOutput(struct bt* root,int depth)
{
int k;
if(root==NULL)return;
else
{
btOutput(root->right,depth+1);
for(k=0;k<depth;k++)
printf(" ");
putchar(root->data);printf("\n");
btOutput(root->left,depth+1);
}
}
void postOrder(struct st* root)
{
struct st* stack[100];
int top=-1;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
putchar(p->data);
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}
void printPath(struct bt* root,char c)
{
struct st* stack[100];
int top=-1;
int i;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
if(p->data==c)
{
for(i=0;i<=top;i++)
{
p=stack[i];
putchar(p->data);
}
printf("\n");
}
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}
void layerPrint(struct bt* root)
{
struct bt* queue[100];
struct bt* p;
int amount=0,head,tail,j,k;
queue[0]=root;
head=0;
tail=1;
amount++;
while(1)
{
j=0;
for(k=0;k<amount;k++)
{
p=queue[head++];
if(p->left!=NULL)
{
queue[tail++]=p->left;
j++;
}
if(p->right!=NULL)
{
queue[tail++]=p->right;
j++;
}
putchar(p->data);
}
amount=j;
if(amount==0)break;
}
}
void indOutput(struct bt* root,int k)
{
int i;
if(root!=NULL)
{
for(i=1;i<=k;i++)
putchar(' ');
putchar(root->data);putchar('\n');
indOutput(root->left,k+1);
indOutput(root->right,k+1);
}
else return;
}
void main()
{
char c;
struct bt * root;
printf("請輸入先序遍歷結果: ");
createBT(&root);
printf("先序遍歷(preOrder)[遞歸]: \n");
preOrder(root);
printf("\n中序遍歷(inOrder)[遞歸]: \n");
inOrder(root);
printf("\n後序遍歷(postOrder)[非遞歸]: \n");
postOrder(root);
printf("\n葉結點(leaves): \n");
printLeaves(root);
printf("\n深度(depth): \n");
printf("%d\n",btDepth(root));
printf("樹形輸出(tree output): \n");
btOutput(root,0);
printf("縮進輸出(indentation output): \n");
indOutput(root,0);
printf("請輸入目標結點(target node): ");
getchar();
c=getchar();
printf("路徑(path): \n");
printPath(root,c);
printf("按層輸出(layerPrint): \n");
layerPrint(root);
printf("\n");
}
