Home Article Practice 二叉树

二叉树

2023-11-14 22:27  views:468  source:小键人丸子头    

#include<iostream>
using namespace std;
typedef char TElemType;
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrNode *pre=new BiThrNode;
void InThreading(BiThrTree p)
{
if(p){
InThreading(p->lchild);
if(!p->lchild){
p->LTag=1;
p->lchild=pre;
}
else p->LTag=0;
if(!pre->rchild)
{
pre->RTag=1;
pre->rchild=p;
}
else pre->RTag=0;
pre=p;
InThreading(p->rchild);
}
}
void InOrderThreading(BiThrTree &Thrt,BiThrTree T){
Thrt=new BiThrNode;
Thrt->LTag=0;
Thrt->RTag=1;
Thrt->rchild=Thrt;
if(!T) Thrt->lchild=Thrt;
else{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);
pre->rchild=Thrt;
pre->RTag=1;
Thrt->rchild=pre;
}
}
void CreateBiTree(BiThrTree &T)
{
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InOrderTraverse_Thr(BiThrTree T){
BiThrNode *p;
p=T->lchild;
while(p!=T)
{
while(p->LTag==0) p=p->lchild;
cout<<p->data;
while (p->RTag==1&&p->rchild!=T)
{
p=p->rchild;
cout<<p->data;
}
p=p->rchild;
}
}
void main()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree,Thrt;
cout<<"请输入建立二叉链表的序列:\n";
CreateBiTree(tree);
InOrderThreading(Thrt,tree);
cout<<"中序遍历线索二叉树的结果为:\n";
InOrderTraverse_Thr(Thrt);
cout<<endl;
}



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)