bitree.cpp

数据结构中的二叉树排序问题

#include <malloc.h>
#include<stdio.h>
#define  maxsize  200       // 二叉树的最大结点数
typedef struct BinNode       // 二叉树的结点结构
{   char data;
    struct BinNode  *lchild, *rchild;    // 左右孩子指针
}BinTree;

void creatTree(BinTree **T)        //先序扩展序列建立二叉树
{
  char ch;
  printf("输入二叉树的先序扩展序列（空结点用 * 表示,输入结束标志'?'）：\n");
  scanf("%c",&ch);
  getchar();
  if(ch!='?')
  {
  if (ch=='*')  
   *T=NULL;
  else
  { 
   *T=(BinNode *)malloc(maxsize * sizeof(BinNode));
   (*T)->data = ch;              // 生成根结点  
   creatTree(&(*T)->lchild);      // 构造左子树
   creatTree(&(*T)->rchild);      // 构造右子树
  }
  }
} 

void preorder(BinTree *p)         //先序遍历二叉树递归
{  if(p!=NULL)
   {  printf("%c ",p->data);
      preorder(p->lchild);
      preorder(p->rchild);
   }
}
void inorder(BinTree *p)         //中序遍历二叉树递归
{  
  if(p!=NULL)
  {
    inorder(p->lchild);
	printf("%c ",p->data);
    inorder(p->rchild);
  }
}
void postorder(BinTree *p)         //后序遍历二叉树递归
{  if(p!=NULL)
   { 
     postorder(p->lchild);
     postorder(p->rchild);
     printf("%c ",p->data);
   }
}

void preorder1(BinTree *T)         //先序遍历二叉树非递归
{ 
  BinTree *a[maxsize],*p;
  int top=-1;
  if(T!=NULL)
  {
    top++;
	a[top]=T;
	while(top>-1)
	{
      p=a[top];
	  top--;
	  printf("%c ",p->data);
	  if(p->rchild!=NULL)
	  {
	    top++;
		a[top]=p->rchild;
	  }
	  if(p->lchild!=NULL)
	  {
		top++;
		a[top]=p->lchild;
	  }
	}
  }
}
void inorder1(BinTree *T)            //中序遍历二叉树非递归        
{
	BinTree *a[maxsize],*p;
    int top=-1;
	p=T;
	while((p!=NULL)||(top!=-1))
	{
		if(p!=NULL)
		{
		  top++;
	      a[top]=p;
		  p=p->lchild;
		}
		else
		{
		  p=a[top];
		  top--;
		  printf("%c",p->data);
		  p=p->rchild;
		}
	}
}
void postorder1(BinTree *T)       //后序遍历二叉树非递归
{
  BinTree *a[maxsize];
  BinTree *p;
  int flag,top=-1;
  do
  {
    while(T!=NULL)
	{
      top++;
	  a[top]=T;
	  T=T->lchild;
	}
	p=NULL;
	flag=1;
	while(top!=-1 && flag)
	{
	  T=a[top];
	  if(T->rchild==p)
	  {
		printf("%c ",T->data);
		top--;
		p=T;
	  }
	  else
	  {
	    T=T->rchild;
		flag=0;
	  }
	 } 
	}while(top!=-1);
}

void level(BinTree *T)              //层次遍历二叉树非递归
{
	struct node
	{
	  BinTree *a[maxsize];
	  int i,j;
	} q;
	q.i=0;
	q.j=0;
	if(T!=NULL)
	  printf("%c ",T->data);
	q.a[q.j]=T;
	q.j=q.j+1;
	while(q.i<q.j)
	{
	  T=q.a[q.i];
	  q.i=q.i+1;
	  if(T->lchild!=NULL)
	  {
		printf("%c ",T->lchild->data);
		q.a[q.j]=T->lchild;
		q.j=q.j+1;
	  }
      if(T->rchild!=NULL)
	  {
		printf("%c ",T->rchild->data);
		q.a[q.j]=T->rchild;
		q.j=q.j+1;
	  }
	}
}


int depth(BinTree *T)              //求二叉树深度
{
  int depth1,depth2;
  if(T==NULL)
    return 0;
  else
  {
	depth1=depth(T->lchild);
    depth2=depth(T->rchild);
	if(depth1>depth2)
	  return(depth1+1);
	else
      return(depth2+1);
  }
}


void main()
{
  char ch;
  BinTree *T=NULL;
  creatTree(&T);
  printf("a.先序扩展序列建立二叉树                           b.先序递归遍历二叉树\n");
  printf("c.中序递归遍历二叉树                               d.后序递归遍历二叉树\n");
  printf("e.先序非递归遍历二叉树                             f.中序非递归遍历二叉树\n");
  printf("g.后序非递归遍历二叉树                             h.层次非递归遍历二叉树\n");
  printf("i.后序遍历求二叉树深度\n");
  while(ch!='?')
  {
  printf("\n请选择操作：(结束选择用?)\n");
  scanf("%c",&ch);
  switch(ch)
  {
   case 'b':     printf("先序递归遍历二叉树: ");preorder(T); break;
   case 'c':     printf("中序递归遍历二叉树: ");inorder(T); break;
   case 'd':     printf("后序递归遍历二叉树: ");postorder(T); break;
   case 'e':     printf("先序非递归遍历二叉树:  ");preorder1(T); break;
   case 'f':     printf("中序非递归遍历二叉树: ");inorder1(T); break;
   case 'g':     printf("后序非递归遍历二叉树: ");postorder1(T); break;
   case 'h':     printf("层次非递归遍历二叉树: ");level(T); break;
   case 'i':     printf("树的深度为: %d",depth(T));
  }
  } 
}