鱼C论坛

 找回密码
 立即注册
查看: 4892|回复: 5

线索二叉树里不明白的地方!

[复制链接]
发表于 2017-4-21 21:31:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
下面的程序已经跟踪过,想请教大神InOrderThreading()函数中else功能中为什么要进行pre->rchild = *p?如果说是将最后的结点地址赋给pre->rchild,为什么*p的地址并没有变化?程序已经跟踪过,大神指教!
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

// 线索存储标志位
// Link(0):表示指向左右孩子的指针
// Thread(1):表示指向前驱后继的线索
typedef enum {Link, Thread} PointerTag;

typedef struct BiThrNode
{
        char data;
        struct BiThrNode *lchild, *rchild;
        PointerTag ltag;
        PointerTag rtag;
} BiThrNode, *BiThrTree;

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

// 创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
void CreateBiThrTree( BiThrTree *T )
{
        char 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);
        }
}

// 中序遍历线索化
void InThreading(BiThrTree 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( BiThrTree *p, BiThrTree T )
{
        *p = (BiThrTree)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( char c )
{
        printf("%c", c);
}

// 中序遍历二叉树,非递归
void InOrderTraverse( BiThrTree T )
{
        BiThrTree 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;
        }
}

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

        CreateBiThrTree( &T );

        InOrderThreading( &p, T );

        printf("the result: \n");

        InOrderTraverse( p );

        printf("\n");

        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-22 20:43:04 | 显示全部楼层
我怎么感觉你没有跟踪过
因为我在你的代码CreateBiThrTree就陷入一个无线递归,没有任何返回条件
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-23 18:13:29 | 显示全部楼层
lumber2388779 发表于 2017-4-22 20:43
我怎么感觉你没有跟踪过
因为我在你的代码CreateBiThrTree就陷入一个无线递归,没有任何返回条件

额~~这个是小甲鱼的源代码~~我就是想请教一下*p在经历了线索遍历二叉树之后为什么值没有变???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-23 18:24:24 | 显示全部楼层
pokerlee 发表于 2017-4-23 18:13
额~~这个是小甲鱼的源代码~~我就是想请教一下*p在经历了线索遍历二叉树之后为什么值没有变???

感觉你不明白那块我是觉得有问题,因为我看了下好像没有起到该有的作用
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-17 12:09:09 | 显示全部楼层

下面的程序已经跟踪过,想请教大神InOrderThreading()函数中else功能中为什么要进行pre->rchild = *p?如果说是将最后的结点地址赋给pre->rchild,为什么*p的地址并没有变化?程序已经跟踪过,大神指教!
p的数值为啥会变啊,
void InOrderThreading( BiThrTree *p, BiThrTree T )
{
        *p = (BiThrTree)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;
        }
}
这段代码中没有对p进行改变啊,只是将p赋值给pre,然后pre发生了改变到了最后一个结点那,然后将首尾连接而已

                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild = pre;
这三句代码只是将双方互指而已
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-2-17 12:09:55 | 显示全部楼层
Code_mzh 发表于 2018-2-17 12:09
下面的程序已经跟踪过,想请教大神InOrderThreading()函数中else功能中为什么要进行pre->rchild = *p?如 ...

所以p的地址是始终不变的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-24 00:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表