二叉树操作~请高手帮我调试一下！
#include "math.h" #include "malloc.h"
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include <queue>
#define stackinitsize 100
#define OK 1
#define ERROR 0
char prelist[stackinitsize];
char inlist[stackinitsize];
typedef int TElemType ;
typedef int Status;
//一一一一一二叉树的二叉链表存储表示一一一一一
typedef struct BiTNode{ //二叉树结构体
char data;
struct BiTNode *lchild,*rchild,*node; //左右孩子指针
}BiTNode,*SElemType,*BiTree;
typedef struct{
//该堆栈的元素是指针类型的
//base和top均是指向指针的指针
SElemType *base;
SElemType *top;
int stacksize;
}sqstack;//堆栈结构
Status InitStack(sqstack &s)//初始化堆栈
{
s.base=(SElemType*)malloc(100*sizeof(SElemType));
if(!s.base) return NULL;
s.top=s.base;
s.stacksize=100;
return OK;
}
int StackEmpty(sqstack &s) //栈空判别
{return(s.top==s.base); }
Status Pop(sqstack &s,SElemType &e)//弹栈(若栈不为空，删除栈顶元素，用e返回其值)
{ if(s.top==s.base) return ERROR;
e=*--s.top; return OK;}
Status GetTop(sqstack &s,SElemType &e) //若栈不为空，用e返回栈顶元素
{ if(s.top==s.base) return ERROR;
e=*(s.top-1);
return OK;
}
Status Push(sqstack &s,SElemType e)//将元素压入堆栈
{ if(s.top-s.base>=s.stacksize) //栈满，追加存储空间
{ s.base=(SElemType *) realloc (s.base,(s.stacksize+10)*sizeof(SElemType));
if(!s.base) exit (OVERFLOW); //存储分配失败
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*s.top++ =e;
return OK;
}
Status PrintElement(TElemType e) //应用函数
{ //输出元素e的值
printf("%2c",e);
return OK;
}
StatusPreOrderCreateBiTree(BiTree&T){ //按先序 次序构造二叉树
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。
//构造二叉链表表示的二叉树T.
char ch;
ch=getchar();
if(ch==' ') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW);
T->data=ch; //生成根结点
PreOrderCreateBiTree(T->lchild);//构造左子树
PreOrderCreateBiTree(T->rchild);//构造右子树
}
return OK;
}//CreateBiTree
BiTNode *preintotree(char pre[100],char in[100],int i,int j,int k,int l) //已知前序、后序序列恢复
二叉树
{
int m;
BiTNode *p;
p=(BiTNode*)malloc(sizeof(BiTNode));
p->data=pre[i];
m=k;
while(in[m]!=pre[i])
m++ ;
if (m==k)p->lchild=NULL;
else p->lchild=preintotree(pre,in,i+1,i+m-k,k,m-1);
if (m==j)p->rchild=NULL;
else p->rchild=preintotree(pre,in,i+m-k+1,j,m+1,l);
return p;
}
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) //先序遍历
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
{
if(T)
{ if (Visit(T->data))
if (PreOrderTraverse(T->lchild,Visit))
if (PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}
else return OK;
}//preOrderTraVerse
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) //中序遍历
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//中序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
{
if(T){
if (InOrderTraverse(T->lchild,Visit))
if (Visit(T->data))
if (InOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}
else return OK;
// printf("\n");
}//preOrderTraVerse
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) //后序遍历
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//后序遍历二叉树T的递归算法，对每个数据元素调用函数visit。
{
if(T){
if (PostOrderTraverse(T->lchild,Visit))
if (PostOrderTraverse(T->rchild,Visit))
if (Visit(T->data)) return OK;
return ERROR;
}
else return OK;
// printf("\n");
}//preOrderTraVerse
void LevelOrderTranslever(BiTNode *T) //层序遍
历
{
struct node
{
BiTNode *vec[20];
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");
}
Status Exchange(BiTNode *t) //交换左右子树
{
BiTNode *temp;
if(t)
{
Exchange(t->lchild);
Exchange(t->rchild);
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp; return OK;
}
return ERROR;
}
Status Leaves_Num(BiTNode *t) //计算叶子结点个
数
{ if(t){ if(t->lchild==NULL && t->rchild==NULL)return OK;
return (Leaves_Num(t->lchild)+Leaves_Num(t->rchild));
}
else return ERROR;
}
int a=0;
void Branch_Num(BiTNode *t) //计算分支结点
个数
{
if(t){
if(t->lchild!=NULL || t->rchild!=NULL)a++,Branch_Num(t->lchild),Branch_Num(t->rchild) ;
}
}
Status height(BiTNode *t) //二叉树的高度
{ if(!t) return ERROR;
int hl=height(t->lchild );
int hr=height(t->rchild );
if(hl>hr)return ++hl;
else return ++hr;
}
/*BiTNode *Search(BiTNode *T,char i) //查询结点
{ if(T!=NULL)
{ if(T->contents==i)return 1;
if(T->lchild !=NULL)
if(T->lchild ->contents ==i)return 2;
if(T->rchild !=NULL)
if(T->rchild ->contents ==i)return 3;
Search(T->lchild,i);
Search(T->rchild,i);
}
}
BiTNode * Search(BiTNode *T,int i) //按给定值在二叉排序树中查询
{
BiTNode * p;
if (T == NULL) p=NULL;
else { if (i == T-> data) p = T;
else if (i > T-> data) p = Search(i, T-> rchild);
else p=Search(i, T-> lchild);
return p;
}
void Search_bst(BiTNode *T)
{int s;
BiTNode *p;
char[5];
printf("\n");
printf( "请输入要查询的结点值: ");
scanf( "%d ",&s);
if ( s!= 0)
{p=Search(T,s);
if(p=NULL)printf( "该结点值不存在!\n ");
else printf( "该结点值存在!\n ");
}
}
/* { if(!T) return ERROR;
else if(elem==T->data)return OK;
else if(elem%2==0) Search(T->rchild,elem,T,p);
else Search(T->rchild,elem,T,p);
}*/
/*Status Insert(BiTNode *T,char i,TElemType e) //插入结点
{
BiTNode *s;
if(!s)
{ s=(BiTNode *)malloc(sizeof(BiTNode));
s->node->contents =e;s->lchild=s->rchild=NULL;
if(Search(T,i)==1)T->node =s;
if(Search(T,i)==2)T->lchild=s;
else if(Search(T,i)==3)T->rchild=s;
return OK;
}
else return ERROR;
}
/*void Delete(BiTNode *T,char i)//删除结点
{ if(T)
if(T->node==i)
{delete node;node=NULL;printf("已删除结点,当前树为空");}
}
BiTree q,s;
if(!p->rchild)
{ q=p;
p=p->lchild;
free(q);
}
else if(!p->lchild)
{
q=p;
p=p->rchild;
free(q);
}
else {
q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
q=s=p->lchild;
while(s->rchild) s=s->rchild;
s->rchild=p->rchild;
free (p);
p=q;
}
}*/
/*Status DeleteBST(BiTNode *T,TElemType elem)//删除树
{
if (!T){return ERROR;}
else{
if (elem==T->data) Delete(T);
else if ( elem<T->data) DeleteBST( T->lchild, elem);
else DeleteBST( T->rchild,elem);
return OK;
}
}*/
Status InorderTraverseNoRecursion(BiTree T,Status(*Visit)(TElemType e)) //中序非递归算法-------1
//采用二叉链表存储结构，visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。
{sqstack s;
BiTree p;
InitStack(s);p=T;
while(p||!StackEmpty(s))
{
if(p){ Push(s,p);p=p->lchild;}//根指针进栈，遍历左子树
else{ //根指针退栈，访问根结点，遍历右子树
Pop(s,p);
if(!Visit(p->data)) return ERROR;
p=p->rchild;
}//else
}//while
return OK;
}//InorderTraVerse1
/*Status InorderTraverseNoRecursion2(BiTree T,Status(*Visit)(TElemType e)) ////中序非递归算法 -------2
//采用二叉链表存储结构，visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。
{sqstack s;
BiTree p;
InitStack(s);Push(s,T);
while(!StackEmpty(s))
{
while(GetTop(s,p)&&p) Push(s,p->lchild);//向左走到尽头
Pop(s,p); //空指针退栈
if(!StackEmpty(s)) { //访问结点，向右一步
Pop(s,p);
if(!Visit(p->data)) return ERROR;
Push(s,p->rchild);
}//if
}//while
return OK;
}//InorderTraVerse1
*/
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;
int i,n;
grade:while(1)
{
printf("\n\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf(" ★★★ ★★★\n");
printf(" ★★★ 2.按先序次序构造二叉树 ★★★\n");
printf(" ★★★ 3.先序遍历、中序遍历、后序遍历 ★★★\n");
printf(" ★★★ 4.层序遍历 ★★★\n");
printf(" ★★★ 5.非递归中序遍历 ★★★\n");
printf(" ★★★ 6.二叉树高度 ★★★\n");
printf(" ★★★ 7.二叉树叶子结点个数 ★★★\n");
printf(" ★★★ 8.二叉树分支结点个数 ★★★\n");
printf(" ★★★ 9.二叉树中所有结点的左右子树交换 ★★★\n");
printf(" ★★★ r.返回主菜单 ★★★\n");
printf(" ★★★ 0.退出程序 ★★★\n");
printf(" ★★★ ★★★\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
printf(" ★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
while(1){
printf("\n请输入您的操作序号: ");
char d=getche();
switch(d)
{ case '0':printf("\n 程序运行结束，按任意键退出!\n\n");exit(0);break;
case '1':printf("\n请输入前序序列：\n");
getch();
for(n=0;;n++)//prelist[n]=getchar();
{
scanf("%c",&prelist[n]);
if(prelist[n-1]=='#') break;
}
printf("\n请输入中序序列：");
for(n=0;;n++)//inlist[n]=getchar();
{
scanf("%c",&inlist[n]);
if(prelist[n-1]=='#') break;
}
t=preintotree(prelist,inlist,0,strlen(prelist)-1,0,strlen(inlist)-1);
printf("\n恢复后的后序序列为：");
PostOrderTraverse(t,PrintElement);
break;
case '2':printf("\n请按先序遍历输入二叉树（当左右子树为空时用空格输入）
\n");PreOrderCreateBiTree(t);break;
case '3':printf("\n 该二叉树的先序遍历为：");PreOrderTraverse(t,PrintElement);
printf("\n 该二叉树的中序遍历为：
");InOrderTraverse(t,PrintElement);//Disptree(t);
printf("\n 该二叉树的后序遍历为：");PostOrderTraverse(t,PrintElement);
printf("\n 该二叉树的树状形态为：");Disptree(t);printf("\n");break;
case '4':printf("\n 该二叉树的层序遍历为：");LevelOrderTranslever(t);break;
case '5':printf("\n 该二叉树的中序遍历为(用非递归调用)：
");InorderTraverseNoRecursion(t,PrintElement);printf("\n");break;
case '6':printf("\n 该二叉树的高度为：%d",height(t));printf("\n");break;
case '7':printf("\n 该二叉树的叶子结点个数为：%d",Leaves_Num(t));printf("\n");break;
case '8':Branch_Num(t);printf("\n 该二叉树的分支结点个数
为：%d",a);printf("\n");break;
case '9':Exchange(t);printf("\n 该二叉树左右子树交换后的先序遍历为：");
PreOrderTraverse(t,PrintElement);printf("\n 该二叉树的树状形态为：
");Disptree(t);printf("\n");break;
case 'r':goto grade;
default:printf(" 输入无效，请重新选择操作!\n");
}
}
}
}
我太笨了啊！
头都大了啊！