| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2909 人关注过本帖
标题:二叉树的路径问题
只看楼主 加入收藏
nofarewell
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-5-14
收藏
 问题点数:0 回复次数:10 
二叉树的路径问题
二叉树用链式结构存储,b为树根指针,p为指向任意一结点指针,怎么输出从*b到*p的路径?
知道怎么查找该结点,但不知道怎么保存正确路径并输出
用栈解了半天解不出来,郁闷 用递归能不能解?麻烦会的同志帮我看看 感激不尽
搜索更多相关主题的帖子: 二叉树 路径 
2007-11-28 13:57
静思
Rank: 3Rank: 3
来 自:沈阳
等 级:新手上路
威 望:8
帖 子:630
专家分:0
注 册:2006-2-28
收藏
得分:0 
采用二叉树的先根次序遍历的递归版本算法,对p及当前遍历到的结点指针进行匹配检测,并把当前检测的结点信息存放至一个数组中(以便最后输出)
       当发现有匹配时,则结束先根遍历,并将找到标志位置true。
     根据标志位如果为true,先序输出路径上的节点。否则 输出没有找到.

英者自知,雄者自胜
2007-11-28 14:39
nofarewell
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-5-14
收藏
得分:0 
谢谢楼上,我会再思考一下
下面是我自己弄的
哎,自学可真晕,没人讨论没人指点,什么都得靠自己摸索 把算法贴出来有什么不足大家指点
程序分两部份:
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]]
2007-11-28 15:29
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
第一首先用,选择那种遍历,肯定是先序遍历,从根结点开始, p=t,p!=q这样不停的搜索,
用栈保存,如果相等了就出栈,还要打出栈内容。
2007-11-28 20:09
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
前序遍历二叉树,然后把栈中东西,倒着打印出来.

倚天照海花无数,流水高山心自知。
2007-11-28 20:35
nofarewell
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-5-14
收藏
得分:0 
我就用的栈,只是还给栈中元素加了一个标志位(感觉这个还是比较关键),确保不会重复搜索走过的路径.类似于解迷宫问题  今天又看了dfs和bfs算法  其实树也是图的一个特历 这两种算法也适用
2007-11-28 22:17
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
感觉你的标志位可能是多余的.

倚天照海花无数,流水高山心自知。
2007-11-28 22:58
nofarewell
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-5-14
收藏
得分:0 
最后完善了一下算法:

问题描述:
设二叉树以二叉链结构存储,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
2007-11-29 16:45
FenteLi
Rank: 1
来 自:上海
等 级:新手上路
帖 子:124
专家分:0
注 册:2007-11-24
收藏
得分:0 
学习,学习。。。。
2007-11-29 17:43
missiyou
Rank: 5Rank: 5
等 级:贵宾
威 望:16
帖 子:531
专家分:218
注 册:2007-10-9
收藏
得分:0 
bitree path(bitree T,int data,bitree A[], int n)
{
   if(!T)
    if(T->data!=data)
    {   A[n]=path(T->lchild,data,A[],n-1);
         A[n]=paht(T->child,data,A[],n-1);
   pirntf("%d",A[n]->data);
     }
  else
{ return NULL;
}

}
本人写了一个递归,没有经常测试,也不知道对不对。
2007-11-29 21:50
快速回复:二叉树的路径问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035838 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved