论坛 › 数据结构与算法 › 线索二叉树的代码 大佬看看哪里有问题 运行之后不停地输出

春江水暖鸭好吃 发表于 2020-3-28 16:50:43

线索二叉树的代码 大佬看看哪里有问题 运行之后不停地输出

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

typedef char ElemType;

typedef enum {Link,Thread} PointTag;

//线索二叉树定义
typedef struct BiThrNode
{
      ElemType data;
      struct BiThrNode *lchild,*rchild;
      PointTag ltag;
      PointTag rtag;
}BiThrNode , *BiThrTree;

//递归创建二叉树
CreateBiThrTree( BiThrTree *T)
{
      ElemType c;
      scanf("%c",&c);
      
      if(' ' == c)
      {
                *T = NULL;
      }
      else
      {
                *T = (BiThrNode *)malloc(sizeof(BiThrNode));
                (*T)->data= c;
                (*T)->ltag = Link;
                (*T)->rtag = Link;
               
                CreateBiThrTree( &(*T)->lchild);
                CreateBiThrTree( &(*T)->rchild);
      }
}

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

//二叉树的中序遍历线索化
void InThreading(BiThrTree T)
{
      if(T)
      {
                InThreading(T->lchild);

                if(!T->lchild)
                {
                        T->ltag = Thread;
                        T->lchild = pre;
                }

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

                pre = T;

                InThreading(T->rchild);
      }
}


void InOrderThreading(BiThrTree *p,BiThrTree T)
{
      *p = (BiThrNode *)malloc(sizeof(BiThrNode));
      (*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(ElemType c)
{
      printf("%c",c);
}

void InOrderTraverse(BiThrTree T)
{
      BiThrTree p;
      p = T->lchild;
      while(p != T)
      {
                while(p->rtag == Link)
                {
                        p = p->lchild;
                }
                visit(p->data);


                while((p->rtag == Thread) && (p->rchild != T))
                {
                        p = p->rchild;
                        visit(p->data);
                }
                p = p->rchild;
      }
}

int main()
{
      BiThrTree P,T = NULL;

      CreateBiThrTree( &T );

      InOrderThreading( &P,T );

      InOrderTraverse( P );

      return 0;
}

yoke. 发表于 2021-2-10 11:21:49

InOrderTraverse函数中的第二个while的条件的rtag改成ltag

查看完整版本: 线索二叉树的代码 大佬看看哪里有问题 运行之后不停地输出