這期內(nèi)容當(dāng)中小編將會(huì)給大家?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)，其中以樹和二叉樹最為常用。

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

二叉樹的遍歷：

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

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

先序遍歷	訪問根節(jié)點(diǎn)→先序遍歷左子樹→先序遍歷右子樹
中序遍歷	中序遍歷左子樹→訪問根節(jié)點(diǎn)→中序遍歷右子樹
后序遍歷	后序遍歷左子樹→后序遍歷右子樹→訪問根節(jié)點(diǎn)

 先序遍歷

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

#include <stdio.h>
#include <stdlib.h>

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

//創(chuàng)建二叉樹 遵循謙虛遍歷法輸入二叉樹的結(jié)點(diǎn)的數(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é)點(diǎn)的具體操作
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é)點(diǎn)數(shù)據(jù) */

#include <stdio.h>
#include <stdlib.h>

typedef char Elemtype;

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

//前序遍歷一次輸入二叉樹的結(jié)點(diǎn)數(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é)點(diǎn)數(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代碼實(shí)現(xiàn) */

#include <stdio.h>
#include <stdlib.h>

typedef char Elemtype;

//創(chuàng)建二叉樹結(jié)點(diǎn)結(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é)點(diǎn)序列:\n");

	CreateBiTree( &t );

	PostOrderTraverse( t );

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

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

分享文章：二叉樹的三種遍歷方式的遞歸算法C代碼怎么寫
轉(zhuǎn)載來源：http://www.chinadenli.net/article38/iphcsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、品牌網(wǎng)站制作、網(wǎng)頁設(shè)計(jì)公司、域名注冊、標(biāo)簽優(yōu)化、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)