线索二叉树源代码.docx
《线索二叉树源代码.docx》由会员分享，可在线阅读，更多相关《线索二叉树源代码.docx（57页珍藏版）》请在冰点文库上搜索。
线索二叉树源代码
Main.cpp
#include
#include
#include
#include
#include"Tree.cpp"
usingnamespacestd;
//-----------------------------------------------------------------------------
boolConvert1（strings1,strings2,string&str）;
boolConvert2（strings1,strings2,string&str）;
voidmenu（）;
voidcenter（stringstr,boole=1）;
//-----------------------------------------------------------------------------
voidmain（）{
menu（）;
charch=getch（）;
while（!
isdigit（ch））{
cout<center（"您的输入有误，请重新输入：
",0）;
ch=getch（）;
cout<}
Treet;
while
（1）{
switch（ch）{
case'1':
{
if（t.Getroot（）!
=NULL）{
cout<center（"您要重新创建二叉树吗？
"）;
center（"（请按回车键继续创建，其他键返回上一级。
）"）;
center（"请选择（回车键/其它键）：
",0）;
charch=getch（）;
cout<if（ch!
='\r'）{
center（"返回上一级成功！
"）;
break;
}
t.Destory（t.Getroot（））;
cout<}
cout<cout<cout<广义表构造法"<cout<先序和中序构造法"<cout<中序和后序构造法"<cout<center（"请选择（0-3）：
",0）;
charch=getch（）;
cout<while（!
（ch>='0'&&ch<='3'））{
center（"您的输入有误，请重新输入：
",0）;
ch=getch（）;
cout<}
switch（ch）{
case'1':
{
cout<";
for（stringstr;cin>>str;）
{
t=str;
if（t.Getroot（）==NULL）
{
cout<";
}
else
{
break;
}
}
center（"广义表构造法创建二叉树成功！
"）;
cout<"<t.PrintTree（t.Getroot（））;
break;
}
case'2':
{
stringstr;
strings1,s2;
cout<";
cin>>s1;
cout<";
cin>>s2;
while
（1）
{
if（Convert1（s1,s2,str））
{
break;
}
else
{
cout<";
cin>>s1;
cout<";
cin>>s2;
}
}
t=str;
center（"先序和中序构造法创建二叉树成功！
"）;
cout<"<t.PrintTree（t.Getroot（））;
break;
}
case'3':
{
stringstr;
strings1,s2;
cout<";
cin>>s2;
cout<";
cin>>s1;
while
（1）
{
Convert2（s1,s2,str）;
if
（1）
{
break;
}
else
{
cout<";
cin>>s2;
cout<";
cin>>s1;
}
}
t=str;
center（"中序和后序构造法创建二叉树成功！
"）;
cout<"<t.PrintTree（t.Getroot（））;
break;
}
default:
{
center（"返回上一级成功！
"）;
}
break;
}
}break;
case'2':
{
cout<cout<cout<t.PreOrderTraverse（t.Getroot（））;
cout<cout<cout<cout<t.InOrderTraverse（t.Getroot（））;
cout<cout<cout<cout<t.PostOrderTraverse（t.Getroot（））;
cout<cout<}break;
case'3':
{
cout<cout<cout<PreOrderTraverse（t.Getroot（））;
cout<cout<cout<cout<InOrderTraverse（t.Getroot（））;
cout<cout<cout<cout<PostOrderTraverse（t.Getroot（））;
cout<cout<cout<cout<t.LevelTraverse（）;
cout<cout<}break;
case'4':
{
cout<charsh='1';
TreeNode*p=newTreeNode（sh）;
cout<cout<t.PreOrderThreading（p）;
cout<t.Display2（p）;
cout<t.Destroy（）;
cout<cout<p->SetLeftChild（NULL）;
p->SetRightChild（NULL）;
t.InOrderThreading（p）;
cout<t.Display1（p）;
t.Destroy（）;
cout<cout<cout<p->SetLeftChild（NULL）;
p->SetRightChild（NULL）;
p->SetLflag1（）;
p->SetRflag1（）;
t.PostOrderThreading（p）;
cout<t.Display3（p）;
t.Destroy（）;
cout<}break;
case'5':
{
cout<cout<"<t.PrintTree（t.Getroot（））;
cout<cout<"<charlh;
lh=getch（）;
t.Insert（lh）;
cout<cout<"<t.PrintTree（t.Getroot（））;
}break;
case'6':
{
cout<cout<"<t.PrintTree（t.Getroot（））;
cout<cout<"<charh;
h=getch（）;
t.Remove（h）;
cout<cout<"<t.PrintTree（t.Getroot（））;
}break;
case'7':
{
cout<cout<"<if（t.Getroot（）!
=NULL）
t.PrintTree（t.Getroot（））;
else
cout<}break;
case'9':
{
system（"cls"）;
menu（）;
}break;
case'0':
{
cout<cout<return;
}break;
}
cout<center（"请输入您的选择：
",0）;
ch=getch（）;
while（!
isdigit（ch））
{
cout<center（"您的输入有误，请重新输入：
",0）;
ch=getch（）;
cout<}
}
}
voidmenu（）{
cout<cout<cout<创建二叉树"<cout<遍历（递归）"<cout<遍历（非递归）"<cout<线索化"<cout<插入节点"<cout<删除节点"<cout<显示二叉树"<cout<重新显示所有菜单"<cout<关闭窗口";
cout<cout<}
voidcenter（stringstr,boole）{
intnumber=（80-str.size（））/2;
cout<if（e）{
cout<}
}
boolConvert1（strings1,strings2,string&str）{
if（s1==""&&s2==""）{
return1;
}
charch=s1[0];
intpos=s2.find（ch）;
if（pos==-1）{
return0;
}
chartemp[3];
temp[0]=ch;
temp[1]='（';
temp[2]='\0';
str+=temp;
strings3,s4;
s3=s1.substr（1,pos）;
s4=s2.substr（0,pos）;
if（!
Convert1（s3,s4,str））{
return0;
}
str+=",";
strings5,s6;
s5=s1.substr（pos+1,s1.size（）-pos-1）;
s6=s2.substr（pos+1,s2.size（）-pos-1）;
if（!
Convert1（s5,s6,str））{
return0;
}
str+="）";
return1;
}
boolConvert2（strings1,strings2,string&str）{
if（s1==""&&s2==""）{
return1;
}
charch=s1[s1.size（）-1];
intpos=s2.find（ch）;
if（pos==-1）{
return0;
}
chartemp[3];
temp[0]=ch;
temp[1]='（';
temp[2]='\0';
str+=temp;
strings3,s4;
s3=s1.substr（0,pos）;
s4=s2.substr（0,pos）;
if（!
Convert2（s3,s4,str））{
return0;
}
str+=",";
strings5,s6;
s5=s1.substr（pos,s1.size（）-pos-1）;
s6=s2.substr（pos+1,s2.size（）-pos-1）;
if（!
Convert2（s5,s6,str））{
return0;
}
str+="）";
return1;
}
Tree.cpp
//================================================================================================================================
//二叉树的定义
//================================================================================================================================
#include