二叉樹的遍歷算法

先序遍歷算法

先序遍歷的實(shí)現(xiàn)方式在前面已經(jīng)說過了，比如下面的一棵二叉樹：

我們需要先訪問根結(jié)點(diǎn)A，然后以先序遍歷的方式遍歷左子樹，左子樹同樣是一棵二叉樹，以同樣的方式訪問根結(jié)點(diǎn)B，然后先序遍歷B的左子樹，會(huì)發(fā)現(xiàn)，這是一個(gè)遞歸的過程，所以我們可以通過遞歸實(shí)現(xiàn)。 先序遍歷算法實(shí)現(xiàn)如下：

void PreOrderTraverse(BiTree t){
	//判斷當(dāng)前結(jié)點(diǎn)是否為空
	if(t == NULL){
		return;
	}
	//輸出根結(jié)點(diǎn)
	printf("%c\t",t->data);
	//先序遍歷左子樹
	PreOrderTraverse(t->lchild);
	//先序遍歷右子樹
	PreOrderTraverse(t->rchild);
}

代碼實(shí)現(xiàn)非常簡(jiǎn)單，但是需要一定的時(shí)間理解： 我們首先傳入二叉樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)不為空，所以輸出A，此時(shí)調(diào)用自身，將左孩子傳入，此時(shí)將先序遍歷左子樹。 傳入結(jié)點(diǎn)B依然不為空，此時(shí)輸出B，然后又調(diào)用自身，將結(jié)點(diǎn)B的左孩子傳入，此時(shí)將先序遍歷結(jié)點(diǎn)B的左子樹。 傳入結(jié)點(diǎn)D依然不為空，此時(shí)輸出D，然后又調(diào)用自身，將結(jié)點(diǎn)D的左孩子傳入，此時(shí)左孩子為空，所以函數(shù)返回，返回后就執(zhí)行先序遍歷右子樹，傳入的右孩子仍然為空，此時(shí)繼續(xù)返回，先序遍歷結(jié)點(diǎn)B的右孩子。 以此類推，注意理解。

我們來測(cè)試一下，因?yàn)閯倓偨佑|遍歷算法，所以這里，我們通過一個(gè)比較笨的方式實(shí)現(xiàn)二叉樹，然后調(diào)用先序遍歷函數(shù)：

int main(){
	//創(chuàng)建根結(jié)點(diǎn)
	BiTree root = (BiTree) malloc(sizeof(BiNode));
	root->data = 'A';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子
	root->lchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->data = 'B';
	//創(chuàng)建根結(jié)點(diǎn)的右孩子
	root->rchild  = (BiTree) malloc(sizeof(BiNode));
	root->rchild->data = 'C';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子的左孩子
	root->lchild->lchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->lchild->data = 'D';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子的右孩子
	root->lchild->rchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->rchild->data = 'E';
	//根結(jié)點(diǎn)的右孩子無左右孩子
	root->rchild->lchild = NULL;
	root->rchild->rchild = NULL;
	//根結(jié)點(diǎn)的左孩子的左孩子無左右孩子
	root->lchild->lchild->lchild = NULL;
	root->lchild->lchild->rchild = NULL;
	//根結(jié)點(diǎn)的左孩子右孩子無左右孩子
	root->lchild->rchild->lchild = NULL;
	root->lchild->rchild->rchild = NULL;
	//先序遍歷
	PreOrderTraverse(root);
	return 0;
}

運(yùn)行結(jié)果：

A B D E C

中序遍歷算法

中序遍歷和后序遍歷的算法就不用分析了，過程是一樣的，只不過是操作根結(jié)點(diǎn)的順序變了。 中序遍歷算法實(shí)現(xiàn)如下：

void InOrderTraverse(BiTree t){
	//判斷當(dāng)前結(jié)點(diǎn)是否為空
	if(t == NULL){
		return;
	}
	//先序遍歷左子樹
	InOrderTraverse(t->lchild);
	//輸出根結(jié)點(diǎn)
	printf("%c\t",t->data);
	//先序遍歷右子樹
	InOrderTraverse(t->rchild);
}

后序遍歷算法

后序遍歷算法實(shí)現(xiàn)如下：

void PostOrderTraverse(BiTree t){
	//判斷當(dāng)前結(jié)點(diǎn)是否為空
	if(t == NULL){
		return;
	}
	//先序遍歷左子樹
	PostOrderTraverse(t->lchild);
	//先序遍歷右子樹
	PostOrderTraverse(t->rchild);
	//輸出根結(jié)點(diǎn)
	printf("%c\t",t->data);
}

