学步园

基本概念

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

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（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;
}