构造中序线索二叉树，为什么最后只输出GMZ三个

d173220523

[C] 纯文本查看 复制代码

#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[i] == *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;
}