线索二叉树实验.docx
《线索二叉树实验.docx》由会员分享，可在线阅读，更多相关《线索二叉树实验.docx（17页珍藏版）》请在冰点文库上搜索。
线索二叉树实验
实验名称：
线索二叉树
一、实验目的和要求∶
（1）掌握线索二叉树的有关知识。
（2）掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法。
（3）掌握二叉树的线索化算法的设计。
二、实验环境和仪器设备∶
Windowsxp/UbuntuVC++6.0
三、实验任务∶
<1>按先序次序遍历先序线索二叉树。
<2>按中序次序遍历中序线索二叉树。
<3>将值为x的结点作为先序线索二叉树T的左子树的（先序）最后一个结点的右孩子插入进去。
<4>按中序次序线索化二叉树。
<5>按后序次序线索化二叉树。
四、实验内容（步骤）∶
<1>设计二叉树的数据结构，并根据数据结构设计算法实现。
<2>编写源代码
<3>上机调试
<4>总结
五、实验程序
#include
#include
usingnamespacestd;
enumThread{
notThreaded,
preThreaded,
midThreaded,
postThreaded};
template
structBiThrNode{
Element_typedata;
BiThrNode*lchild,*rchild;
boolltag,rtag;
};
template
classBiThrTree{
public:
BiThrTree（）;
BiThrTree（constchar*filename）;//根据文件构造二叉树
~BiThrTree（）;//析构函数
voidBuild（constchar*filename）;//根据文件创建二叉树
voidPreOrder（）;//先序遍历二叉树
voidMidOrder（）;//中序遍历二叉树
voidPostOrder（）;//后序遍历二叉树
BiThrNode*PreSuc（BiThrNode*node）const;//先序后继
BiThrNode*MidSuc（BiThrNode*node）const;//中序后继
BiThrNode*PostUsher（BiThrNode*node）const;//后序前驱
voidPostPrint（）;//输出后序遍历二叉树
voidPostPrint（BiThrNode*node）;
voidPreThread（）;//先序线索化
voidPreThread（BiThrNode*node）;
voidMidThread（）;//中序线索化
voidMidThread（BiThrNode*node）;
voidPostThread（）;//后序线索化
voidPostThread（BiThrNode*node）;
voidInsertAtL（Element_typedata）;//插入为左子树先序最后一个结点的右孩子
voidClear（）;//删除二叉树
voidClear（BiThrNode*node）;
voidVisit（BiThrNode*node）;//访问结点
private:
voidCreatNode（BiThrNode*node）;
BiThrNode*root;
ifstreamfile;
Threadstatus;
BiThrNode*pre;
};
template
BiThrTree:
:
BiThrTree（）{
root=NULL;
status=notThreaded;
}
template
BiThrTree:
:
BiThrTree（constchar*filename）{
root=NULL;
Build（filename）;
}
template
BiThrTree:
:
~BiThrTree（）{
Clear（）;
root=NULL;
}
template
voidBiThrTree:
:
Build（constchar*filename）{
if（root!
=NULL）
Clear（）;
Element_typedata;
chartree[40];
intchild;
file.open（filename）;
file>>tree>>child;
if（child==0）{
file>>data;
root=newBiThrNode;
root->data=data;
root->lchild=NULL;
root->rchild=NULL;
root->ltag=false;
root->rtag=false;
CreatNode（root）;
}
elseroot=NULL;
status=notThreaded;
}
template
voidBiThrTree:
:
PreOrder（）{
if（status==notThreaded）
PreThread（）;
BiThrNode*te=root;
while（te!
=NULL）{
Visit（te）;
te=PreSuc（te）;
}
}
template
voidBiThrTree:
:
MidOrder（）{
if（status==notThreaded）
MidThread（）;
BiThrNode*te=root;
if（te==NULL）
return;
while（te->lchild!
=NULL）
te=te->lchild;
while（te!
=NULL）{
Visit（te）;
te=MidSuc（te）;
}
}
template
voidBiThrTree:
:
PostOrder（）{
if（status==notThreaded）{
PostThread（）;
PostPrint（）;
}
}
template
BiThrNode*BiThrTree:
:
PreSuc（BiThrNode*node）const{
if（!
node->ltag）
returnnode->lchild;
elsereturnnode->rchild;
}
template
BiThrNode*BiThrTree:
:
MidSuc（BiThrNode*node）const{
if（node->rtag）
returnnode->rchild;
BiThrNode*te=node->rchild;
if（te==NULL）
returnte;
while（!
te->ltag）
te=te->lchild;
returnte;
}
template
BiThrNode*BiThrTree:
:
PostUsher（BiThrNode*node）const{
if（!
node->rtag）
returnnode->rchild;
else
returnnode->lchild;
}
template
voidBiThrTree:
:
PostPrint（）{
PostPrint（root）;
}
template
voidBiThrTree:
:
PostPrint（BiThrNode*node）{
if（node==NULL）
return;
PostPrint（PostUsher（node））;
cout<data<<"";
}
template
voidBiThrTree:
:
PreThread（）{
if（status==notThreaded）{
pre=NULL;
if（root!
=NULL）
PreThread（root）;
pre=NULL;
status=preThreaded;
}
}
template
voidBiThrTree:
:
PreThread（BiThrNode*node）{
if（node==NULL）
return;
BiThrNode*te=pre;
pre=node;
PreThread（node->lchild）;
PreThread（node->rchild）;
if（node->lchild==NULL）{
node->ltag=true;
node->lchild=te;
}
if（te!
=NULL&&te->rchild==NULL）{
te->rtag=true;
te->rchild=node;
}
}
template
voidBiThrTree:
:
MidThread（）{
if（status==notThreaded）{
BiThrNode*te;
te=root;
pre=NULL;
if（te==NULL）
return;
MidThread（te）;
pre=NULL;
status=midThreaded;
}
elsecout<<"thistreeisthreaded/n";
}
template
voidBiThrTree:
:
MidThread（BiThrNode*node）{
if（node==NULL）
return;
MidThread（node->lchild）;
BiThrNode*te=pre;
pre=node;
if（node->lchild==NULL）{
node->ltag=true;
node->lchild=te;
}
if（te!
=NULL&&te->rchild==NULL）{
te->rtag=true;
te->rchild=node;
}
MidThread（node->rchild）;
}
template
voidBiThrTree:
:
PostThread（）{
if（status==notThreaded）{
BiThrNode*te=root;
pre=NULL;
if（te==NULL）
return;
/*while（te->lchild!
=NULL）{
te=te->lchild;
}*/
PostThread（te）;
pre=NULL;
status=postThreaded;
}
}
template
voidBiThrTree:
:
PostThread（BiThrNode*node）{
if（node==NULL）
return;
PostThread（node->lchild）;
PostThread（node->rchild）;
if（node->lchild==NULL）{
node->ltag=true;
node->lchild=pre;
}
if（pre!
=NULL&&pre->rchild==NULL）{
pre->rtag=true;
pre->rchild=node;
}
pre=node;
}
template
voidBiThrTree:
:
InsertAtL（Element_typedata）{
BiThrNode*node=newBiThrNode;
BiThrNode*end,*te,*pre;
node->data=data;
node->lchild=NULL;
node->rchild=NULL;
node->ltag=false;
node->rtag=false;
if（root->rtag）
end=NULL;
elseend=root->rchild;
pre=root;
te=PreSuc（pre）;
while（te!
=end）{
pre=te;
te=PreSuc（te）;
}
pre->rtag=false;
pre->rchild=node;
node->ltag=true;
node->lchild=pre;
node->rtag=true;
node->rchild=end;
}
template
voidBiThrTree:
:
Clear（）{
if（status==notThreaded）{
Clear（root）;
root=NULL;
}
else{
BiThrNode*node,*te;
node=root;
while（node!
=NULL）{
te=node;
switch（status）{
casepreThreaded:
node=PreSuc（node）;
break;
casemidThreaded:
node=MidSuc（node）;
break;
casepostThreaded:
node=PostUsher（node）;
break;
default:
return;
}
delete（te）;
}
}
}
template
voidBiThrTree:
:
Clear（BiThrNode*node）{
if（node==NULL）
return;
Clear（node->lchild）;
node->lchild=NULL;
Clear（node->rchild）;
node->rchild=NULL;
deletenode;
}
template
voidBiThrTree:
:
Visit（BiThrNode*node）{
cout<data<<"";
}
template
voidBiThrTree:
:
CreatNode（BiThrNode*node）{
Element_typedata;
intlchild,rchild;
BiThrNode*te;
file>>lchild>>rchild;
if（lchild==0）{
file>>data;
node->lchild=newBiThrNode;
te=node->lchild;
te->data=data;
te->lchild=NULL;
te->rchild=NULL;
te->ltag=false;
te->rtag=false;
CreatNode（te）;
}
if（rchild==0）{
file>>data;
node->rchild=newBiThrNode;
te=node->rchild;
te->data=data;
te->lchild=NULL;
te->rchild=NULL;
te->ltag=false;
te->rtag=false;
CreatNode（te）;
}
}
voidpart1（constchar*file）{
cout<<"树"<BiThrTreetree（file）;
cout<<"树的先序遍历:
\n";
tree.PreOrder（）;
cout<<"\n\n";
}
voidpart2（constchar*file）{
cout<<"树"<BiThrTreetree（file）;
cout<<"树的中序遍历:
\n";
tree.MidOrder（）;
cout<<"\n\n";
}
voidpart3（constchar*file）{
cout<<"树"<BiThrTreetree（file）;
cout<<"树的后序遍历:
\n";
tree.PostOrder（）;
cout<<"\n\n";
}
voidpart4（constchar*file）{
cout<<"树"<BiThrTreetree（file）;
cout<<"先序遍历最初的树\n";
tree.PreOrder（）;
cout<cout<<"插入结点X:
\n";
tree.InsertAtL（'X'）;
cout<<"结果（先序遍历）:
\n";
tree.PreOrder（）;
cout<<"\n\n";
}
intmain（）{
part1（"FULL41.CBT"）;
part1（"LETTER.CBT"）;
cout<<"\n\n";
part2（"FULL41.CBT"）;
part2（"LETTER.CBT"）;
cout<<"\n\n";
part3（"FULL41.CBT"）;
part3（"LETTER.CBT"）;
cout<<"\n\n";
part4（"FULL41.CBT"）;
part4（"LETTER.CBT"）;
cout<<"\n\n";
system（"pause"）;
return0;
}
六、完整的实验结果记录∶
（为了方便，将此次试验重新分为四个部分）
<1>先序线索化二叉树，再先序遍历二叉树
预期结果：
Full41.cbt:
ABCDEFGHIJKLMN
Letter.cbt:
abcdefghijklmnopqrstuvwxyz
<2>中序线索化二叉树，再中序遍历二叉树
预期结果：
FULL41.CBT：
DCEBGFHAKJLINMO
LETTER.CBT：
dfgeihjclkmbonpartsuqwxvyz
<3>后序线索化二叉树，再后序遍历二叉树
预期结果：
FULL41.CBT：
DECGHFBKLJNOM
LETTER.CBT：
gfijhedlmkcopnbtusrxwzyvqa
<4>将值为x的结点作为先序线索二叉树T的左子树的（先序）最后一个结点的右孩子插入进去。
预期结果：
FULL41.CBT：
ABCDEFGHXIJKLMNO
LETTER.CBT：
abcdefghijklmnopXqrstuvwxyz
升级会员 