线索二叉树里不明白的地方!
下面的程序已经跟踪过,想请教大神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;
}
我怎么感觉你没有跟踪过
因为我在你的代码CreateBiThrTree就陷入一个无线递归,没有任何返回条件 lumber2388779 发表于 2017-4-22 20:43
我怎么感觉你没有跟踪过
因为我在你的代码CreateBiThrTree就陷入一个无线递归,没有任何返回条件
额~~这个是小甲鱼的源代码~~我就是想请教一下*p在经历了线索遍历二叉树之后为什么值没有变???{:5_96:} pokerlee 发表于 2017-4-23 18:13
额~~这个是小甲鱼的源代码~~我就是想请教一下*p在经历了线索遍历二叉树之后为什么值没有变???
感觉你不明白那块我是觉得有问题,因为我看了下好像没有起到该有的作用
下面的程序已经跟踪过,想请教大神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;
这三句代码只是将双方互指而已 Code_mzh 发表于 2018-2-17 12:09
下面的程序已经跟踪过,想请教大神InOrderThreading()函数中else功能中为什么要进行pre->rchild = *p?如 ...
所以p的地址是始终不变的
页:
[1]