非遞歸遍歷算法

遍歷思想

前面介紹了三種遍歷算法，都是通過遞歸實(shí)現(xiàn)的，雖然遞歸實(shí)現(xiàn)的代碼量非常少，但是遞歸較難理解，而且空間消耗大，所以這里我也介紹一下遍歷算法的非遞歸實(shí)現(xiàn)，具體想用哪種辦法就看自己了。

這里以中序遍歷算法的非遞歸實(shí)現(xiàn)作為例子重點(diǎn)講述。 當(dāng)然思想還是一樣的，我們需要優(yōu)先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后訪問右子樹，既然是這樣，根結(jié)點(diǎn)我們就需要先保存下來，這里可以用棧實(shí)現(xiàn)。 比如下面的這棵二叉樹：

如何實(shí)現(xiàn)非遞歸的中序遍歷呢？

中序遍歷算法是先遍歷左子樹，然后訪問根結(jié)點(diǎn)的，所以一開始傳入根結(jié)點(diǎn)A，我們不能訪問，此時(shí)將根結(jié)點(diǎn)A入棧，然后遍歷根結(jié)點(diǎn)A的左子樹。

此時(shí)以同樣的方式遍歷左子樹，遇到左子樹的根結(jié)點(diǎn)B，同樣不能訪問，將根結(jié)點(diǎn)B入棧，然后遍歷根結(jié)點(diǎn)B的左子樹。

我們接著遍歷結(jié)點(diǎn)B的左子樹，同樣將根結(jié)點(diǎn)D入棧。

此時(shí)結(jié)點(diǎn)D無左孩子，這樣就可以訪問根結(jié)點(diǎn)了，對(duì)棧進(jìn)行出棧操作，因?yàn)闂５奶匦?，此時(shí)出棧結(jié)點(diǎn)為D。

然后遍歷根結(jié)點(diǎn)D的右子樹，因?yàn)榻Y(jié)點(diǎn)D無右孩子，此時(shí)需要退回到結(jié)點(diǎn)B，這時(shí)候結(jié)點(diǎn)B的左子樹已經(jīng)遍歷完了，可以訪問根結(jié)點(diǎn)了，對(duì)棧進(jìn)行出棧操作，出棧結(jié)點(diǎn)為B。

此時(shí)根結(jié)點(diǎn)A的左子樹也遍歷完了，又進(jìn)行出棧操作，出棧結(jié)點(diǎn)為A。

以同樣的方式遍歷右子樹，遇到結(jié)點(diǎn)C，先入棧，然后訪問其左子樹，結(jié)點(diǎn)C無左孩子，所以結(jié)點(diǎn)C出棧，接著遍歷右子樹，以此類推。

遍歷結(jié)果為：D B A C E

算法實(shí)現(xiàn)

實(shí)現(xiàn)思想講解清楚了，接下來是算法實(shí)現(xiàn)，在實(shí)現(xiàn)這個(gè)算法之前我們還需要實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu)，這里采用順序棧。

#define TElemType char
int top=-1;//top變量時(shí)刻表示棧頂元素所在位置
//構(gòu)造結(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct BiTNode{
    TElemType data;//數(shù)據(jù)域
    struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
//前序和中序遍歷使用的進(jìn)棧函數(shù)
void push(BiTNode** a,BiTNode* elem){
    a[++top]=elem;
}
//彈棧函數(shù)
void pop( ){
    if (top==-1) {
        return ;
    }
    top--;
}
//模擬操作結(jié)點(diǎn)元素的函數(shù)，輸出結(jié)點(diǎn)本身的數(shù)值
void displayElem(BiTNode* elem){
    printf("%c ",elem->data);
}
//拿到棧頂元素
BiTNode* getTop(BiTNode**a){
    return a[top];
}
//中序遍歷非遞歸實(shí)現(xiàn)
void InOrderTraverse(BiTree Tree){
    BiTNode* a[20];//定義一個(gè)順序棧
    BiTNode * p;//臨時(shí)指針
    p=Tree;
    //當(dāng)p為NULL并且棧為空時(shí)，表明樹遍歷完成
    while (p != NULL || top!=-1) {
        //如果p不為NULL，將其壓棧并遍歷其左子樹
        if (p != NULL) {
            push(a, p);
            p=p->lchild;
        }
        //如果p==NULL，表明左子樹遍歷完成，需要遍歷上一層結(jié)點(diǎn)的右子樹
        else{
            p=getTop(a);
            pop();
            displayElem(p);
            p=p->rchild;
        }
    }
}

