注册 登录
编程论坛 C语言论坛

线索化二叉树出现问题

楚川杉 发布于 2020-11-03 17:11, 1192 次点击

请问哪位大佬可以看一看这个程序,希望大佬能够帮我指正提出意见
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);
        
    }
   
   
}
1 回复
#2
楚川杉2020-11-03 17:12
debug了好久没找出来
1