线索二叉树代码实现

宝宝吃肉

跟着小甲鱼敲代码 验证了好几次 完全是copy类型的 可是错误百出 求大神帮忙 积攒了n多天的5个鱼币奉上  求不吝赐教
代码如下
#include<stdio.h>
#include<stdlib.h>


typedef char ElemType;

typedef enum{Link,Thread} PointerTag;

// 线索存储标志位
//Link（0）：表示指向左右孩子的指针
//Thread（1）：表示指向前去后继的线索

typedef struct BinThrNode
{
    char data;
        struct BinThrNode *lchild,*rchild;
        PointerTag ltag;
        PointerTag rtag;
}BinThrNode,*BinThrtree;

//全局变量，始终指向刚刚访问过的节点
BinThrTree pre;


void CreateBinThrtree(BinThrTree *T)
{
        char c;

        scanf("%c",&c);
        if(' '== c )
        {
            *T = NULL;
        }
        else
        {
            *T =(BinThrNode *)malloc(sizeof(BinThrNode));
        (*T)->data = c;
                (*T)->ltag = Link;
                (*T)->rtag = Link;

                CreateBinTree(&(*T)->lchild);
        CreateBinTree(&(*T)->rchild);
        }
}

void InThreading(BinThrTree T)
{
    if(T)
        {
            InThreading(T->lchild);//递归左孩子线索化
        if(!T->lchild)          //如果该节点没有左孩子，设置ltag为Thread，并把lchild指向上一个访问的节点
                {
                    T->ltag = Thread;
                        T->lchild = pre;
                }

                if(!pre->rchild)
                {
                    pre->rtag = Thread;
                        pre->rchild = T;
                }

        pre = T;

                InThreading(T->rchild);
        }
}

void InOrderThreading(BinThrTree *p,BinThrTree T)
{
    *p = (BinThrtree)malloc(sizeof(BinThrNode));
        (*p)->ltag = Link;
        (*p)->rtag = Thread;
        (*p)->rchild = *p;
        if(!T)
        {
            (*p)->lchild = *p;
        }
        else
        {
            (*p)->lchild = T;
                pre = *p;

                InThreading(T);
                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild =pre;
        }
}
//中序遍历二叉树，非递归

void visit(char c)
{
    printf("%c",c);
}

void InOrderTraverse(BinThrTree T)
{
    BinThrTree p;
        p = T->lchild;

        while(p != T)
        {
            while (p->ltag == Link)
                {
                    p = p->lchild;
                }
                visit(p->data);

                while(p->rtag == Thread && p->rchild!=T)
                {
                    p = p->rchild;
                        visit(p->data);
                }
                p = p->rchild;
        }
}
// P头指针 T头节点
int main()
{
        BinThrTree P,T = NULL;

        CreateBinThrTree(&T);

        InOrderThreading(&P,T);

        printf("中序遍历输出：\n");

        InOrderTraverse( P )；
        printf("\n");
    return 0;

}

zZ_小春

楼主，我今晚再把你的代码改了一下，把类型换成了int型的，因为char型的比较相同那里应该就有问题的，还有我上次改的那些，就可以得到想要的结果了，具体代码如下

#include<stdio.h>
#include<stdlib.h>


typedef int ElemType;

typedef enum{Link,Thread} PointerTag;

// 线索存储标志位
//Link（0）：表示指向左右孩子的指针
//Thread（1）：表示指向前去后继的线索

typedef struct BinThrNode
{
    int data;
        struct BinThrNode *lchild,*rchild;
        PointerTag ltag;
        PointerTag rtag;
}BinThrNode,*BinThrtree;

//全局变量，始终指向刚刚访问过的节点
BinThrNode *pre;


void CreateBinThrtree(BinThrNode **T)
{
        int c;

        scanf("%d",&c);
        if(0== c )
        {
            *T = NULL;
        }
        else
        {
            *T =(BinThrNode *)malloc(sizeof(BinThrNode));
                        (*T)->data = c;
                (*T)->ltag = Link;
                (*T)->rtag = Link;

                CreateBinThrtree(&(*T)->lchild);
       CreateBinThrtree(&(*T)->rchild);
        }
}

void InThreading(BinThrNode *T)
{
    if(T)
        {
            InThreading(T->lchild);//递归左孩子线索化
        if(!T->lchild)          //如果该节点没有左孩子，设置ltag为Thread，并把lchild指向上一个访问的节点
                {
                    T->ltag = Thread;
                        T->lchild = pre;
                }

                if(!pre->rchild)
                {
                    pre->rtag = Thread;
                        pre->rchild = T;
                }

        pre = T;

                InThreading(T->rchild);
        }
}

void InOrderThreading(BinThrNode **p,BinThrNode *T)
{
    *p = (BinThrNode *)malloc(sizeof(BinThrNode));
        (*p)->ltag = Link;
        (*p)->rtag = Thread;
        (*p)->rchild = *p;
        if(!T)
        {
            (*p)->lchild = *p;
        }
        else
        {
            (*p)->lchild = T;
                pre = *p;

                InThreading(T);
                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild =pre;
        }
}
//中序遍历二叉树，非递归

void visit(int c)
{
    printf("%d",c);
}

