论坛 › 数据结构与算法 › 新人线索二叉树部分代码

霜林尽染 发表于 2015-5-24 19:26:59

新人线索二叉树部分代码

#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;

}

在   InThreading函数中，假如 T节点指向G， 那它的 pre 指向 C 吗？ 如果指向CC没有右孩子，那 C 的 右孩子又指回 G 吗？

vank 发表于 2015-5-25 15:59:47

通俗易懂，强烈建议大家看看

酱油先生 发表于 2015-5-27 07:36:02

通俗易懂，强烈建议大家看看

此地无银 发表于 2015-5-27 13:37:32

你把C的右孩子没有的情况 当成 C的右孩子指向NULL，小甲鱼在视频里提到过。

对于你问题的描述，不是很理解。

EntU 发表于 2015-5-28 00:47:31

支持楼主！德玛西亚！

溯月0503 发表于 2015-5-28 09:26:33

:sad

逆战时代 发表于 2015-5-28 16:02:57

支持下。。。。。。。。

蓝色枫叶 发表于 2015-5-28 20:02:22

假如 T节点指向G
pre指向C，C没有右孩子，pre->rchild=G,pre=G
pre指向G，G->rchild==NULL,   InThreading(G->rchild)，所以G的线索已经完成了
然后又回到头结点

霜林尽染 发表于 2015-5-29 23:26:21

蓝色枫叶 发表于 2015-5-28 20:02
假如 T节点指向G
pre指向C，C没有右孩子，pre->rchild=G,pre=G
pre指向G，G->rchild==NULL,   InThreadin ...

谢谢，非常感谢

deyuanzhao 发表于 2015-6-1 13:59:47

学海无涯贵在坚持

lizishu 发表于 2017-12-22 15:53:41

支持下

查看完整版本: 新人线索二叉树部分代码