线索二叉树代码实现,数据结构与算法,技术交流,鱼C论坛

宝宝吃肉 发表于 2013-8-15 15:13:21

线索二叉树代码实现

本帖最后由宝宝吃肉于 2013-8-16 00:45 编辑

跟着小甲鱼敲代码验证了好几次完全是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_小春 发表于 2013-8-15 15:13:22

楼主，我今晚再把你的代码改了一下，把类型换成了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;

}

宝宝吃肉 发表于 2013-8-15 15:14:17

lz在线等

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

你这样的求助没人看得懂，怪不得没人回复你{:5_105:}

宝宝吃肉 发表于 2013-8-16 00:30:03

a2636161388 发表于 2013-8-15 16:33 static/image/common/back.gif
你这样的求助没人看得懂，怪不得没人回复你

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

宝宝吃肉 发表于 2013-8-17 20:47:55

求助啊

zZ_小春 发表于 2013-8-19 11:03:24

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

}

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

zZ_小春发表于 2013-8-25 21:40 static/image/common/back.gif
楼主，我今晚再把你的代码改了一下，把类型换成了int型的，因为char型的比较相同那里应该就有问题的，还有我 ...

谢谢

zZ_小春 发表于 2013-8-27 22:24:28

宝宝吃肉发表于 2013-8-27 09:37 static/image/common/back.gif
谢谢

不客气{:5_109:}

笑龙传说 发表于 2013-11-17 19:56:33

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

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

笑龙传说 发表于 2013-11-17 19:58:49

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

zch463170098 发表于 2013-12-3 20:58:47

zZ_小春发表于 2013-8-15 15:13 static/image/common/back.gif
楼主，我今晚再把你的代码改了一下，把类型换成了int型的，因为char型的比较相同那里应该就有问题的，还有我 ...

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

昵称Jin 发表于 2013-12-16 14:17:59

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

霜林尽染 发表于 2015-5-23 13:11:07

路过看看

vanentu 发表于 2015-5-23 22:31:02

:shock:

喵小乐cherry 发表于 2015-5-26 22:19:23

:lol:

EntU 发表于 2015-5-28 00:48:36

支持楼主！德玛西亚！

溯月0503 发表于 2015-5-28 09:25:57

:sad

页: [1]

鱼C论坛's Archiver

线索二叉树代码实现