shu.cpp

二叉树的常用算法

#include<stdio.h>
#include<malloc.h>
#include <math.h >
#define  MaxSize 20

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

//建立二叉树
void CreateBiTree(BiTree *T)
{
	char ch;
	scanf("%c",&ch);
	getchar();
	if(ch==' ')
	{
		printf("不产生子树。\n");
		*T=NULL;
	}
	else
	{
		if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))
		{
			printf("分配空间失败");
			return;
		}//生成一个新节点
		(*T)->data = ch;
		printf("产生左右子树。\n");
		CreateBiTree(&(*T)->lchild);                           
		CreateBiTree(&(*T)->rchild);                            
	}
}

//递归前序遍历
void Preorder(BiTNode *T)
 {
	 if(T)
	 {
		 printf("%c ",T->data);
		 Preorder(T->lchild);                                
		 Preorder(T->rchild);                              
	 }
}

//递归中序遍历
void Inorder(BiTNode *T)
{
	 if(T)
	 {
		 Inorder(T->lchild);
		 printf("%c ",T->data);
		 Inorder(T->rchild);
	 } 
}

//递归后序遍历
void Postorder(BiTNode *T)
{
	if(T)
	{
		Postorder(T->lchild);
		Postorder(T->rchild);
		printf("%c ",T->data);
	} 
}

//非递归前序遍历
void NPreorder(BiTNode *T)
 {
	BiTNode *stack[MaxSize],*p;
	int top=-1;
	 if(T)
	 {
		 top++;
		 stack[top]=T;                  //根节点进栈
		 while(top>-1)                  //栈不为空时循环
		 {
			 p=stack[top];              //退栈并访问该节点
			 top--;
			 printf("%c ",p->data);
			 if(p->rchild)             //右孩子进栈
			 {
				 top++;
				 stack[top]=p->rchild;
			 }
			 if(p->lchild)             //左孩子进栈
			 {
				 top++;
				 stack[top]=p->lchild;
			 }
		 }                          
	 }
}

//非递归中序遍历
void NInorder(BiTNode *T)
{
	BiTNode *stack[MaxSize],*p;
	int top=-1;
	p=T;
	while(p||top!=-1)
	{
		if(p)
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}                              //根节点进栈，遍历左子树
		else                           //根节点退栈，访问根节点，遍历右子树
		{
			p=stack[top];
			top--;
			printf("%c ",p->data);
			p=p->rchild;
		}
	}
}

//非递归后序遍历
void NPostorder(BiTNode *T)
{
	BiTNode *stack[MaxSize],*p;
	int flag,top=-1;
	do
	{
		while(T)
		{
			top++;
			stack[top]=T;
			T=T->lchild;
		}                              //所有左节点进栈
		p=NULL;                        //p总是指向当前节点的前一个已经访问过的节点
		flag=1;                        //flag为1表示当前节点已经访问过了
		while(top!=-1 && flag)
		{
			T=stack[top];
			if(T->rchild==p)          //右子树不存在或者已经被访问过时
			{
				printf("%c ",T->data);
				top--;
				p=T;                  //调整p指针
			}
			else
			{
				T=T->rchild;
				flag=0;              //调整访问标志
			}
		}
	} while(top!=-1);
}

//层次遍历二叉树
void Translever(BiTNode *T)
{
	struct node
	{
		BiTNode *vec[MaxSize];
		int f,r;                //r为队尾，f为队头
	}queue;
	BiTNode *p;
	p=T;
	queue.f=0;
	queue.r=0;
	if(T)
		printf("%c ", p->data);
	queue.vec[queue.r]=p;
	queue.r=queue.r+1;
	while(queue.f<queue.r)
	{
		p=queue.vec[queue.f];
		queue.f=queue.f+1;
		if(p->lchild)
		{
			printf("%c ",p->lchild->data);
			queue.vec[queue.r]=p->lchild;
			queue.r=queue.r+1;
		}
		if(p->rchild)
		{
			printf("%c ",p->rchild->data);
			queue.vec[queue.r]=p->rchild;
			queue.r=queue.r+1;
		}
	}
	printf("\n");
}

//求二叉树的深度
int Depth(BiTNode *T)
{
	int dep1,dep2;
	if(T==NULL)
		return(0);
	else
	{
		dep1=Depth(T->lchild);
		dep2=Depth(T->rchild);
		if(dep1>dep2)
			return(dep1+1);
		else
			return(dep2+1);
	}
}

//输出二叉树
void Disptree(BiTNode *T)
{
	if(T)
	{
		printf("%c",T->data);
        if(T->lchild || T->rchild)
		{
			printf("(");
			Disptree(T->lchild);
			if(T->rchild)
				printf(",");
			Disptree(T->rchild);
			printf(")");
		}
	}
}
 
void main()
{
	BiTree T=NULL;
	char j;
	int sign = 1;

	printf("*本程序可以进行建立二叉树、递归与非递归先序、中序、后序遍历二叉树、层次遍历二叉树、输出二叉树的扩展序列的操作。\n");
	printf("*请将二叉树的先序序列输入以建立二叉树，叶子节点用空格代替。\n");
	printf("*您必须一个一个地输入字符。\n");
	while(sign)
	{ 
		printf("请选择: \n");
		printf("0.生成二叉树                                 1.求二叉树的深度\n");
		printf("2.递归先序遍历                               3.非递归先序遍历\n");
		printf("4.递归中序遍历                               5.非递归中序遍历\n");
		printf("6.递归后序遍历                               7.非递归后序遍历\n"); 
		printf("8.层次遍历                                   9.输出二叉树的广义表形式\n");
		printf("q.退出程序\n");
		scanf("%c",&j);
		getchar();
		switch(j)
		{
		case '0':
			printf("生成二叉树:");
			CreateBiTree(&T); 
			printf("\n");
			printf("\n");
			break;
		case '1':
			if(T)
			{
				printf("此二叉树的深度为:");
				printf("%d",Depth(T));
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		case '2':
			if(T)
			{
				printf("递归先序遍历二叉树:");
				Preorder(T);
				printf("\n");
				printf("\n");
			}
			else 
				printf("二叉树为空!\n");
			break;
        case '3':
			if(T)
			{
				printf("非递归先序遍历二叉树:");
				NPreorder(T);
				printf("\n");
				printf("\n");
			}
			else 
				printf("二叉树为空!\n");
			break;
		case '4':
			if(T)
			{
				printf("递归中序遍历二叉树:");
				Inorder(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		case '5':
			if(T)
			{
				printf("非递归中序遍历二叉树:");
				NInorder(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		case '6':
			if(T)
			{
				printf("递归后序遍历二叉树:");
				Postorder(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		case '7':
			if(T)
			{
				printf("非递归后序遍历二叉树:");
				NPostorder(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
        case '8':
			if(T)
			{
				printf("层次遍历二叉树:");
				Translever(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		case '9':
			if(T)
			{
				printf("输出二叉树:");
				Disptree(T);
				printf("\n");
				printf("\n");
			}
			else printf("二叉树为空!\n");
			break;
		default:
			sign=0;
			printf("程序运行结束，按任意键退出!\n");
		}
	}
}