二叉树用链式结构存储,b为树根指针,p为指向任意一结点指针,怎么输出从*b到*p的路径?
知道怎么查找该结点,但不知道怎么保存正确路径并输出
用栈解了半天解不出来,郁闷 用递归能不能解?麻烦会的同志帮我看看 感激不尽

谢谢楼上,我会再思考一下
下面是我自己弄的
哎,自学可真晕,没人讨论没人指点,什么都得靠自己摸索 把算法贴出来有什么不足大家指点
程序分两部份:
1,头文件btree.h部份定义树结点类型,用括号表示法的字符串建树   
2,path   函数部份用于找到并输出路径
建树和找路径都用的栈
////////btree.h部份////////////////////////////////////////////

#include   <stdio.h>
#include   <malloc.h>
#include   <stdlib.h>
#define   MAXSIZE   128*128
struct   BTNode           
{
char   data;
BTNode   *lchild;
BTNode   *rchild;
};
void   CreateBTNode(BTNode   *&b,char   str[])     
{
BTNode   *st[MAXSIZE],*p=NULL;
int   top=-1,k,i=0;
char   ch=str[i];
b=NULL;
while(ch!='\0')
{
switch(ch)
{
case   '(':   top++;st[top]=p;k=1;break;
case   ')':   top--;break;
case   ',':   k=2;break;
default:
p=(BTNode   *)malloc(sizeof(BTNode));
p-> data=ch;
p-> lchild=p-> rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case   1:   st[top]-> lchild=p;break;
case   2:   st[top]-> rchild=p;break;
}
}
}
i++;
                ch=str[i];
}
}

///////////////////path部份/////////////////////////////
#include   "btree.h"
void   path(BTNode   *b,BTNode   *q)
{
BTNode   *p;
struct   Stack
{   BTNode   *bt;
    int   flag;
};
Stack   st[MAXSIZE];
int   top=-1;
p=b;
do{
while(p!=NULL&&p-> data!=q-> data)
{   
        top++;
        st[top].bt=p;   
st[top].flag=0;
p=p-> lchild;   
}
if(p!=NULL)
{
for(int   i=0;i <=top;i++)
printf("%c-> ",st[i].bt-> data);
printf("%c\n",p-> data);
break;
}
else   if(p==NULL&&st[top].bt-> rchild!=NULL&&st[top].flag==0)
{     
p=st[top].bt-> rchild;
st[top].flag=1;
}
else
{   
top--;
        if(st[top].flag==0)
{
st[top].flag=1;
                p=st[top].bt-> rchild;
}
else   
top--;
}
}while(top!=-1);
}
////////////主函数调用//////////////////////////////////////////
int   main()
{
char   ch[MAXSIZE]="A(B(D(H,I),E(J,K)),C(F(L,M),G(N,O)))";
BTNode   *b;
CreateBTNode(b,ch);
BTNode   *q=b-> rchild-> lchild->lchild;
path(b,q);
return   0;
}


输出结果:A-> C-> F-> L

[[italic] 本帖最后由 nofarewell 于 2007-11-28 15:31 编辑 [/italic]]

我就用的栈,只是还给栈中元素加了一个标志位(感觉这个还是比较关键),确保不会重复搜索走过的路径.类似于解迷宫问题  今天又看了dfs和bfs算法  其实树也是图的一个特历 这两种算法也适用

最后完善了一下算法：

问题描述：
设二叉树以二叉链结构存储，b为指向根结点指针，x为任一结点类型数据，在树b中寻找x，并打印显示出经过的路径
算法思路：
1，定义树结点类型，设计创建树函数CreateBTNode()（用一个符号表示法的字符串创建），将这两部份定义为头文件btree.h。
2，设计求树的路径函数path()。
（1）定义一个栈，保存查找时经过的结点指针，并增加一个标志位flag避免回溯时访问已访问过的结点。
（2）类似于先序遍历，先访问根结点，然后访问左子树，接着是右子树，直至找到该结点。
（3）如果找到该结点，则打印栈中的数据（从栈底至栈顶）。如果找不到，则显示相关信息。
算法实现：
//btree.h:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 128*128
struct BTNode          //定义树结点类型
{
 char data;              //结点数据
 BTNode *lchild;          //左孩子指针
 BTNode *rchild;        //右孩子指针
};
void CreateBTNode(BTNode *&b,char ch[])           //用括号表示法的子符串创建树
{
 BTNode *st[MAXSIZE],*p=NULL;                     //由于和本主题无关，这里就不多做介绍
 int top=-1,k,i=0;
 b=NULL;
 while(ch[i]!='\0')
 {
  switch(ch[i])
  {
  case '(': top++;st[top]=p;k=1;break;
  case ')': top--;break;
  case ',': k=2;break;
  default:
      p=(BTNode *)malloc(sizeof(BTNode));
   p->data=ch[i];
   p->lchild=p->rchild=NULL;
   if(b==NULL)
    b=p;
   else
   {
    switch(k)
    {
    case 1: st[top]->lchild=p;break;
    case 2: st[top]->rchild=p;break;
    }
   }
  }
  i++;
 }
}

//function path():
#include "btree.h"
void path(BTNode *b,char x)
{
 BTNode *p;
 struct TreeNodeStack          //定义保存用于查找过程中保存结点指针的栈
 { BTNode *bt;                       //bt保存结点指针
   int flag;                              //flag标志确定该结点是否左右子树都已查找过
 }st[MAXSIZE];                     
 int top=-1;
 p=b;
 if(b->data==x)            //如果根结点数据等于x
  printf("%c\n",b->data);
 else                 //如果不是根结点
 {
  do{
   while(p!=NULL&&p->data!=x)         //先在左子树中查找
   {
    top++;
          st[top].bt=p;
       st[top].flag=0;                     //进栈时flag为零，表示还未查找其右子树
       p=p->lchild;
   }
   if(p!=NULL)                //如果找到，则打印栈中内容（从栈底至栈顶）
   {
       for(int i=0;i<=top;i++)
     printf("%c->",st[i].bt->data);
       printf("%c\n",p->data);
       break;
   }
   else if(p==NULL&&st[top].bt->rchild!=NULL&&st[top].flag==0)   //如果在左子树中未找到，且其右子树不空
   {                                                                                                                //且未查找过
       p=st[top].bt->rchild;             //查找右子树
       st[top].flag=1;                      //flag置1表示其左右子树均查找过
   }
   else                                //如果是叶子结点
   {
       top--;                       //往后回溯
    if(st[top].flag==0)              //如果回溯后的结点的右子树还未访问
    {
        st[top].flag=1;             //标志位置1
              p=st[top].bt->rchild;               //访问其右子树
    }
    else                      //如果回溯后的结点右子树已访问
        top--;                //再回溯一次，直至找到右子树还没访问的结点
   }
  }while(top!=-1);          //查找直至栈空
  if(top<=-1)
  printf("can't find the tree node!\n");         //栈空且未找到该结点，打印提示信息
 }
}

//main():
int main()
{
 char ch[MAXSIZE]="A(B(D(H,I),E(J,K)),C(F(L,M),G(N,O)))";               
 BTNode *b;
 CreateBTNode(b,ch);
 char x;
 printf("plese input the data of tree node which you want to look up:\n");
 scanf("%c",&x);
 path(b,x);
 return 0;
}

输入：O
输出：
A->C->G->O

我倒 要的是根结点到那个结点的路径，不是搜索整棵树直至访问到该结点的所有访问过的结点。递归型的数据结构，不做标记怎么能行？如果是多余的请版主同志帮我弄一个看看