這期內(nèi)容當(dāng)中小編將會給大家?guī)碛嘘P(guān)二叉樹的三種遍歷方式的遞歸算法C代碼怎么寫，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

我們提供的服務(wù)有：成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、酉陽土家族苗族ssl等。為上千多家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的酉陽土家族苗族網(wǎng)站制作公司

基本概念

樹形結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用。

二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結(jié)點；深度為k的二叉樹至多有2^(k) -1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0
= n2 + 1。

二叉樹的遍歷：

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點，使每一個結(jié)點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實質(zhì)上是將二叉樹的各個結(jié)點轉(zhuǎn)換成為一個線性序列來表示。

二叉樹的三種遞歸的遍歷方法：

 先序遍歷

/* 二叉樹的建立和前序遍歷的C代碼實現(xiàn) */

#include 
#include 

typedef char ElemType;
typedef struct BiTNode {
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//創(chuàng)建二叉樹 遵循謙虛遍歷法輸入二叉樹的結(jié)點的數(shù)據(jù)
void CreatBiTree( BiTree *T )
{
	ElemType c;

	scanf("%c", &c);
	if( '^' == c ) {
		*T = NULL;
	}

	else {
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = c;
		CreatBiTree(&((*T)->lchild));
		CreatBiTree(&((*T)->rchild));
	}
}

//訪問二叉樹結(jié)點的具體操作
void visit( BiTree T, int level )
{
	printf("%c 在第 %d 層\n", T->data, level);
}


//遍歷二叉樹
void PreOrderTraverse( BiTree T, int level )
{
	if( T ) {
		visit( T , level );
		PreOrderTraverse( T->lchild, level+1 );
		PreOrderTraverse( T->rchild, level+1 );
	}
}

int main()
{
	BiTree T;
	CreatBiTree(&T);
	PreOrderTraverse( T, 1 );
	return 0;
}

中序遍歷

/* 二叉樹的中序遍歷打印結(jié)點數(shù)據(jù) */

#include 
#include 

typedef char Elemtype;

//創(chuàng)建二叉樹結(jié)點結(jié)構(gòu)體
typedef struct BiTNode {
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//前序遍歷一次輸入二叉樹的結(jié)點數(shù)據(jù)  創(chuàng)建二叉樹
void CreateBiTree( BiTree *t )
{
	Elemtype c;
	scanf("%c", &c);

	if( ' ' == c ) 
		*t = NULL;

	else {
		(*t) = (BiTree)malloc(sizeof(BiTNode));
		(*t)->data = c;
		CreateBiTree(&(*t)->lchild);
		CreateBiTree(&(*t)->rchild);
	}
}

//訪問二叉樹結(jié)點數(shù)據(jù)函數(shù)
void visit( BiTree t )
{
	printf("%c ", t->data );
}

//中序遍歷二叉樹函數(shù)
void InOrderTraverse( BiTree t )
{
	if( t ) {
		InOrderTraverse( t->lchild );
		visit( t );
		InOrderTraverse( t->rchild );
	}
}

int main()
{
	BiTree t;
	printf("請按照前序遍歷順序輸入數(shù)據(jù)建立二叉樹:\n");

	CreateBiTree( &t );

	InOrderTraverse( t );

	printf("\n");
	return 0;
}

后序遍歷

/* 二叉樹的后續(xù)遍歷的C代碼實現(xiàn) */

#include 
#include 

typedef char Elemtype;

//創(chuàng)建二叉樹結(jié)點結(jié)構(gòu)
typedef struct BiTNode {
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//前序遍歷輸入創(chuàng)建二叉樹
void CreateBiTree( BiTree *t )
{
	Elemtype c;
	scanf("%c", &c);

	if( ' ' == c )
		(*t) = NULL;
	else {
		(*t) = (BiTree)malloc(sizeof(BiTNode));
		(*t)->data = c;
		CreateBiTree( &(*t)->lchild );
		CreateBiTree( &(*t)->rchild );
	}
}

//訪問函數(shù)
void visit( BiTree t )
{
	printf("%c ", t->data);
}

//后序遍歷二叉樹
void PostOrderTraverse( BiTree t )
{
	if( NULL == t )
		return ;

	else {
		PostOrderTraverse( t->lchild );
		PostOrderTraverse( t->rchild );
		visit( t );
	}
}

int main()
{
	BiTree t;
	printf("請前序輸入二叉樹的結(jié)點序列:\n");

	CreateBiTree( &t );

	PostOrderTraverse( t );

	printf("\n");
	return 0;
}

上述就是小編為大家分享的二叉樹的三種遍歷方式的遞歸算法C代碼怎么寫了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。