标题:线索化二叉树出现问题
只看楼主
楚川杉
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2020-3-10
结帖率:66.67%
 问题点数:0 回复次数:1 
线索化二叉树出现问题

请问哪位大佬可以看一看这个程序,希望大佬能够帮我指正提出意见
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);
        
    }
    
    
} 
搜索更多相关主题的帖子: 节点 二叉树 NULL 线索 void 
2020-11-03 17:11
楚川杉
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2020-3-10
得分:0 
debug了好久没找出来
2020-11-03 17:12



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-503745-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.171210 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved