线索二叉树代码实现

宝宝吃肉

跟着小甲鱼敲代码 验证了好几次 完全是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型的比较相同那里应该就有问题的，还有我上次改的那些，就可以得到想要的结果了，具体代码如下

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. 
   
5. typedef int ElemType;
   
6. 
   
7. typedef enum{Link,Thread} PointerTag;
   
8. 
   
9. // 线索存储标志位
   
10. //Link（0）：表示指向左右孩子的指针
    
11. //Thread（1）：表示指向前去后继的线索
    
12. 
    
13. typedef struct BinThrNode
    
14. {
    
15.     int data;
    
16.         struct BinThrNode *lchild,*rchild;
    
17.         PointerTag ltag;
    
18.         PointerTag rtag;
    
19. }BinThrNode,*BinThrtree;
    
20. 
    
21. //全局变量，始终指向刚刚访问过的节点
    
22. BinThrNode *pre;
    
23. 
    
24. 
    
25. void CreateBinThrtree(BinThrNode **T)
    
26. {
    
27.         int c;
    
28. 
    
29.         scanf("%d",&c);
    
30.         if(0== c )
    
31.         {
    
32.             *T = NULL;
    
33.         }
    
34.         else
    
35.         {
    
36.             *T =(BinThrNode *)malloc(sizeof(BinThrNode));
    
37.                         (*T)->data = c;
    
38.                 (*T)->ltag = Link;
    
39.                 (*T)->rtag = Link;
    
40. 
    
41.                 CreateBinThrtree(&(*T)->lchild);
    
42.        CreateBinThrtree(&(*T)->rchild);
    
43.         }
    
44. }
    
45. 
    
46. void InThreading(BinThrNode *T)
    
47. {
    
48.     if(T)
    
49.         {
    
50.             InThreading(T->lchild);//递归左孩子线索化
    
51.         if(!T->lchild)          //如果该节点没有左孩子，设置ltag为Thread，并把lchild指向上一个访问的节点
    
52.                 {
    
53.                     T->ltag = Thread;
    
54.                         T->lchild = pre;
    
55.                 }
    
56. 
    
57.                 if(!pre->rchild)
    
58.                 {
    
59.                     pre->rtag = Thread;
    
60.                         pre->rchild = T;
    
61.                 }
    
62. 
    
63.         pre = T;
    
64. 
    
65.                 InThreading(T->rchild);
    
66.         }
    
67. }
    
68. 
    
69. void InOrderThreading(BinThrNode **p,BinThrNode *T)
    
70. {
    
71.     *p = (BinThrNode *)malloc(sizeof(BinThrNode));
    
72.         (*p)->ltag = Link;
    
73.         (*p)->rtag = Thread;
    
74.         (*p)->rchild = *p;
    
75.         if(!T)
    
76.         {
    
77.             (*p)->lchild = *p;
    
78.         }
    
79.         else
    
80.         {
    
81.             (*p)->lchild = T;
    
82.                 pre = *p;
    
83. 
    
84.                 InThreading(T);
    
85.                 pre->rchild = *p;
    
86.                 pre->rtag = Thread;
    
87.                 (*p)->rchild =pre;
    
88.         }
    
89. }
    
90. //中序遍历二叉树，非递归
    
91. 
    
92. void visit(int c)
    
93. {
    
94.     printf("%d",c);
    
95. }
    
96. 
    
97. void InOrderTraverse(BinThrNode *T)
    
98. {
    
99.     BinThrNode *p;
    
100.         p = T->lchild;
     
101. 
     
102.         while(p != T)
     
103.         {
     
104.             while (p->ltag == Link)
     
105.                 {
     
106.                     p = p->lchild;
     
107.                 }
     
108.                 visit(p->data);
     
109. 
     
110.                 while(p->rtag == Thread && p->rchild!=T)
     
111.                 {
     
112.                     p = p->rchild;
     
113.                         visit(p->data);
     
114.                 }
     
115.                 p = p->rchild;
     
116.         }
     
117. }
     
118. // P头指针 T头节点
     
119. int main()
     
120. {
     
121.         BinThrNode *P,*T = NULL;
     
122. 
     
123.          CreateBinThrtree(&T);
     
124. 
     
125.         InOrderThreading(&P,T);
     
126. 
     
127.         printf("中序遍历输出：\n");
     
128. 
     
129.         InOrderTraverse( P );
     
130.         printf("\n");
     
131.     return 0;
     
132. 
     
133. }

复制代码

宝宝吃肉

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