層次遍歷算法

層次遍歷算法是通過二叉樹的層次決定的，如下面的一棵二叉樹：

它的層次遍歷結(jié)果為：A B C D E，即從上到下，從左到右進(jìn)行遍歷。 對(duì)于層次遍歷，我們可以使用隊(duì)列實(shí)現(xiàn)。 首先傳入根結(jié)點(diǎn)A，此時(shí)將根結(jié)點(diǎn)A入隊(duì)，然后就可以執(zhí)行出隊(duì)操作，出隊(duì)結(jié)點(diǎn)為A；

出隊(duì)之后判斷根結(jié)點(diǎn)A是否有左右孩子，如果有，則將結(jié)點(diǎn)B、C分別入隊(duì)，然后執(zhí)行出隊(duì)操作，由于隊(duì)列的特性，出隊(duì)結(jié)點(diǎn)為B；

結(jié)點(diǎn)B出隊(duì)之后判斷結(jié)點(diǎn)B是否有左右孩子，有左孩子，則入隊(duì)，然后執(zhí)行出隊(duì)操作，出隊(duì)結(jié)點(diǎn)為C；

繼續(xù)判斷結(jié)點(diǎn)C是否有左右孩子，結(jié)點(diǎn)C有右孩子E，將結(jié)點(diǎn)E入隊(duì)，然后執(zhí)行出隊(duì)操作，出隊(duì)結(jié)點(diǎn)為D；

判斷結(jié)點(diǎn)D是否有左右孩子，結(jié)點(diǎn)D無左右孩子，直接執(zhí)行出隊(duì)操作，出隊(duì)結(jié)點(diǎn)為E； 結(jié)點(diǎn)E也無左右孩子，而隊(duì)列也已經(jīng)空了，此時(shí)遍歷完成。

該算法和剛才介紹的非遞歸遍歷算法有異曲同工之妙，這里就不具體寫出該算法了，大家可以嘗試著自己實(shí)現(xiàn)一下。

先序遍歷建立二叉樹算法

在學(xué)習(xí)遍歷算法的時(shí)候，還記得我們是如何建立二叉樹的嗎？

int main(){
	//創(chuàng)建根結(jié)點(diǎn)
	BiTree root = (BiTree) malloc(sizeof(BiNode));
	root->data = 'A';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子
	root->lchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->data = 'B';
	//創(chuàng)建根結(jié)點(diǎn)的右孩子
	root->rchild  = (BiTree) malloc(sizeof(BiNode));
	root->rchild->data = 'C';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子的左孩子
	root->lchild->lchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->lchild->data = 'D';
	//創(chuàng)建根結(jié)點(diǎn)的左孩子的右孩子
	root->lchild->rchild  = (BiTree) malloc(sizeof(BiNode));
	root->lchild->rchild->data = 'E';
	//根結(jié)點(diǎn)的右孩子無左右孩子
	root->rchild->lchild = NULL;
	root->rchild->rchild = NULL;
	//根結(jié)點(diǎn)的左孩子的左孩子無左右孩子
	root->lchild->lchild->lchild = NULL;
	root->lchild->lchild->rchild = NULL;
	//根結(jié)點(diǎn)的左孩子右孩子無左右孩子
	root->lchild->rchild->lchild = NULL;
	root->lchild->rchild->rchild = NULL;
	return 0;
}

可以看到，這個(gè)方法非常麻煩，但是建立算法又建立在遍歷算法之上，所以我們應(yīng)該先掌握遍歷算法，再來學(xué)習(xí)建立算法。

先序遍歷建立算法即通過一個(gè)先序的遍歷序列建立出一棵二叉樹，比如下面的一個(gè)先序序列： A B C D E G F 需要注意的是，單憑這個(gè)先序序列并不能唯一確定一棵二叉樹。

比如這兩棵二叉樹的先序遍歷結(jié)果均為：A B C D E G F。 所以我們需要對(duì)這棵二叉樹進(jìn)行補(bǔ)充，補(bǔ)充一些空結(jié)點(diǎn)，然后按照順序進(jìn)行建立：

先序遍歷建立二叉樹算法實(shí)現(xiàn)如下：

BiTree CreateBiTreePre(){
	BiTree root;
	char ch;
	printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)據(jù)：\n");
	scanf("%c",&ch);
	getchar(); //接收一個(gè)回車
	if(ch == '#'){
		root = NULL;
	}else{
		//創(chuàng)建結(jié)點(diǎn)
		root = (BiTree) malloc(sizeof(BiNode));
		root->data = ch;
		//遞歸建立左子樹
		root->lchild = CreateBiTreePre();
		//遞歸建立右子樹
		root->rchild = CreateBiTreePre();
	}
	return root;
}

