鱼C论坛

 找回密码
 立即注册
查看: 4537|回复: 6

数据结构 线索二叉树 小甲鱼代码有个地方不明白

[复制链接]
发表于 2014-3-31 13:07:14 | 显示全部楼层 |阅读模式
5鱼币
本帖最后由 洛熙封晨 于 2014-3-31 13:08 编辑

这是小甲鱼视频里面给的源代码,代码里面有3行不是很明白,用红色标出了,请大神讲解下

#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("中序遍历输出结果为: ");

        InOrderTraverse( P );

        printf("\n");

        return 0;
}



如题,代码中红色的3行不是很明白,求大神讲解这几行代码的作用

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

使用道具 举报

发表于 2014-4-1 12:28:47 | 显示全部楼层
  1. (*p)->lchild = T; //p是指针的指针
  2.                 pre = *p; //pre是指针
  3.                 InThreading(T); //调用这个函数,你注释的是中序遍历线索化
  4.                 pre->rchild = *p; //做孩子赋值为一个指针。。。*p
  5.                 pre->rtag = Thread; //rtag 标记为Thread
  6.                 (*p)->rchild = pre;//*p的右孩子为pre.......
复制代码
这个不是数据结构的视频么。。。。反正大概原理懂了就行。。。基本上不用。。用的时候。。在百度。。copy。。。然后。。就是那样。。。。相信我。。。
ps; 有什么说错的。。请见谅
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-5-15 10:56:10 | 显示全部楼层
看了下,我也不明白,呵呵
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-5-25 20:16:05 | 显示全部楼层
(*p)->lchild = T; //p是指针的指针
                pre = *p; //pre是指针
                InThreading(T); //调用这个函数,你注释的是中序遍历线索化
                pre->rchild = *p; //做孩子赋值为一个指针。。。*p
                pre->rtag = Thread; //rtag 标记为Thread
                (*p)->rchild = pre;//*p的右孩子为pre.......
给你个解释吧!希望你能明白,首先你得知道*p(注意这里是个二级指针,蛋疼的很)表示什么,它表示我们第一次创建的pre,就是用malloc动态分配了个堆给他,然后*p指向这个新分配的内存,第一点你要明白的是*p它只是赋值给pre,在整个函数期间这个*p一直没变,始终指向那个新分配的内存,第二点,pre =* p;就是把pre的值指向了新分配的内存,而这个pre在函数InThreading(T)被修改,在函数InThreading(T)调用完后,pre指向了树最右边的最后一个节点了。而这时*p还是指向新分配的内存。 pre->rchild = *p,这句表示把树右边的最后一个节点右孩子指向那个新分配的内存(节点),当然还要把最后这个节点的rtag标志改为线索化。最后指向新内存的(*P)的右孩子就要指向树的最后那个节点,这样就形成了一个回路,有点类似循环链表,我已经说得很详细了。:lol:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-5-28 00:25:36 | 显示全部楼层
立夏表示即将告别春天,夏天开始。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-17 14:48:40 | 显示全部楼层
                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild = pre;
这三行代码我的理解是将头结点和最后一个结点相互指向,连接起来,也就是向双向链表一样连接起来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-17 14:50:38 | 显示全部楼层
                pre->rchild = *p;
                pre->rtag = Thread;
                (*p)->rchild = pre;
这三行代码我的理解是将头结点和最后一个结点相互指向,连接起来,也就是向双向链表一样连接起来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 04:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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