二叉树基本操作-数据结构

数据结构—二叉树基本操作

实现如下功能： （1）假设二叉树的结点值是字符，根据输入的一棵二叉树的括号表示法建立一棵以二叉链表表示的二叉树。 （2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 30  
#define NULL 0
#define ok 1
#define overflow -2
typedef char ElemType;
typedef struct BiTreeNode
{
          
   
  ElemType data;
  struct BiTreeNode *LChild,*RChild;   //队头指针，队尾指针;
  int height;  //二叉树高度
}BiTreeNode,*BiTree;
//先序建立二叉树
void InitBiTree(BiTree &T)
{
          
   
  return;
}
BiTree CreateBiTree( char *str,int i,int m)
{
          
   
  BiTree p;
  if(i>=m){
          
   
	  return NULL;}
    p=new BiTreeNode;
	p->data=str[i];
	printf("%c",p->data);
	p->LChild=CreateBiTree(str,2*i+1,m);  //创建结点左子树
	p->RChild=CreateBiTree(str,2*i+2,m);  //创建结点右子树
  return p;
}
//访问
void visit(char c)
{
          
   
 printf("the node is :%c
",c);
}

//先序遍历二叉树
void PreOrder(BiTree T)
{
          
    
 if(T!=NULL) 
 {
          
   
 visit(T->data); //访问根结点
 PreOrder(T->LChild);  //先序遍历左子树
  PreOrder(T->RChild);  //先序遍历右子树
}
}
//中序遍历二叉树
void InOrder(BiTree T)
{
          
    
 if(T!=NULL) 
 {
          
   
 InOrder(T->LChild);  //中序遍历左子树
visit(T->data);  //访问根结点
  InOrder(T->RChild);  //中序遍历右子树
 }
 }

//后序遍历二叉树
void PostOrder(BiTree T)
{
          
    
 if(T!=NULL)  
 {
          
   
 PostOrder(T->LChild);  //后序遍历左子树
  PostOrder(T->RChild);  //后序遍历右子树
visit(T->data); //访问根结点
}
}
//统计结点个数
int  PreOrderCount(BiTree pointer)
{
          
   
	int count=0;
 if(pointer==NULL) return NULL;
 else {
          
   
	 count++;
 PreOrderCount(pointer->LChild);  //先序遍历左子树
 PreOrderCount(pointer->RChild);  //先序遍历右子树
}
 return count;
}
void main()
{
          
   
   int i,n;
   char str[MAXSIZE];
	BiTree root;
//int a,height=0;
	int select;

  do {
          
   
printf("
 frist be use must be initiated !
");
printf("please choose (0--7):
");
printf("====================menu==========
");
printf("        1   to initBiTree       
");
printf("        2   to CreateBiTree       
");
printf("        3    to PreOrder  
");
printf("        4   to    InOrder
");
printf("        5    to PostOrder 
");
//printf("        6    the NoderHeight   
");
printf("          0      exit     
");
printf("
======================================
");
scanf("%d",&select);
switch(select)
{
          
   
case 1:
	{
          
    system("cls");
	InitBiTree(root);
	  printf("the bitree have been initated!
");
	   break;
	}
case 2:
	{
          
     system("cls");
       printf("please input a BiTree node num:
");
	scanf("%d",&n);
	getchar(); // 接收上一下语句scanf后的回车符
	printf("please input a string which length is %d:",n);
	for(i=0;i<n;i++)
		str[i]=getchar();
	printf("

");
	root=CreateBiTree(str,0,n);
	printf(" the tree is already creat
");
	break;

}
case 3:
	{
          
     system("cls");
      printf("preorder traverse
");
	   PreOrder(root);
	
	  break;
	}
case 4:
	{
          
     system("cls");
printf("Inorder traverse
");
	   InOrder(root);
	  break;
	}
case 5:
	{
          
     system("cls");
printf("PostOrder traverse
");
	   PostOrder(root);
	 break;
	}

case 0: exit(0);

}
  }while(select<=8);
}