最后完善了一下算法:
问题描述:
设二叉树以二叉链结构存储,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