数据结构_二叉树(C语言)

(一)二叉树图文解析

<mark>本文章对递归的理解要求较高（反正我是说不清楚的=,=）</mark>

一般二叉树采用的是链式存储结构，也就是单链表的结构，但二叉树的结点包括俩个指针域，一个指向左结点，一个指右结点，即二叉；树的度：不管哪个结点，二叉树都只能最多分出俩个分支，所以二叉树的度为2；二叉树像树木一样分叉成俩根树枝，直到树木分叉到最后不再分叉，最后不再分叉的结点也就叫做树木的叶子。

(二) 二叉树代码解析

(1)二叉树的基本操作

1.1 二叉树的存储结构

typedef struct BiTNode
{
	char data;//结点数据域
	struct BiTNode *Lchild,*Rchild;//左指针和右指针
}BiTNode,*BiTree;

1.2 先序遍历创建二叉树

void CreatBiTree(BiTree &T)
{
	char ch;
	scanf("%c",&ch);//输入结点数据
	if(ch=='#')//输入为#代表结点为空，不再创建新结点
		T=NULL;
	else
	{
		T=(BiTNode*)malloc(sizeof(BiTNode));//为结点分配空间
		T->data=ch;//结点数据域为ch
		CreatBiTree(T->Lchild);//递归创建左结点
		CreatBiTree(T->Rchild);//递归创建右结点
	}
}

1.3 二叉树的先序遍历

void PreOrderTraverse(BiTree T)
{
	if(T)
	{
		printf("%c ",T->data);//先输出当前结点的数据
		PreOrderTraverse(T->Lchild);//然后递归遍历左结点,输出结点数据 
		PreOrderTraverse(T->Rchild);//再递归遍历右结点,输出结点数据
	}
}

遍历顺序要根据函数内递归顺序来：(强行解说递归，意会、意会…)
1、首先输出当前结点数据，然后递归遍历左结点，递归完左结点后再递归右结点；
2、递归左结点的过程中，依旧是先输出当前结点数据，直到左结点为空后结束递归
3、在递归完左结点后再递归完右结点，仍然是先输出当前结点数据，直到有结点为空后结束递归

1.4 二叉树的中序遍历

void InOrderTraverse(BiTree T)
{
	if(T)
	{
		InOrderTraverse(T->Lchild);//先递归遍历左结点，直到递归结束
		printf("%c ",T->data);//在输出数据
		InOrderTraverse(T->Rchild);//然后递归遍历右结点
	}//先遍历到最后一个左结点，再输出数据，然后遍历右结点
}

1.5 二叉树的后序遍历

void PostOrderTraverse(BiTree T)
{
	if(T)
	{
		PostOrderTraverse(T->Lchild);//先递归遍历左结点，直到结束
		PostOrderTraverse(T->Rchild);//再递归遍历右结点，直到结束
		printf("%c ",T->data);//最后输出数据
	}//先遍历到最后一个左结点，再遍历到最后一个左结点的最后一个右结点，最后输出数据
}

1.6 二叉树的深度

int Depth(BiTree T)
{
	if(T==NULL)
		return 0;
	else
	{
		int m=Depth(T->Lchild);//递归计算左子树的深度
		int n=Depth(T->Rchild);//递归计算右子树的深度
		if(m>n)//返回最大深度值
			return m+1;
		else
			return n+1;
	}
}

1.7 二叉树的结点数

int NodeCount(BiTree T)
{
	if(T==NULL)//结点为空，递归结束
		return 0;
	else//返回左结点+右结点+1,[+1]相当于计数结点的数量
		return NodeCount(T->Lchild)+NodeCount(T->Rchild)+1;
}

1.8 二叉树的叶子数

int LeafCount(BiTree T)
{
	if(T==NULL)
		return 0;
	else 
		if(!T->Lchild&&!T->Rchild)//单个结点没有子结点，叶子数为一
			return 1;
		else//递归计算左叶子数和右叶子数的总数
			return LeafCount(T->Lchild)+LeafCount(T->Rchild);
}

(2) 二叉树源代码及测试

2.1 源代码:

#include<stdio.h>
#include<malloc.h>
typedef struct BiTNode
{
	char data;
	struct BiTNode *Lchild,*Rchild;
}BiTNode,*BiTree;

void CreatBiTree(BiTree &T)
{
	char ch;
	scanf("%c",&ch);
	if(ch=='#')
	{
		T=NULL;
	}
	else
	{
		T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data=ch;
		CreatBiTree(T->Lchild);
		CreatBiTree(T->Rchild);
	}
}
void PreOrderTraverse(BiTree T)
{
	if(T)
	{
		printf("%c ",T->data);
		PreOrderTraverse(T->Lchild);		
		PreOrderTraverse(T->Rchild);
	}
}
void InOrderTraverse(BiTree T)
{
	if(T)
	{
		InOrderTraverse(T->Lchild);
		printf("%c ",T->data);
		InOrderTraverse(T->Rchild);
	}
}

void PostOrderTraverse(BiTree T)
{
	if(T)
	{
		PostOrderTraverse(T->Lchild);
		PostOrderTraverse(T->Rchild);
		printf("%c ",T->data);
	}
}

int Depth(BiTree T)
{
	if(T==NULL)
		return 0;
	else
	{
		int m=Depth(T->Lchild);
		int n=Depth(T->Rchild);
		if(m>n)
			return m+1;
		else
			return n+1;
	}
}

int NodeCount(BiTree T)
{
	if(T==NULL)
		return 0;
	else
		return NodeCount(T->Lchild)+NodeCount(T->Rchild)+1;
}
int LeafCount(BiTree T)
{
	if(T==NULL)
		return 0;
	else 
		if(!T->Lchild&&!T->Rchild)
			return 1;
		else
			return LeafCount(T->Lchild)+LeafCount(T->Rchild);
}

int main()
{
	BiTree T;
	printf("先序遍历创建二叉树\n输入结点数据('#'结束):");
	CreatBiTree(T);

	printf("先序遍历输出:");
	PreOrderTraverse(T);
	printf("\n");

	printf("中序遍历输出:");
	InOrderTraverse(T);
	printf("\n");

	printf("后序遍历输出:");
	PostOrderTraverse(T);
	printf("\n");

	printf("二叉树深度:%d\n",Depth(T));

	printf("二叉树结点数:%d\n",NodeCount(T));

	printf("二叉树叶子数:%d\n",LeafCount(T));
	
	return 0;
}