线索二叉树的中序线索化找前驱
// 线索二叉树.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

typedef struct BiThNode
{
char data;

BiThNode * lchild ;

BiThNode * rchild ;

int LTag;

int RTag;

}BiThNode, *BiThTree ;

BiThTree g_pre ;

void CreateTree( BiThTree &T)
{
char ch;

ch = getchar();

if(ch == ' ')

T = NULL;

else
{
T = (BiThTree) malloc(sizeof(BiThNode)) ;

if(!T)
{
cout<<"Out of space !";

return ;
}

T->data = ch ;

T->LTag = 0;

T->RTag = 0;

CreateTree( T->lchild ) ;

CreateTree( T->rchild ) ;

}

return ;
}

void InOrderThread ( BiThTree &Thrt , BiThTree T) //线索
{
void InThreading( BiThTree ) ;


Thrt = (BiThTree) malloc (sizeof(BiThNode)) ;

if(!Thrt)
{
cout<<"over follow !!";

return ;
}

Thrt->data = ' ';

Thrt->LTag = 0;

Thrt->RTag = 1;

Thrt->rchild = Thrt ;

if(!T) Thrt->lchild = Thrt ;

else
{
Thrt->lchild = T;

g_pre = Thrt;

InThreading( T ) ;

g_pre->rchild = Thrt ;

g_pre->RTag = 1 ;

Thrt->rchild = g_pre ;
}

return ;
}
void InThreading( BiThTree Q )
{
if(Q)
{
InThreading( Q->lchild ) ;

if(!Q->lchild )
{
Q->LTag = 1;

Q->lchild = g_pre;
}

if(!g_pre->rchild)
{
g_pre->RTag = 1;

g_pre->rchild = Q ;
}
g_pre = Q;

InThreading( Q->rchild ) ;
}
}

void InOederTravese(BiThTree &Thrt ) //中序遍历
{
BiThNode * q ;

q = Thrt->lchild ;

while( !(q == Thrt))
{
while(q->LTag == 0)

q = q->lchild;

cout<<'\t'<<q->data;

if(q->RTag == 1 && !(q->rchild== Thrt))
{
q = q->rchild ;

cout<<'\t'<<q->data;
}
q = q->rchild ;
}
cout<<endl;

return ;
}



void Search_pri(BiThTree Thrt, char e) //找前驱
{
BiThNode * q;

q = Thrt ->lchild ;

while( !(q== Thrt) )
{
while(q->LTag == 0)
{
q = q->lchild;

if(q->rchild->data == e)

{
cout<<"前驱："<<q->data;

return ;
}//if

}//while

if(q->RTag == 1 && !(q->rchild == Thrt))
{
q = q->rchild ;

if(q->rchild->data == e)
{
cout<<"前驱："<<q->data;
}//if
}//if

q = q->rchild ;

}

return ;

}

void main()
{
BiThTree T ;

BiThTree Thrt ;

char e;

cout<<"请输入树的结点数据： ";

CreateTree ( T ) ;

InOrderThread ( Thrt , T) ; //线索二叉树

cout<<endl<<"中序线索遍历：" ;

InOederTravese( Thrt ) ;

cout<<endl<<"求结点前驱，请输入结点名： ";

cin>>e;

Search_pri( Thrt, e ) ;

return ;
}

上面的是源代码：我测试的数据：abc##de#f##g###(#代表空格)，在找前驱的时候，出错。

请各位强人帮帮小弟，谢了。


[解决办法]
这样的程序都是自己调滴。。。
[解决办法]
你为什么不用工具贴代码？ 那样多清楚？
[解决办法]

C/C++ code

void Search_pri(BiThTree Thrt, char e)  {//中序遍历线索化后的二叉树找前驱     BiThNode * q;     q = Thrt ->lchild ;     while( q != Thrt) )   {         while(q->LTag == 0)         {               if(q->lchild->data == e) {                 cout < <"前驱：" < <q->data;                                 return ;             }//if             q = q->lchild;         }//while         while(q->RTag == 1 && q->rchild != Thrt)  {            if(q->rchild->data == e)  {                 cout < <"前驱：" < <q->data;             }//if             q = q->rchild ;         }//while        q = q->rchild ;     }     return ; }