线索二叉树实验Word下载.docx
《线索二叉树实验Word下载.docx》由会员分享，可在线阅读，更多相关《线索二叉树实验Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
preThreaded,
midThreaded,
postThreaded};
template<
classElement_type>
structBiThrNode{
Element_typedata;
BiThrNode*lchild,*rchild;
boolltag,rtag;
};
classBiThrTree{
public:
BiThrTree（）;
BiThrTree（constchar*filename）;
//根据文件构造二叉树
~BiThrTree（）;
//析构函数
voidBuild（constchar*filename）;
//根据文件创建二叉树
voidPreOrder（）;
//先序遍历二叉树
voidMidOrder（）;
//中序遍历二叉树
voidPostOrder（）;
//后序遍历二叉树
BiThrNode<
Element_type>
*PreSuc（BiThrNode<
*node）const;
//先序后继
*MidSuc（BiThrNode<
//中序后继
*PostUsher（BiThrNode<
//后序前驱
voidPostPrint（）;
//输出后序遍历二叉树
voidPostPrint（BiThrNode<
*node）;
voidPreThread（）;
//先序线索化
voidPreThread（BiThrNode<
*node）;
voidMidThread（）;
//中序线索化
voidMidThread（BiThrNode<
voidPostThread（）;
//后序线索化
voidPostThread（BiThrNode<
voidInsertAtL（Element_typedata）;
//插入为左子树先序最后一个结点的右孩子
voidClear（）;
//删除二叉树
voidClear（BiThrNode<
voidVisit（BiThrNode<
//访问结点
private:
voidCreatNode（BiThrNode<
*root;
ifstreamfile;
Threadstatus;
*pre;
BiThrTree<
:
:
BiThrTree（）{
root=NULL;
status=notThreaded;
}
BiThrTree（constchar*filename）{
Build（filename）;
~BiThrTree（）{
Clear（）;
voidBiThrTree<
Build（constchar*filename）{
if（root!
=NULL）
chartree[40];
intchild;
file.open（filename）;
file>
>
tree>
child;
if（child==0）{
file>
data;
root=newBiThrNode<
;
root->
data=data;
lchild=NULL;
rchild=NULL;
ltag=false;
rtag=false;
CreatNode（root）;
}
elseroot=NULL;
PreOrder（）{
if（status==notThreaded）
PreThread（）;
*te=root;
while（te!
=NULL）{
Visit（te）;
te=PreSuc（te）;
MidOrder（）{
MidThread（）;
if（te==NULL）
return;
while（te->
lchild!
=NULL）
te=te->
lchild;
te=MidSuc（te）;
voidBiThrTree<
PostOrder（）{
if（status==notThreaded）{
PostThread（）;
PostPrint（）;
BiThrNode<
*BiThrTree<
PreSuc（BiThrNode<
*node）const{
if（!
node->
ltag）
returnnode->
elsereturnnode->
rchild;
MidSuc（BiThrNode<
if（node->
rtag）
returnnode->
*te=node->
returnte;
while（!
te->
ltag）
returnte;
PostUsher（BiThrNode<
*node）const{
rtag）
returnnode->
else
PostPrint（）{
PostPrint（root）;
PostPrint（BiThrNode<
*node）{
if（node==NULL）
return;
PostPrint（PostUsher（node））;
cout<
data<
"
"
;
PreThread（）{
if（status==notThreaded）{
pre=NULL;
if（root!
PreThread（root）;
status=preThreaded;
PreThread（BiThrNode<
*node）{
*te=pre;
pre=node;
PreThread（node->
lchild）;
rchild）;
if（node->
lchild==NULL）{
node->
ltag=true;
lchild=te;
if（te!
=NULL&
&
rchild==NULL）{
te->
rtag=true;
rchild=node;
MidThread（）{
*te;
te=root;
pre=NULL;
if（te==NULL）
return;
MidThread（te）;
status=midThreaded;
elsecout<
thistreeisthreaded/n"
MidThread（BiThrNode<
MidThread（node->
PostThread（）{
if（te==NULL）
/*while（te->
lchild!
te=te->
}*/
PostThread（te）;
status=postThreaded;
PostThread（BiThrNode<
if（node==NULL）
PostThread（node->
if（node->
lchild==NULL）{
node->
lchild=pre;
if（pre!
=NULL&
pre->
rchild==NULL）{
pre->
InsertAtL（Element_typedata）{
*node=newBiThrNode<
*end,*te,*pre;
if（root->
end=NULL;
elseend=root->
pre=root;
te=PreSuc（pre）;
while（te!
=end）{
pre=te;
te=PreSuc（te）;
rchild=end;
Clear（）{
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）;
casepostThreaded:
node=PostUsher（node）;
default:
return;
}
delete（te）;
}
Clear（BiThrNode<
if（node==NULL）
Clear（node->
lchild）;
rchild）;
rchild=NULL;
deletenode;
Visit（BiThrNode<
CreatNode（BiThrNode<
intlchild,rchild;
lchild>
if（lchild==0）{
lchild=newBiThrNode<
te=node->
te->
CreatNode（te）;
if（rchild==0）{
rchild=newBiThrNode<
voidpart1（constchar*file）{
树"
file<
\n"
BiThrTree<
char>
tree（file）;
树的先序遍历:
tree.PreOrder（）;
\n\n"
voidpart2（constchar*file）{
树的中序遍历:
tree.MidOrder（）;
voidpart3（constchar*file）{
树的后序遍历:
tree.PostOrder（）;
voidpart4（constchar*file）{
先序遍历最初的树\n"
endl;
插入结点X:
tree.InsertAtL（'
X'
）;
结果（先序遍历）:
intmain（）{
part1（"
FULL41.CBT"
LETTER.CBT"
part2（"
part3（"
part4（"
system（"
pause"
return0;
六、完整的实验结果记录∶
（为了方便，将此次试验重新分为四个部分）
先序线索化二叉树，再先序遍历二叉树
预期结果：
Full41.cbt:
ABCDEFGHIJKLMN
Letter.cbt:
abcdefghijklmnopqrstuvwxyz
中序线索化二叉树，再中序遍历二叉树
FULL41.CBT：
DCEBGFHAKJLINMO
LETTER.CBT：
dfgeihjclkmbonpartsuqwxvyz
后序线索化二叉树，再后序遍历二叉树
DECGHFBKLJNOM
gfijhedlmkcopnbtusrxwzyvqa
ABCDEFGHXIJKLMNO
abcdefghijklmnopXqrstuvwxyz
升级会员 