构造中序线索二叉树，为什么最后只输出GMZ三个
#include <iostream>typedef struct ThreadNode{
char data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
ThreadTree PrelnCreat(char* in, char* pre, int n){
if(n == 0)
return NULL;
ThreadTree p = new ThreadNode;
p->data = *pre;
for(int i = 0;i < n; i++)
if(in == *pre)
break;
p->lchild = PrelnCreat(in, pre +1, i);
p->rchild = PrelnCreat(in + i + 1, pre + i + 1, n - (i + 1));
return p;
}
void InThread(ThreadTree &p,ThreadTree &pre){
if(p!=NULL){
InThread(p->lchild,pre) ; //递归，线索化左子树
if (p->lchild==NULL) { //左子树为空，建立前驱线索
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=p; //建立前驱结点的后继线索
pre->rtag=1;
}
pre=p;//标记当前结点成为刚刚访问过的结点
InThread(p->rchild,pre);//递归，线索化右子树
}//if(p!-NULL)
}
void CreatelnThread(ThreadTree T) {
ThreadTree pre=NULL;
if (T!=NULL) { //非空二叉树，线索化
InThread(T,pre); //线索化二叉树
pre->rchild=NULL;//处理遍历的最后一个结点
pre->rtag=1;
}
}
ThreadNode *Firstnode(ThreadNode *p){
while(p->ltag==0)
p=p->lchild;//最左下结点（不一定是叶结点〉
return p;
}
ThreadNode *Nextnode(ThreadNode *p){
if(p->rtag==0)
return Firstnode(p->rchild);
else
return p->rchild;//rtag==l 直接返回后继线索
}
void Inorder(ThreadNode *T) {
for(ThreadNode *p=Firstnode(T);p!=NULL; p=Nextnode(p))
printf("%c",p->data);
}
int main(){
char* pr="GDAFEMHZ";
char* in="ADEFGHMZ";
ThreadTree t=PrelnCreat(in,pr,8);
CreatelnThread(t);
Inorder(t);
//printf("%c",p->data);
//printf("%d",xiangsi(t,t1));
printf("\n");
return 0;
}
页:
[1]