二叉链表（C语言实现）——递归和非递归遍历_Mr

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define QueueSize 100					//	借助队列实现层序遍历 
#define StackSize 100					//	借助栈实现非递归遍历 
typedef char DataType;
typedef struct BiTNode
{
	DataType data;
	struct BiTNode * lchild;
	struct BiTNode * rchild;
	
}BiTNode,*BiTree;
 
//	栈元素类型 
typedef struct SNode
{
	BiTNode * bt;	//	结点域 
	int flag;		//	标志域 
	
}ElemType;
 
void Creat_BiTree(BiTree* T);			//	建立树 
int Depth_BiTree(BiTree T);				//	树深度 
int Count_BiTree(BiTree T);				//	树结点个数 
int LeafCount_BiTree(BiTree T);			//	树叶子结点个数 
bool Destroy_BiTree(BiTree T);			//	销毁树 
void PreOrder_Traverse(BiTree T);		//	前序遍历递归算法 
void InOrder_Traverse(BiTree T);		//	中序遍历递归算法 
void PostOrder_Traverse(BiTree T);		//	后序遍历递归算法 
void Level_Traverse(BiTree T);			//	层序遍历 
void Pre_Traverse(BiTree T);			//	前序遍历非递归算法
void In_Traverse(BiTree T);				//	中序遍历非递归算法
void Post_Traverse(BiTree T);			//	后序遍历非递归算法 
 
int main()
{
	BiTree T;
	printf("请输入根结点："); 
	Creat_BiTree(&T);
	
	printf("
");	
	printf("树深度：%%d
",Depth_BiTree(T)) ;
	printf("树结点个数：%%d
",Count_BiTree(T));
	printf("树叶子结点个数：%%d
",LeafCount_BiTree(T));
	
	printf("
————————层序遍历算法————————
");
	printf("层序遍历：");
	Level_Traverse(T);
	printf("

");
	
	printf("
————————递归遍历算法————————
");
	printf("递归前序遍历：");
	PreOrder_Traverse(T);
	printf("

");
	
	printf("递归中序遍历：");
	InOrder_Traverse(T);
	printf("

");
	
	printf("递归后序遍历：");
	PostOrder_Traverse(T);
	printf("

");
	
	printf("
————————非递归遍历算法————————
"); 
	printf("非递归前序遍历：");
	Pre_Traverse(T);
	printf("

");
	
	printf("非递归中序遍历：");
	In_Traverse(T);
	printf("

");
	
	printf("非递归后序遍历：");
	Post_Traverse(T);
	printf("

");
	
	return 0;
	
}
 
//	注意产生空指针 
void Creat_BiTree(BiTree* T)
{
	char ch; 
	fflush(stdin);
	scanf("%%c",&ch);
	if(ch == '#')
	{
		*T = NULL; 
		return;
	}
	else
	{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = ch;
		printf("请输入%%c的左子树结点：", ch);
		Creat_BiTree(&(*T)->lchild);
		printf("请输入%%c的右子树结点：", ch);
		Creat_BiTree(&(*T)->rchild);
	}
}
 
int Depth_BiTree(BiTree T)
{
	if(!T)
		return; 
	//	递归求树深度 
	return Depth_BiTree(T->lchild) > Depth_BiTree(T->rchild) ? Depth_BiTree(T->lchild)+1 : Depth_BiTree(T->rchild)+1;//	深度=最大层数+1 
}
 
int Count_BiTree(BiTree T)
{
	if(!T)
		return;
	//	递归求树结点数
	return 	Count_BiTree(T->lchild) + Count_BiTree(T->rchild) + 1;	//	树结点：左子树结点+右子树结点+根结点 
	
}
 
int LeafCount_BiTree(BiTree T)
{
	if(!T)
		return;
		
	if(T->lchild==NULL && T->rchild==NULL)	//	左、右孩子指针域均为空时为叶子结点 
		return 1;
	else	
		 return LeafCount_BiTree(T->lchild) + LeafCount_BiTree(T->rchild);
}
 
bool Destroy_BiTree(BiTree T)
{
	if(!T)
		return false;
		
	Destroy_BiTree(T->lchild);
	Destroy_BiTree(T->rchild);
	free(T);
	T = NULL;	//	防止产生野指针 
	return true; 
}
 
void PreOrder_Traverse(BiTree T)
{
	if(!T)
		return;
		
	printf("%%3c",T->data);
	PreOrder_Traverse(T->lchild);
	PreOrder_Traverse(T->rchild);
}
 
void InOrder_Traverse(BiTree T)
{
	if(!T)
		return;
		
	InOrder_Traverse(T->lchild);
	printf("%%3c",T->data);
	InOrder_Traverse(T->rchild);
}
 
void PostOrder_Traverse(BiTree T)
{
	if(!T)
		return;
		
	PostOrder_Traverse(T->lchild);
	PostOrder_Traverse(T->rchild);
	printf("%%3c",T->data);
}
 
void Level_Traverse(BiTree T)
{
	// 初始化队列
	BiTree Q[QueueSize]; 
	int front = 0;
	int rear = 0;
	
	if(!T)
		return;
	Q[rear++] = T;
	while(front != rear)
	{
		BiTree p = Q[front++];
		printf("%%3c",p->data);
				
		if(p->lchild!=NULL)
			Q[rear++] = p->lchild;
		if(p->rchild!=NULL)
			Q[rear++] = p->rchild;
	}
	return;
}
 
void Pre_Traverse(BiTree T)
{	
	BiTree p = T;		//	初始化工作指针
	 
//	将栈初始化 
	BiTree Stack[StackSize];
	int top = -1;
	
	while(p!=NULL || top!=-1)	//	两个条件都不成立时，才能退出循环 
	{
		if(p!=NULL)
		{
			printf("%%3c",p->data);	//	访问输出结点后，将其入栈 
			Stack[++top] = p;
			p = p->lchild;
		}
		else
		{
			p = Stack[top--];
			p = p->rchild;
		}
	}
	
} 
 
void In_Traverse(BiTree T)
{
	BiTree p = T;		//	初始化工作指针
	
//	栈初始化
	BiTree Stack[StackSize];
	int top = -1;
	
	while(p!=NULL || top!=-1)
	{
		if(p!=NULL)
		{
			Stack[++top] = p;
			p = p->lchild;
		}
		else 
		{
			p = Stack[top--];
			printf("%%3c",p->data);	//	出栈后，访问输出结点 
			p = p->rchild;
		}
	} 
}  
 
void Post_Traverse(BiTree T)
{
	BiTree p = T;
	ElemType Stack[StackSize];
	int top = -1;
	
	while(p!=NULL || top!=-1 )
	{
		if(p!=NULL)
		{
			++top;
			Stack[top].bt = p;
			Stack[top].flag = 1;
			p = p->lchild;	
		}
		else  
		{
			if(Stack[top].flag==1)//	左子树遍历完，访问栈顶元素但不出栈，随后将标志域设为2，并遍历右子树 
			{
				p = Stack[top].bt;	
				Stack[top].flag = 2;
				p = p->rchild; 
			}
			else
			{
				p = Stack[top--].bt;
				printf("%%3c",p->data);
				p = NULL;	//	p置空，以便继续退栈 
			}
		}	
	} 
}

 ①前序遍历

②中序遍历

 

 

③后序遍历

 

④层序遍历