鱼C论坛

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

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

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

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

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

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

  3. typedef char ElemType;

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

  8. typedef struct BiThrNode
  9. {
  10.         char data;
  11.         struct BiThrNode *lchild, *rchild;
  12.         PointerTag ltag;
  13.         PointerTag rtag;
  14. } BiThrNode, *BiThrTree;

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

  17. // 创建一棵二叉树,约定用户遵照前序遍历的方式输入数据
  18. void CreateBiThrTree( BiThrTree *T )
  19. {
  20.         char c;

  21.         scanf("%c", &c);
  22.         if( ' ' == c )
  23.         {
  24.                 *T = NULL;
  25.         }
  26.         else
  27.         {
  28.                 *T = (BiThrNode *)malloc(sizeof(BiThrNode));
  29.                 (*T)->data = c;
  30.                 (*T)->ltag = Link;
  31.                 (*T)->rtag = Link;

  32.                 CreateBiThrTree(&(*T)->lchild);
  33.                 CreateBiThrTree(&(*T)->rchild);
  34.         }
  35. }

  36. // 中序遍历线索化
  37. void InThreading(BiThrTree T)
  38. {
  39.         if( T )
  40.         {
  41.                 InThreading( T->lchild );                // 递归左孩子线索化

  42.                 if( !T->lchild )        // 如果该结点没有左孩子,设置ltag为Thread,并把lchild指向刚刚访问的结点。
  43.                 {
  44.                         T->ltag = Thread;
  45.                         T->lchild = pre;
  46.                 }

  47.                 if( !pre->rchild )
  48.                 {
  49.                         pre->rtag = Thread;
  50.                         pre->rchild = T;
  51.                 }

  52.                 pre = T;

  53.                 InThreading( T->rchild );                // 递归右孩子线索化
  54.         }
  55. }

  56. void InOrderThreading( BiThrTree *p, BiThrTree T )
  57. {
  58.         *p = (BiThrTree)malloc(sizeof(BiThrNode));
  59.         (*p)->ltag = Link;
  60.         (*p)->rtag = Thread;
  61.         (*p)->rchild = *p;
  62.         if( !T )
  63.         {
  64.                 (*p)->lchild = *p;
  65.         }
  66.         else
  67.         {
  68.                 (*p)->lchild = T;
  69.                 pre = *p;
  70.                 InThreading(T);
  71.                 pre->rchild = *p;
  72.                 pre->rtag = Thread;
  73.                 (*p)->rchild = pre;
  74.         }
  75. }

  76. void visit( char c )
  77. {
  78.         printf("%c", c);
  79. }

  80. // 中序遍历二叉树,非递归
  81. void InOrderTraverse( BiThrTree T )
  82. {
  83.         BiThrTree p;
  84.         p = T->lchild;

  85.         while( p != T )
  86.         {
  87.                 while( p->ltag == Link )
  88.                 {
  89.                         p = p->lchild;
  90.                 }
  91.                 visit(p->data);

  92.                 while( p->rtag == Thread && p->rchild != T )
  93.                 {
  94.                         p = p->rchild;
  95.                         visit(p->data);
  96.                 }

  97.                 p = p->rchild;
  98.         }
  99. }

  100. int main()
  101. {
  102.         BiThrTree p, T = NULL;

  103.         CreateBiThrTree( &T );

  104.         InOrderThreading( &p, T );

  105.         printf("the result: \n");

  106.         InOrderTraverse( p );

  107.         printf("\n");

  108.         return 0;
  109. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> 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-3-28 19:10

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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