前序线索二叉树前序线索二叉树
#include
#include #include
struct Tnode
{
char data;
struct Tnode *lchild;
struct Tnode *rchild;
bool lflag,rflag;
};
struct Tnode *head,*pre; struct Tnode *root=0; char stack[100];
char A[100];
int top=-1;
void create(struct Tnode* &p,in...
前序线索二叉树
#include
#include #include
struct Tnode
{
char data;
struct Tnode *lchild;
struct Tnode *rchild;
bool lflag,rflag;
};
struct Tnode *head,*pre; struct Tnode *root=0; char stack[100];
char A[100];
int top=-1;
void create(struct Tnode* &p,int l,int r)
{
int i,j,k;
if(l>r)
{
return;
}
p=(struct Tnode*)malloc(sizeof(struct Tnode));
p->data=A[l];
p->lchild=0;
p->rchild=0;
if(l==r)return;
else
{
if(A[l+2]==',') {
create(p->rchild,l+3,r-1);
return;
}
else if(A[l+3]==',')
{
create(p->lchild,l+2,l+2);
create(p->rchild,l+4,r-1);
return;
}
else
{
stack[++top]='('; i=l+4;
while(top>=0)
{
if(A[i]=='(')
{
stack[++top]='(';
}
else if(A[i]==')')
{
top--;
}
i++;
}
create(p->lchild,l+2,i-1);
create(p->rchild,i+1,r-1);
}
}
}
void preorder_thread(struct Tnode *p)
{
if(p)
{
if(p->lchild==0)
{
p->lflag=1;
p->lchild=pre;
}
else p->lflag=0; if(pre->rchild==0)
{
pre->rflag=1;
pre->rchild=p; }
else p->rflag=0;
pre=p;
if(p->lflag==0) preorder_thread(p->lchild);
if(p->rflag==0) preorder_thread(p->rchild);
}
}
void makethread()
{
head=(struct Tnode*)malloc(sizeof(struct Tnode));
head->lflag=0;
head->lchild=root;
head->rflag=1;
head->rchild=head;
pre=head;
preorder_thread(root);
pre->rflag=1;
pre->rchild=head;
head->rflag=1;
head->rchild=pre;
}
void preorder_th(struct Tnode *p)
{
if(p)
{
printf("%c ",p->data);
while(p->rchild!=head)
{
if(p->lflag!=1) {
p=p->lchild;
printf("%c ",p->data);
}
else
{
p=p->rchild;
printf("%c ",p->data);
}
}
}
}
int main()
{
int i,j,k,n;
scanf("%s",A);
n=strlen(A);
create(root,0,n-1);
makethread();
preorder_th(root);
printf("\n");
system("pause");
}
本文档为【前序线索二叉树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483