跳到主要內容
黯羽輕揚每天積累一點點

二叉樹 (Binary Tree) 相關算法的實現

免費2015-03-17#Math#二叉树

本文主要討論二叉樹相關算法的 C 語言實現，包括樹的創建、三種方式遍歷（遞歸與非遞歸）、輸出葉��點、計算樹的深度、樹形輸出、按層縮進輸出、按層順序輸出、計算從根到指定結點的路徑

no_mkd

寫在前面：

二叉樹是比較簡單的一種數據結構，理解並熟練掌握其相關算法對於複雜數據結構的學習大有裨益

一。二叉樹的創建

[不喜歡理論的點我跳過>>]

所謂的創建二叉樹，其實就是讓計算機去存儲這個特殊的數據結構（特殊在哪裡？特殊在它是我們自定義的）

首先，計算機內部存儲都是線性的，而我們的樹形結構是一種層級的，計算機顯然無法理解，計算機能夠接受的原始數據類型並不能滿足我們的需求

所以，只好自定義一種數據結構來表示層級關係

實際上是要定義結構 + 操作，結構是為操作服務的，舉個例子，我們要模擬買票的過程，現有的數據結構無法滿足我們的需求（不要提數組...），我們需要的操作可能是:

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");
}

截圖示例：

一顆較為複雜的二叉樹：

其先序遍歷結果為：ABD××EG×××C×FH××I××（×表示空，輸入的時候要把×換成空格）

把 D 改成 H 再試一次（存在重複元素了，因該有兩條到 H 的路徑）

評論

暫無評論，快來發表你的看法吧

提交評論