測(cè)試一下：

int main(){
	BiTree root;
	//先序建立二叉樹
	root = CreateBiTreePre();
	printf("先序遍歷:");
	PreOrderTraverse(root);
	printf("\n");
	printf("中序遍歷:");
	InOrderTraverse(root);
	printf("\n");
	printf("后序遍歷:");
	PostOrderTraverse(root);
	return 0;
}

運(yùn)行程序，輸入：A B C # # D E # G # # F # # # 運(yùn)行結(jié)果：

先序遍歷:A      B       C       D       E       G       F
中序遍歷:C      B       E       G       D       F       A
后序遍歷:C      G       E       F       D       B       A

遍歷二叉樹算法的應(yīng)用

下面介紹一下遍歷二叉樹算法的應(yīng)用。

復(fù)制二叉樹

通過遍歷一棵二叉樹，我們能夠?qū)⒁豢枚鏄鋸?fù)制到另一棵二叉樹上。

BiTree CopyTree(BiTree t){
	BiTree newT;
 	if(t == NULL){ 
 		return NULL;
 	}else{
 		//創(chuàng)建新結(jié)點(diǎn)
  		newT = (BiTree) malloc(sizeof(BiNode));
  		if(newT == NULL){
  			exit(-1);
  		}
  		//復(fù)制結(jié)點(diǎn)的數(shù)據(jù)域
 		newT->data = t->data;
 		//遞歸復(fù)制左子樹
  		newT->lchild=CopyTree(t->lchild);
  		//遞歸復(fù)制右子樹
  		newT->rchild=CopyTree(t->rchild);
  		return newT;
 	}
}

中序和后序復(fù)制二叉樹的實(shí)現(xiàn)與其類似，不重復(fù)討論。

計(jì)算二叉樹的深度

遍歷二叉樹算法還可以用于計(jì)算二叉樹的深度，算法如下：

int Depth(BiTree t){
	int m,n;
	//判斷二叉樹是否為空
	if(t == NULL){
		return 0;		//深度為0
	}
	//計(jì)算左子樹深度
	m = Depth(t->lchild);
	//計(jì)算右子樹深度
	n = Depth(t->rchild);
	//判斷左右子樹哪棵樹深度最大，最后記得加1(加的是根結(jié)點(diǎn))
	if(m > n){
		return m + 1;
	}else{
		return n + 1;
	}
}

這些算法都比較簡(jiǎn)單，就不一一分析了，看代碼注釋應(yīng)該就能夠理解了。

計(jì)算二叉樹的結(jié)點(diǎn)總數(shù)

遍歷算法因?yàn)橐L問二叉樹中的每個(gè)結(jié)點(diǎn)，所以它還能夠用于計(jì)算結(jié)點(diǎn)總數(shù)，算法實(shí)現(xiàn)如下：

int GetNodeCount(BiTree t){
	if(t == NULL){	//若當(dāng)前結(jié)點(diǎn)為NULL，返回0
		return 0;
	}
	//返回左子樹結(jié)點(diǎn)數(shù) + 右子樹結(jié)點(diǎn)數(shù) + 根結(jié)點(diǎn)
	return GetNodeCount(t->lchild) + GetNodeCount(t->rchild) + 1;
}

計(jì)算二叉樹的葉子結(jié)點(diǎn)數(shù)

計(jì)算葉子結(jié)點(diǎn)數(shù)的方式和剛才的算法類似，下面是代碼實(shí)現(xiàn)：

int GetLeafCount(BiTree t){
	if(t == NULL){	//若當(dāng)前結(jié)點(diǎn)為NULL，返回0
		return 0;
	}
	if(t->lchild == NULL && t->rchild == NULL){
		//若當(dāng)前結(jié)點(diǎn)無左右孩子，則表明是葉子結(jié)點(diǎn)
		return 1;
	}
	//返回左子樹葉子結(jié)點(diǎn)數(shù) + 右子樹葉子結(jié)點(diǎn)數(shù)
	return GetLeafCount(t->lchild) + GetLeafCount(t->rchild);
}

線索二叉樹的由來

先來看下面這棵二叉樹：

這是二叉樹存儲(chǔ)結(jié)構(gòu)中的二叉鏈表，其優(yōu)點(diǎn)是能夠很方便地找到任意結(jié)點(diǎn)的左右孩子，然而，它也有缺點(diǎn)：一般情況下，無法直接找到某個(gè)結(jié)點(diǎn)在某種遍歷序列下的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。

