![]() |
#2
农民工2016-06-29 09:39
|
用的方法是笨办法。
但是我想知道问题究竟出在哪里。
一步步调试了十来次,没有问题,运行的时候也大多没有问题,但是偶尔运行结果就不对了
测试数据有:ABC@@DE@G@@F@@@#以及ABD@@E@@CF@@G@@#
有时正常构建5层树,有时只有四层,有时则是三层(第一个测试数据)

#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<windows.h>
using namespace std;
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
int Tag;
};
BinTree Insert(BinTree BST,char X);
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
int GetHeight(BinTree Bt);
int main()
{
char data[50],ex;
int n;
cin.getline(data,49);
for(int i=0;i<49;i++)
{
if(data[i]=='#')
{
n=i;
break;
}
}
BinTree BST=NULL;
for(int j=0;j<n;j++)
{
BST=Insert(BST,data[j]);
}
cout<<endl;
PreorderTraversal(BST);
cout<<endl;
InorderTraversal(BST);
cout<<endl;
PostorderTraversal(BST);
cout<<endl;
LevelorderTraversal(BST);
cout<<endl;
cout<<GetHeight(BST);
system("pause");
return 0;
}
BinTree Insert(BinTree BST,char X)
{
if(!BST&&X!='@')
{
Position temp;
temp=(Position)malloc(sizeof(Position));
temp->Data=X;
temp->Left=temp->Right=NULL;
temp->Tag=2;
return temp;
}
if(BST)
{
Position temp;
switch(BST->Tag)
{
case 2:
if(X=='@')
{
BST->Tag--;
break;
}
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Data=X;
temp->Tag=2;
BST->Left=temp;
BST->Tag=1;
break;
case 1:
if(BST->Right)
{
BST->Right=Insert(BST->Right,X);
if(BST->Right->Tag==0) BST->Tag=0;
}
else if(BST->Left)
{
if(BST->Left->Tag!=0)
{
BST->Left=Insert(BST->Left,X);
}
else if(X!='@')
{
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Tag=2;
temp->Data=X;
BST->Right=temp;
}
else
{
BST->Tag--;
}
}
else
{
if(X!='@')
{
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Tag=2;
temp->Data=X;
BST->Right=temp;
}
else
{
BST->Tag--;
}
}
break;
case 0:
cout<<endl<<"错误"<<endl;
break;
}
return BST;
}
return BST;
}
// InorderTraversal
void InorderTraversal(BinTree Bt)
{
if(Bt)
{
InorderTraversal(Bt->Left);
cout<<Bt->Data;
InorderTraversal(Bt->Right);
}
return;
}
// PreorderTraversal
void PreorderTraversal(BinTree Bt)
{
if(Bt)
{
cout<<Bt->Data;
PreorderTraversal(Bt->Left);
PreorderTraversal(Bt->Right);
}
return;
}
// PostorderTraversal
void PostorderTraversal(BinTree Bt)
{
if(Bt)
{
PostorderTraversal(Bt->Left);
PostorderTraversal(Bt->Right);
cout<<Bt->Data;
}
return;
}
// LevelorderTraversal
void LevelorderTraversal(BinTree Bt)
{
BinTree ArrBt[100], T;
int top=0;
int head=0;
if(!Bt) return;
ArrBt[top++]=Bt;
while(top!=head)
{
T=ArrBt[head++];
cout<<T->Data;
if(T->Left) ArrBt[top++]=T->Left;
if(T->Right) ArrBt[top++]=T->Right;
}
cout<<endl;
return;
}
int GetHeight(BinTree Bt)
{
int a=0,b=0;
if(Bt)
{
a=1+GetHeight(Bt->Left);
b=1+GetHeight(Bt->Right);
int c=a>b?a:b;
return c;
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include<windows.h>
using namespace std;
typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
int Tag;
};
BinTree Insert(BinTree BST,char X);
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
int GetHeight(BinTree Bt);
int main()
{
char data[50],ex;
int n;
cin.getline(data,49);
for(int i=0;i<49;i++)
{
if(data[i]=='#')
{
n=i;
break;
}
}
BinTree BST=NULL;
for(int j=0;j<n;j++)
{
BST=Insert(BST,data[j]);
}
cout<<endl;
PreorderTraversal(BST);
cout<<endl;
InorderTraversal(BST);
cout<<endl;
PostorderTraversal(BST);
cout<<endl;
LevelorderTraversal(BST);
cout<<endl;
cout<<GetHeight(BST);
system("pause");
return 0;
}
BinTree Insert(BinTree BST,char X)
{
if(!BST&&X!='@')
{
Position temp;
temp=(Position)malloc(sizeof(Position));
temp->Data=X;
temp->Left=temp->Right=NULL;
temp->Tag=2;
return temp;
}
if(BST)
{
Position temp;
switch(BST->Tag)
{
case 2:
if(X=='@')
{
BST->Tag--;
break;
}
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Data=X;
temp->Tag=2;
BST->Left=temp;
BST->Tag=1;
break;
case 1:
if(BST->Right)
{
BST->Right=Insert(BST->Right,X);
if(BST->Right->Tag==0) BST->Tag=0;
}
else if(BST->Left)
{
if(BST->Left->Tag!=0)
{
BST->Left=Insert(BST->Left,X);
}
else if(X!='@')
{
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Tag=2;
temp->Data=X;
BST->Right=temp;
}
else
{
BST->Tag--;
}
}
else
{
if(X!='@')
{
temp=(Position)malloc(sizeof(Position));
temp->Left=temp->Right=NULL;
temp->Tag=2;
temp->Data=X;
BST->Right=temp;
}
else
{
BST->Tag--;
}
}
break;
case 0:
cout<<endl<<"错误"<<endl;
break;
}
return BST;
}
return BST;
}
// InorderTraversal
void InorderTraversal(BinTree Bt)
{
if(Bt)
{
InorderTraversal(Bt->Left);
cout<<Bt->Data;
InorderTraversal(Bt->Right);
}
return;
}
// PreorderTraversal
void PreorderTraversal(BinTree Bt)
{
if(Bt)
{
cout<<Bt->Data;
PreorderTraversal(Bt->Left);
PreorderTraversal(Bt->Right);
}
return;
}
// PostorderTraversal
void PostorderTraversal(BinTree Bt)
{
if(Bt)
{
PostorderTraversal(Bt->Left);
PostorderTraversal(Bt->Right);
cout<<Bt->Data;
}
return;
}
// LevelorderTraversal
void LevelorderTraversal(BinTree Bt)
{
BinTree ArrBt[100], T;
int top=0;
int head=0;
if(!Bt) return;
ArrBt[top++]=Bt;
while(top!=head)
{
T=ArrBt[head++];
cout<<T->Data;
if(T->Left) ArrBt[top++]=T->Left;
if(T->Right) ArrBt[top++]=T->Right;
}
cout<<endl;
return;
}
int GetHeight(BinTree Bt)
{
int a=0,b=0;
if(Bt)
{
a=1+GetHeight(Bt->Left);
b=1+GetHeight(Bt->Right);
int c=a>b?a:b;
return c;
}
return 0;
}