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

這期內容當中小編將會給大家帶來有關二叉樹的三種遍歷方式的遞歸算法C代碼怎么寫，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

基本概念

樹形結構是一類重要的非線性數據結構，其中以樹和二叉樹最為常用。

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

二叉樹的遍歷：

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

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

 先序遍歷

/* 二叉樹的建立和前序遍歷的C代碼實現 */

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

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

//創建二叉樹 遵循謙虛遍歷法輸入二叉樹的結點的數據
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));
	}
}

//訪問二叉樹結點的具體操作
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;
}

中序遍歷

/* 二叉樹的中序遍歷打印結點數據 */

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

typedef char Elemtype;

//創建二叉樹結點結構體
typedef struct BiTNode {
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//前序遍歷一次輸入二叉樹的結點數據  創建二叉樹
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);
	}
}

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

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

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

	CreateBiTree( &t );

	InOrderTraverse( t );

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

后序遍歷

/* 二叉樹的后續遍歷的C代碼實現 */

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

typedef char Elemtype;

//創建二叉樹結點結構
typedef struct BiTNode {
	Elemtype data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//前序遍歷輸入創建二叉樹
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 );
	}
}

//訪問函數
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("請前序輸入二叉樹的結點序列:\n");

	CreateBiTree( &t );

	PostOrderTraverse( t );

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

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