数据结构 线索二叉树 小甲鱼代码有个地方不明白
本帖最后由 洛熙封晨 于 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行不是很明白，求大神讲解这几行代码的作用
(*p)->lchild = T; //p是指针的指针
pre = *p; //pre是指针
InThreading(T); //调用这个函数，你注释的是中序遍历线索化
pre->rchild = *p; //做孩子赋值为一个指针。。。*p
pre->rtag = Thread; //rtag 标记为Thread
(*p)->rchild = pre;//*p的右孩子为pre.......这个不是数据结构的视频么。。。。反正大概原理懂了就行。。。基本上不用。。用的时候。。在百度。。copy。。。然后。。就是那样。。。。相信我。。。
ps； 有什么说错的。。请见谅 看了下，我也不明白，呵呵 (*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: 立夏表示即将告别春天，夏天开始。 pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
这三行代码我的理解是将头结点和最后一个结点相互指向，连接起来，也就是向双向链表一样连接起来 pre->rchild = *p;
pre->rtag = Thread;
(*p)->rchild = pre;
这三行代码我的理解是将头结点和最后一个结点相互指向，连接起来，也就是向双向链表一样连接起来
页:
[1]