/*******************
下面main()函数中的display(tree)函数和displaytbtree(tree)没有达到预期的输出结果(Turbo C for windows6.1运行环境)，有人指出其中inthread(btree)函数中指针越界！该函数修正后的代码是什么啊，请各位大哥大姐帮我写出来，谢谢！！感谢不尽！！！
当lflag=0,rflag=0表示lchild,rchild为左右孩子指针
当lflag=1,rflag=1表示lchild是前驱线索指针,rchild是后续线索指针
e
/ \
d g
/ / \
b f i
/ \ /
a c h
***********************************/

#include "stdio.h"
#include "stdlib.h" /*定义抽象数据类型*/
typedef char datatype;
typedef struct threadbtnode /*定义线索二叉树结构体类型*/
{
datatype data;
int lflag;
int rflag;
struct threadbtnode *lchild;
struct threadbtnode *rchild;
}tbtnode;
/*用值e初始化二叉树*/
tbtnode *inittbtree(datatype e)
{
tbtnode *root;
root=(tbtnode*)malloc(sizeof(tbtnode));
root->data=e;
root->lflag=1;
root->rflag=1;
root->lchild=NULL;
root->rchild=NULL;
return root;
}
/*建立一棵含有n个元素的二叉树tbtree，从数组中接收参数*/
void createtbtree(tbtnode *tbtree,datatype *elem,int n)
{
int i;
tbtnode *tbt,*p,*q;
for(i=0;i<n;i++)
{
p=tbtree;
tbt=(tbtnode*)malloc(sizeof(tbtnode));
tbt->data=elem;
tbt->lflag=1;
tbt->rflag=1;
tbt->lchild=NULL;
tbt->rchild=NULL;
while(p!=NULL)
{
q=p;
if(tbt->data<p->data)
p=p->lchild;
else
p=p->rchild;
}
if(tbt->data<q->data)
q->lchild=tbt;
else
q->rchild=tbt;
}
}
/*中序递归线索化二叉树*/
tbtnode *pre; /*节点pre始终指向tbtree的前驱节点*/
void inthread(tbtnode *tbtree)
{
if(tbtree!=NULL)
{
inthread(tbtree->lchild);
if(tbtree->lchild==NULL)
{
tbtree->lflag=1;
tbtree->lchild=pre;
}
else
tbtree->lflag=0;
if(pre->rchild==NULL)
{
pre->rflag=1;
pre->rchild=tbtree;
}
else
pre->rflag=0;
pre=tbtree;
inthread(tbtree->rchild);
}
}
/*加头节点的线索化二叉树算法*/
tbtnode *createinthread(tbtnode *tbtree)
{
tbtnode *threadroot;
threadroot=(tbtnode*)malloc(sizeof(tbtnode));
threadroot->lflag=0;
threadroot->rflag=1;
threadroot->rchild=threadroot;
if(tbtree==NULL)
{
threadroot->lflag=1;
threadroot->lchild=threadroot;
}
else
{
threadroot->lchild=tbtree;
pre=threadroot;
inthread(tbtree); /*调用二叉树线索化函数*/
pre->rflag=1;
pre->rchild=threadroot;
threadroot->rchild=pre;
}
return threadroot;
}
/*查找线索二叉树节点t的后续并返回该节点*/
tbtnode *nexttbtnode(tbtnode *t)
{
tbtnode *p;
if(t->rflag==1)
return t->rchild;
else
{
p=t->rchild;
while(p->lflag==0)
p=p->lchild;
return p;
}
}
/*中序遍历线索二叉树算法*/
void displaytbtree(tbtnode *tbtree)
{
tbtnode *p;
p=tbtree->rchild;
while(p->lflag==0)
p=p->lchild;
while(p!=tbtree)
{
printf("%2c",p->data);
p=nexttbtnode(p); /*调用线索二叉树后续节点查找函数*/
}
}
/*中序递归遍历算法输出二叉树*/
void display(tbtnode *btree)
{
if(btree!=NULL)
{
display(btree->lchild);
printf("%2c",btree->data);
display(btree->rchild);
}
}
/*主函数程序*/
main()
{
datatype string,str[8]={'d','g','b','f','i','a','c','h'};
tbtnode *tree;
tree=inittbtree('e'); /*调用二叉树初始化函数*/
createtbtree(tree,str,8); /*调用二叉树建立函数*/
inthread(tree); /*调用二叉树线索化函数*/
display(tree); /*调用中序递归遍历输出函数,结果应为a b c d e f g h i*/
tree=createinthread(tree); /*调用加头节点二叉树线索化函数*/
displaytbtree(tree); /*调用线索二叉树中序遍历输出函数,结果应为a b c d e f g h i*/
}

[此贴子已经被作者于2007-9-11 0:49:45编辑过]