阿坝州网站建设公司

二叉树的三种遍历方式的递归算法C代码怎么写

这期内容当中小编将会给大家带来有关二叉树的三种遍历方式的递归算法C代码怎么写，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

我们提供的服务有：成都网站制作、成都网站建设、外贸营销网站建设、微信公众号开发、网站优化、网站认证、酉阳土家族苗族ssl等。为上千多家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的酉阳土家族苗族网站制作公司

基本概念

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0
= n2 + 1。

二叉树的遍历：

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

二叉树的三种递归的遍历方法：

先序遍历访问根节点→先序遍历左子树→先序遍历右子树
中序遍历中序遍历左子树→访问根节点→中序遍历右子树
后序遍历后序遍历左子树→后序遍历右子树→访问根节点

 先序遍历

/* 二叉树的建立和前序遍历的C代码实现 */

#include 
#include 

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 
#include 

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 
#include 

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代码怎么写了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。


名称栏目：二叉树的三种遍历方式的递归算法C代码怎么写
分享路径：http://azwzsj.com/article/iphcsp.html

其他资讯