void InOrderTraverse(BinThrNode *T)
{
    BinThrNode *p;
        p = T->lchild;

        while(p != T)
        {
            while (p->ltag == Link)
                {
                    p = p->lchild;
                }
                visit(p->data);

                while(p->rtag == Thread && p->rchild!=T)
                {
                    p = p->rchild;
                        visit(p->data);
                }
                p = p->rchild;
        }
}
// P头指针 T头节点
int main()
{
        BinThrNode *P,*T = NULL;

         CreateBinThrtree(&T);

        InOrderThreading(&P,T);

        printf("中序遍历输出：\n");

        InOrderTraverse( P );
        printf("\n");
    return 0;

}

宝宝吃肉

lz在线等     

a2636161388

你这样的求助没人看得懂，怪不得没人回复你

宝宝吃肉

a2636161388 发表于 2013-8-15 16:33

                               
登录/注册后可看大图

你这样的求助没人看得懂，怪不得没人回复你

第一次发帖，代码不全 次奥。

宝宝吃肉

求助啊                    

zZ_小春

//修改了各个函数的形参，还有一个小错误就是楼主的标点符号用了中文，最后还是不能出到楼主想要的结果，在创建二叉树的时候用的是递归，但是好像没有结束条件，自己能力有限，等着牛人出现，哈哈！！
#include<stdio.h>
#include<stdlib.h>


typedef char ElemType;

typedef enum{Link,Thread} PointerTag;

// 线索存储标志位
//Link（0）：表示指向左右孩子的指针
//Thread（1）：表示指向前去后继的线索

typedef struct BinThrNode
{
    char data;
        struct BinThrNode *lchild,*rchild;
        PointerTag ltag;
        PointerTag rtag;
}BinThrNode,*BinThrtree;

//全局变量，始终指向刚刚访问过的节点
BinThrNode *pre;


void CreateBinThrtree(BinThrNode **T)
{
        char c;

        scanf("%c",&c);
        if(' '== c )
        {
            *T = NULL;
        }
        else
        {
            *T =(BinThrNode *)malloc(sizeof(BinThrNode));
        (*T)->data = c;
                (*T)->ltag = Link;
                (*T)->rtag = Link;

                CreateBinThrtree(&(*T)->lchild);
       CreateBinThrtree(&(*T)->rchild);
        }
}

void InThreading(BinThrNode *T)
{
    if(T)
        {
            InThreading(T->lchild);//递归左孩子线索化
        if(!T->lchild)          //如果该节点没有左孩子，设置ltag为Thread，并把lchild指向上一个访问的节点
                {
                    T->ltag = Thread;
                        T->lchild = pre;
                }

                if(!pre->rchild)
                {
                    pre->rtag = Thread;
                        pre->rchild = T;
                }

        pre = T;

                InThreading(T->rchild);
        }
}

void InOrderThreading(BinThrNode **p,BinThrNode *T)
{
    *p = (BinThrNode *)malloc(sizeof(BinThrNode));
        (*p)->ltag = Link;
        (*p)->rtag = Thread;
        (*p)->rchild = *p;
        if(!T)
        {
            (*p)->lchild = *p;
        }
        else
        {
            (*p)->lchild = T;
                pre = *p;

                InThreading(T);
                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild =pre;
        }
}
//中序遍历二叉树，非递归

void visit(char c)
{
    printf("%c",c);
}

void InOrderTraverse(BinThrNode *T)
{
    BinThrNode *p;
        p = T->lchild;

        while(p != T)
        {
            while (p->ltag == Link)
                {
                    p = p->lchild;
                }
                visit(p->data);

                while(p->rtag == Thread && p->rchild!=T)
                {
                    p = p->rchild;
                        visit(p->data);
                }
                p = p->rchild;
        }
}
// P头指针 T头节点
int main()
{
        BinThrNode *P,*T = NULL;

         CreateBinThrtree(&T);

        InOrderThreading(&P,T);

        printf("中序遍历输出：\n");

        InOrderTraverse( P );
        printf("\n");
    return 0;

}

宝宝吃肉

zZ_小春 发表于 2013-8-25 21:40

                               
登录/注册后可看大图

楼主，我今晚再把你的代码改了一下，把类型换成了int型的，因为char型的比较相同那里应该就有问题的，还有我 ...

谢谢                  

zZ_小春

宝宝吃肉 发表于 2013-8-27 09:37

                               
登录/注册后可看大图

谢谢

不客气

笑龙传说

我认为这段代码中不用递归的时候，那段非递归的代码有问题，  
while(p->rtag == Thread && p->rchild!=T)
                {
                    p = p->rchild;
                        visit(p->data);
                }

初始化的时候，明明rtag都赋值为0了，什么时候编程的thread

笑龙传说

还有就是中序遍历时，为什么处理节点在中间，不在开始啊

zch463170098

zZ_小春 发表于 2013-8-15 15:13

                               
登录/注册后可看大图

楼主，我今晚再把你的代码改了一下，把类型换成了int型的，因为char型的比较相同那里应该就有问题的，还有我 ...

你这样的求助没人看得懂，怪不得没人回复你

昵称Jin

找资源的孩子总是穿梭游走在各个帖子与板块之间，见资源就下，见贴就顶，争取早日拿到灌水大师勋章。

霜林尽染

路过看看

vanentu

:shock:

喵小乐cherry

:lol:

EntU

支持楼主！德玛西亚！

溯月0503

:sad