二叉树结点路径

怎么输出二叉树从根结点到任一结点的路径?设该树以二叉链存储,b为指向头结点指针,p为指向任意结点指针 

4 个解决方案

#1

知道怎么查找该结点,但不知道怎么保存正确路径并输出 
用栈解了半天解不出来,郁闷 用递归能不能解?麻烦会的同志帮我看看 感激不尽

#2

呵呵,最后还是自个做了出来.哎,自学可真晕,没人讨论没人指点,什么都得靠自己摸索 把算法贴出来一下吧 大家相互交流
程序分两部份:
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;
path(b,q);
return 0;
}


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

#3

楼主好牛啊

#4

最后完善了一下算法:


问题描述：

设二叉树以二叉链结构存储，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