二叉樹的三種遍歷方式的遞歸算法C代碼怎么寫

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

基本概念

樹形結(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)；對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0
= n2 + 1。

二叉樹的遍歷：

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

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

 先序遍歷

/* 二叉樹的建立和前序遍歷的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("請(qǐng)按照前序遍歷順序輸入數(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("請(qǐng)前序輸入二叉樹的結(jié)點(diǎn)序列:\n");

	CreateBiTree( &t );

	PostOrderTraverse( t );

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

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