為了能夠方便地找到任意結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)，我們可以在結(jié)點(diǎn)中保存其前驅(qū)和后繼的結(jié)點(diǎn)地址，但如果為其增設(shè)兩個(gè)指針域顯然會(huì)犧牲很多空間，為此，我們可以利用二叉鏈表中的空指針域。

假設(shè)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其一共有2n個(gè)指針域，而n個(gè)結(jié)點(diǎn)的二叉樹有n - 1個(gè)孩子結(jié)點(diǎn)，也就是說，該二叉樹一共使用了n - 1個(gè)指針域用來指向左右孩子，這樣就有n + 1個(gè)指針域是空著的，我們剛好可以利用這些指針域，用它們指向結(jié)點(diǎn)的前驅(qū)或者后繼結(jié)點(diǎn)。

如何利用二叉鏈表中的空指針域

對(duì)于一棵二叉樹的二叉鏈表結(jié)構(gòu)，若某個(gè)結(jié)點(diǎn)的左孩子為空，則將空的左孩子指針域指向其前驅(qū)結(jié)點(diǎn)；同理，若某個(gè)結(jié)點(diǎn)的右孩子為空，則將空的友好孩子指針域指向其后繼結(jié)點(diǎn)。我們將這種改變指向的指針稱為"線索"，加上了線索的二叉樹稱為線索二叉樹。

看這樣的一個(gè)例子，比如下面的一棵二叉樹：

我們說二叉樹的線索化是相對(duì)于某個(gè)遍歷序列而言的，上面這棵二叉樹的中序遍歷結(jié)果為：C B E G D F A 則對(duì)于中序遍歷序列來說，該如何實(shí)現(xiàn)線索化呢？

先看結(jié)點(diǎn)A，其右孩子指針域?yàn)榭?，此時(shí)我們應(yīng)該利用起來這個(gè)空指針域，讓其指向它的后繼結(jié)點(diǎn)，而從中序遍歷結(jié)果得知，結(jié)點(diǎn)A無后繼結(jié)點(diǎn)，所以我們最后還是讓結(jié)點(diǎn)A的右孩子指針域?yàn)榭眨蛔魈幚怼?/p>

再看結(jié)點(diǎn)C，其左右孩子指針域均為空，此時(shí)我們先處理左孩子指針域。從中序遍歷結(jié)果得知，結(jié)點(diǎn)C無前驅(qū)結(jié)點(diǎn)，但其后繼結(jié)點(diǎn)為B，所以我們不對(duì)左孩子指針域作處理，而讓右孩子指針域指向結(jié)點(diǎn)B。

繼續(xù)看結(jié)點(diǎn)E，其左孩子指針域?yàn)榭?，而其前?qū)結(jié)點(diǎn)為B，所以讓其左孩子指針域指向結(jié)點(diǎn)B。

處理結(jié)點(diǎn)F和結(jié)點(diǎn)G的方式也是一樣的，最后線索化完成的結(jié)果應(yīng)為：

看到線索化后的二叉樹，很多同學(xué)可能懵了，這么多的指針指向，到底哪些是指向前驅(qū)和后繼結(jié)點(diǎn)的，哪些是指向孩子結(jié)點(diǎn)的呢？

為了區(qū)分，我們可以對(duì)二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)增設(shè)兩個(gè)標(biāo)志域ltag和rtag，并作出如下約定：

• ltag = 0，lchild指向該結(jié)點(diǎn)的左孩子
• ltag = 1，lchild指向該結(jié)點(diǎn)的前驅(qū)
• rtag = 0，rchild指向該結(jié)點(diǎn)的右孩子
• rtag = 1，rchild指向該結(jié)點(diǎn)的后繼

所以其結(jié)點(diǎn)結(jié)構(gòu)應(yīng)為：

typedef struct BiThrNode{
	char data;
	struct BiThrNode *lchild,*rchild;
	int ltag,rtag;	//標(biāo)志域
}BiThrNode,*BiThrTree;

看下面的一棵二叉樹：

對(duì)其進(jìn)行先序線索化，先得出先序遍歷結(jié)果：A B C D E，其線索化結(jié)果為：

其中序線索化結(jié)果為(中序遍歷結(jié)果：B C A E D)：

后序線索化就留給大家自己畫一畫了。

到此這篇關(guān)于C語言實(shí)現(xiàn)二叉樹的示例詳解的文章就介紹到這了,更多相關(guān)C語言二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！