text3.cpp

实现二叉树的各种操作,包括建立,遍历,查找等具体的内容

#include <stdio.h>
#include <malloc.h>
#define SIZE 100

int leftdep,rightdep;
typedef struct       BiTNode           //定义二叉树节点结构
{
char       data;                          //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;


int visit(BiTree t);
void CreateBiTree(BiTree &T);         //生成一个二叉树
void PreOrder(BiTree);               //递归先序遍历二叉树
void InOrder(BiTree);                //递归中序遍历二叉树
void PostOrder(BiTree);              //递归后序遍历二叉树
void InOrderTraverse(BiTree T); //非递归中序遍历二叉树
void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树
void LeverTraverse(BiTree T);//非递归层序遍历二叉树



/*
//建立二叉树  参数法
void TCreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);         //读入一个字符   
if(ch==' ') {T=NULL;printf("!");}      //注意递归的推出机制
else 
{
       T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点
       T->data=ch;
	   //printf("%c\n",ch);
       TCreateBiTree(T->lchild);       //生成左子树
	   //printf("%c\n",ch);
       TCreateBiTree(T->rchild);       //生成右子树
	   //printf("%c\n",ch);
          }
}
*/

//建立二叉树  非参数法
BiTree CreateBiTree()
{
BiTree t;
char ch;
scanf("%c",&ch);
if(ch==' ')t=NULL;

else {
     t=(BiTNode*)malloc(sizeof(BiTNode));
     t->data=ch;
	 t->lchild=CreateBiTree();
	 t->rchild=CreateBiTree();
	}
return t;
}

//先序遍历的递归
void PreOrder(BiTree T)
{
if(T)
{
       printf("%c ",T->data);       //访问结点
       PreOrder(T->lchild);        //遍历左子树
       PreOrder(T->rchild);        //遍历右子树
}
}
void InOrder(BiTree T)
{
if(T)
{
       InOrder(T->lchild);        //遍历左子树
       printf("%c ",T->data);       //访问结点
	   InOrder(T->rchild);        //遍历右子树
}
}

void printree(BiTree t)
{
	if(t!=NULL)
		{printf("%c",t->data);
		 if(t->lchild!=NULL||t->rchild!=NULL)
			{	printf("(");
				printree(t->lchild);
				if(t->rchild!=NULL)
				printf(",");
				printree(t->rchild);
				printf(")");
			}
		}
}

int treedepth(BiTree t)
{
  if(t==NULL) return 0;
  else
	{
		leftdep=treedepth(t->lchild);
		rightdep=treedepth(t->rchild);
		if(leftdep>rightdep)
		return (leftdep+1);
		else
		return (rightdep+1);
	}
}

/*int TreeLeaf(BiTree T)
{
if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL) return 1;
else return(TreeLeaf(T->lchild)+TreeLeaf(T->rchild));
}
*/
//主函数
void main()
{
BiTree T;       
char j;
int flag=1;
//---------------------程序解说-----------------------
printf("本程序实现二叉树的操作。\n");
printf("叶子结点以空格表示。\n");
printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n");
//----------------------------------------------------
printf("\n");
printf("请建立二叉树。\n");
printf("建树将以三个空格后回车结束。\n");
printf("例如:1 2 3 4 5 6        (回车)\n");
//CreateBiTree(T);            //初始化队列
T=CreateBiTree();
printree(T);

int H=treedepth(T);
printf("%d,%d,%d\n",H,leftdep,rightdep);

//int LeafNum=TreeLeaf(T);
//printf("TreeLeafNum=%d",LeafNum);
getchar();
while(flag)
         {
       printf("\n");
       printf("请选择: \n");
       printf("1.递归先序遍历\n");
       printf("2.递归中序遍历\n");
       printf("3.递归后序遍历\n");
       printf("4.非递归中序遍历\n");
       printf("5.非递归先序遍历\n");
       printf("6.非递归层序遍历\n");
       printf("0.退出程序\n");
       scanf(" %c",&j);
       switch(j)
       {
        case '1':if(T)
                 {
         printf("递归先序遍历二叉树:");
         PreOrder(T);
         printf("\n");
                  }
			else printf("二叉树为空!\n");
			break;
		case '2':if(T)
                 {
         printf("递归中序遍历二叉树:");
         InOrder(T);
         printf("\n");
                 }
            else printf("二叉树为空!\n");
            break;

        default:flag=0;printf("程序运行结束，按任意键退出!\n");
       }
         }
}