[已解决]新人线索二叉树部分代码

霜林尽染

#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 吗？ 如果指向C  C没有右孩子，那 C 的 右孩子又指回 G 吗？

最佳答案

月排行榜 / 总排行榜

此地无银

2015-5-27 13:37:32

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

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

跳转到最佳答案楼层

vank

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

酱油先生

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

此地无银

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

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

EntU

支持楼主！德玛西亚！

溯月0503

:sad

逆战时代

支持下。。。。。。。。

蓝色枫叶

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

霜林尽染

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

谢谢，非常感谢

deyuanzhao

学海无涯  贵在坚持

lizishu

支持下