线索化二叉树出现问题
请问哪位大佬可以看一看这个程序,希望大佬能够帮我指正提出意见
BThrTree creatBTree(BThrTree p)通过前序遍历创建二叉树
void inOrderThread(BThrTree p)用中序遍历创建线索二叉树
BThrTree findNext(BThrTree p)为查找某个节点的后继
void displayThrBTree(BThrTree p)遍历创建的中序线索结果
AB#C##DE##FG#H##I##为测试数据
按理应输出BCAEDGHFI
但输入数据后没有任何反应
程序代码:
#include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct BNode { datatype data; int ltag;//1为前驱,0为左孩子 int rtag;//1为后继,0为右孩子 struct BNode *lchild; struct BNode *rchild; }BThrNode,*BThrTree; BThrTree creatBTree(BThrTree p); void inOrderThread(BThrTree p); BThrTree findNext(BThrTree p); void displayThrBTree(BThrTree p); void main(){ BThrTree btree =creatBTree(btree); inOrderThread(btree); displayThrBTree(btree); } //不创建空指针的情况 //通过前序创建二叉树 BThrTree creatBTree(BThrTree p){ //AB#C##DE##FG#H##I## datatype value; scanf("%c",&value); if(value=='#'){ p=NULL; } else{ p=(BThrTree)malloc(sizeof(BThrNode)); p->data=value; p->ltag=0; p->rtag=0; p->lchild=creatBTree(p->lchild); p->rchild=creatBTree(p->rchild); } return p; } //利用中序遍历线索化 void inOrderThread(BThrTree p){ static BThrTree pre=NULL; if(p==NULL){ return ; } //左子树线索化 inOrderThread(p->lchild); //线索化处理 if(p->lchild==NULL){ p->lchild=pre; p->ltag=1; } if(pre->rchild==NULL&&pre!=NULL){ pre->rchild=p; pre->rtag=1; } pre=p; //右子树线索化 inOrderThread(p->rchild); } //查找节点的后继 BThrTree findNext(BThrTree p){ if(p->rtag==1){ return p->rchild; } else{ BThrTree temp=(BThrTree)malloc(sizeof(BThrNode)); temp=p->rchild; while(temp->ltag==0){ temp=temp->lchild; } return temp; } } //遍历输出线索树 void displayThrBTree(BThrTree p){ if(p==NULL){ return; } //找到遍历的开始节点 BThrTree root; root=p;//获取根节点 while(root->ltag==0){//对于线索二叉树只有最左下角的节点的左孩子是空 ,其余左孩子都有前继或左孩子 root=root->lchild; } printf("%d",root->data); //访问第一个节点 while(root->rchild!=NULL){//线索树中的最后一节点的右孩子为空 root=findNext(root);//获取后继节点 printf("%d",root->data); } }