急！！！请帮忙找一下错，二叉树查找函数。

Question

下面的二叉树查找函数只能找到根节点，其他节点都找不到，怎么回事啊？请大家不吝赐教！

void mytree::searchtemp(tnode *sub_root,tnode *st[MaxSize],int i)
{ //按中序遍历的顺序将节点依次存储于st中
if (sub_root)
{
searchtemp(sub_root->lchild,st,i);
st[i]=sub_root;
i++;
searchtemp(sub_root->rchild,st,i);
}
for(;i<MaxSize;i++)st[i]=NULL;
}

void mytree::search(string data)
{
tnode *st[MaxSize];

int i=0;
searchtemp(bt,st,i);

for(i=0;i<MaxSize;i++) //在st中查找data
{
if(st[i]!=NULL) //若未到达最后一个结点则继续查找
{
if(st[i]->data==data)
{
cout<<"该元素在当前二叉树中！"<<endl;
i=i+1;break;
}
}
else
{
cout<<"该元素不在当前二叉树中!"<<endl;
break;
} //已到达最后一个结点，查找结束。查找失败。
}
}

Answer 1

这是我刚做好的，你下载一个dev-cpp软件，把这个复制进去编译就行了。
数据结构课程设计源程序
注：main函数在最后，这样编译时就不用声明其他要用的函数。

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status ;
//函数状态类型
typedef int ElemType ;
//二叉树结点数据类型为整型
#define FORMAT "%d "
//输出格式与ElemType对应

void RandomHundred(int ran[100])
//产生100个不大于100且各不相同的整数，存放在ran[100]中
{int i,temp,ransubscript ;
//temp用于交换，ransubscript为随机下标
for(i=1;i<101;++i)ran[i-1]=i ;
//先把1－100按顺序放入数组中
for(i=100;i>0;--i)
{ransubscript=rand()%i ;
//产生随机下标
temp=ran[i-1];
ran[i-1]=ran[ransubscript];
ran[ransubscript]=temp ;
//交换ran[i-1]与ran[ransubscript]}}
typedef struct BSTNode
{ElemType data ;
int bf ;
/*结点的平衡因子*/
struct BSTNode*lchild,*rchild ;
/* 左、右孩子指针 */}BSTNode,*BSTree ;
#define EQ(a,b)((a)==(b))
#define LT(a,b)((a)<(b))
#define LH +1 /* 左高 */
#define EH 0 /* 等高 */
#define RH -1 /* 右高 */
void R_Rotate(BSTree*p)
{/* 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转 */
/* 处理之前的左子树的根结点。算法9.9 */
BSTree lc ;
lc=(*p)->lchild ;
/* lc指向p的左子树根结点 */
(*p)->lchild=lc->rchild ;
/* lc的右子树挂接为p的左子树 */
lc->rchild=*p ;
*p=lc ;
/* p指向新的根结点 */}

void L_Rotate(BSTree*p)
{/* 对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转 */
/* 处理之前的右子树的根结点。算法9.10 */
BSTree rc ;
rc=(*p)->rchild ;
/* rc指向p的右子树根结点 */
(*p)->rchild=rc->lchild ;
/* rc的左子树挂接为p的右子树 */
rc->lchild=*p ;
*p=rc ;
/* p指向新的根结点 */}

void LeftBalance(BSTree*T)
{/* 对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时， */
/* 指针T指向新的根结点。算法9.12 */
BSTree lc,rd ;
lc=(*T)->lchild ;
/* lc指向*T的左子树根结点 */
switch(lc->bf)
{ /* 检查*T的左子树的平衡度，并作相应平衡处理 */
case LH :
/* 新结点插入在*T的左孩子的左子树上，要作单右旋处理 */
(*T)->bf=lc->bf=EH ;
R_Rotate(T);
break ;
case RH :
/* 新结点插入在*T的左孩子的右子树上，要作双旋处理 */
rd=lc->rchild ;
/* rd指向*T的左孩子的右子树根 */
switch(rd->bf)
{ /* 修改*T及其左孩子的平衡因子 */
case LH :
(*T)->bf=RH ;
lc->bf=EH ;
break ;
case EH :
(*T)->bf=lc->bf=EH ;
break ;
case RH :
(*T)->bf=EH ;
lc->bf=LH ;
break ;}
rd->bf=EH ;
L_Rotate(&(*T)->lchild);
/* 对*T的左子树作左旋平衡处理 */
R_Rotate(T);
/* 对*T作右旋平衡处理 * }}

void RightBalance(BSTree*T)
{/* 对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时， */
/* 指针T指向新的根结点 */
BSTree rc,rd ;
rc=(*T)->rchild ;
/* rc指向*T的右子树根结点 */
switch(rc->bf)
{/* 检查*T的右子树的平衡度，并作相应平衡处理 */
case RH :
/* 新结点插入在*T的右孩子的右子树上，要作单左旋处理 */
(*T)->bf=rc->bf=EH ;
L_Rotate(T);
break ;
case LH :
/* 新结点插入在*T的右孩子的左子树上，要作双旋处理 */
rd=rc->lchild ;
/* rd指向*T的右孩子的左子树根 */
switch(rd->bf)
{/* 修改*T及其右孩子的平衡因子 */
case RH :
(*T)->bf=LH ;
rc->bf=EH ;
break ;
case EH :
(*T)->bf=rc->bf=EH ;
break ;
case LH :
(*T)->bf=EH ;
rc->bf=RH ;
break ;}
rd->bf=EH ;
R_Rotate(&(*T)->rchild);
/* 对*T的右子树作右旋平衡处理 */
L_Rotate(T);
/* 对*T作左旋平衡处理 */}}

Status InsertAVL(BSTree*T,ElemType e,Status*taller)
{/* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */
/* 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */
/* 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。算法9.11 */
if(!*T)
{/* 插入新结点，树“长高”，置taller为TRUE */
*T=(BSTree)malloc(sizeof(BSTNode));
(*T)->data=e ;
(*T)->lchild=(*T)->rchild=NULL ;
(*T)->bf=EH ;
*taller=TRUE ;}
else
{if(EQ(e,(*T)->data))
{/* 树中已存在和e有相同关键字的结点则不再插入 */
*taller=FALSE ;
return FALSE ;}
if(LT(e,(*T)->data))
{/* 应继续在*T的左子树中进行搜索 */
/* 未插入 */
if(!InsertAVL(&(*T)->lchild,e,taller))return FALSE ;
/* 已插入到*T的左子树中且左子树“长高” */
/* 检查*T的平衡度 */
if(*taller)switch((*T)->bf)
{case LH :
/* 原本左子树比右子树高，需要作左平衡处理 */
LeftBalance(T);
*taller=FALSE ;
break ;
case EH :
/* 原本左、右子树等高，现因左子树增高而使树增高 */
(*T)->bf=LH ;
*taller=TRUE ;
break ;
case RH :
(*T)->bf=EH ;
/* 原本右子树比左子树高，现左、右子树等高 */
*taller=FALSE ;}}
else
{/* 应继续在*T的右子树中进行搜索 */
/* 未插入 */
if(!InsertAVL(&(*T)->rchild,e,taller))return FALSE ;
/* 已插入到T的右子树且右子树“长高” */
/* 检查T的平衡度 */
if(*taller)switch((*T)->bf)
{case LH :
(*T)->bf=EH ;
/* 原本左子树比右子树高，现左、右子树等高 */
*taller=FALSE ;
break ;
case EH :
/* 原本左、右子树等高，现因右子树增高而使树增高 */
(*T)->bf=RH ;
*taller=TRUE ;
break ;
case RH :
/* 原本右子树比左子树高，需要作右平衡处理 */
RightBalance(T);
*taller=FALSE ;}}}
return TRUE ;}

typedef BSTree SElemType;//这个很重要，定义栈的元素类型为二叉树结点指针BSTree
//栈的顺序存储表示
//SElemType为栈元素，由用户在主函数中定义
#define STACK_INIT_SIZE 100 /* 存储空间初始分配量 */
#define STACKINCREMENT 10 /* 存储空间分配增量 */
typedef struct SqStack
{SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
//顺序栈（存储结构由SqStack.h定义）的基本操作
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;}

Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;}

Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;}
*((*S).top)++=e;
return OK;}

Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;}
void PreOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
//非递归先序遍历二叉树
{BSTree p,e ;
SqStack S ;
InitStack(&S);
p=T ;
while(p||!StackEmpty(S))
{//遍历左子树
while(p)
{ (*Visit)(p->data);
Push(&S,p);
p=p->lchild ;}
//通过下一次循环中的内嵌while实现右子树遍历
if(!StackEmpty(S))
{Pop(&S,&e);
p=e->rchild ;}}}

void InOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
{/* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果: 中序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
if(T)
{InOrderTraverse(T->lchild,(*Visit));
/* 先中序遍历左子树 */
(*Visit)(T->data);
/* 再访问根结点 */
InOrderTraverse(T->rchild,(*Visit));
/* 最后中序遍历右子树 */}}

void PostOrderTraverse(BSTree T,Status(*Visit)(ElemType e))
{/* 初始条件: 二叉树T存在,Visit是对结点操作的应用函数 */
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit一次且仅一次 */
/* T不空 */
if(T)
{PostOrderTraverse(T->lchild,(*Visit));
/* 先后序遍历左子树 */
PostOrderTraverse(T->rchild,(*Visit));
/* 再后序遍历右子树 */
(*Visit)(T->data);
/* 最后访问根结点 */}}

/*输出元素*/
Status PrintElement(ElemType e)
{printf(FORMAT,e);
return OK ;}

#include"RandomHundred.c"
//功能模块1－void RandomHundred(int ran[100]);产生100个不大于100且各不相同的整数，存放在ran[100]中
#include"BSTree.h"
//平衡二叉排序树的类型定义
#include"InsertAVL.c"
//功能模块2－Status InsertAVL(BSTree *T,ElemType e,Status *taller);
//平衡二叉排序树T插入元素e,taller为长高标志供递归调用时检查
typedef BSTree SElemType;//这个很重要，定义栈的元素类型为二叉树结点指针BSTree
#include"SqStack.h"
//顺序栈的存储结构
#include"SqStack.c"
//栈的操作:供非递归先序遍历用
#include"Traverse.c"
//功能模块3－void PreOrderTraverse(BSTree T,Status (*Visit)(ElemType e));非递归先序遍历二叉树
//void InOrderTraverse(BSTree T,Status(*Visit)(ElemType e));中序遍历二叉树
//void PostOrderTraverse(BSTree T,Status(*Visit)(ElemType e));后序遍历二叉树
//Status PrintElement(ElemType e);输出元素函数，供遍历调用
main()
{//主函数
BSTree T=NULL ;
//注意T必须先置空，非常重要
int i,ran[100];
//i为计数器，ran数组用于存放从RandomHundred函数随机得来的1－100
Status taller ;
//长高与否标志，可以不初始化
printf("数据结构课程设计题目：\n");
printf("1－－利用随机函数产生100个(不大于100且各不相同的)随机整数\n");
printf("2－－用这些整数来生成一棵二叉树\n");
printf("3－－分别对二叉树进行先序遍历，中序遍历和后序遍历输出树中结点元素序列\n");
printf("注意：先序遍历输出要求采用非递归来实现\n\n");
printf("产生100个(不大于100且各不相同的)随机整数：\n");
RandomHundred(ran);
for(i=0;i<100;++i)printf(FORMAT,ran[i]);
printf("\n\n");
for(i=0;i<100;++i)InsertAVL(&T,ran[i],&taller);
printf("已经按以上顺序把这些整数一个一个插入平衡二叉排序树!\n\n");
printf("先序遍历二叉树(采用非递归算法):\n");
PreOrderTraverse(T,PrintElement);
printf("\n");
printf("中序遍历二叉树:\n");
InOrderTraverse(T,PrintElement);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrderTraverse(T,PrintElement);
printf("\n\n");
printf("课程设计题目演示完毕!\n06级统计一班 高翕山 200630980108\n");
getch();
}答者： edogoku | 二级

Answer 2

1. 你这压根就不是二叉树查找,是个遍历二叉树的方法
2. searchtemp 有错误, 这个函数的做法是将二叉树的所有节点放到数组里面
但是 searchtemp(sub_root->lchild,st,i); 每次递归进来传入的 i 都是一样的 为 0
searchtemp(sub_root->rchild,st,i); 中的 i 倒是每次都递增了,但除了最后一次意外都被 for(;i<MaxSize;i++)st[i]=NULL; 给弄掉了.
你这个地方要改的话, 需要让 searchtemp 返回一个值, 表示sub_root->lchild的总的元素个数
然后searchtemp传入的i在这个元素个数上再往后赋值本回答被提问者采纳

Answer 3

void createbintree(bintree *t){
printf("创建树:\n"); //这句最好不要
char ch;
if((ch=getchar())==' ') *t=NULL;
else{
*t=(bintree*)malloc(sizeof(bintree));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
传值是单向的，传址则要操作地址。

==============================
*t=(bintree*)malloc(sizeof(binnode));

要不，贴贴你的定义。

==============================
#include "stdio.h"
#include "malloc.h"
typedef struct node{
char data;
struct node *lchild,* rchild;
}*bintree;

void createbintree(bintree *t)
{
char ch;
if((ch=getchar())==' ') *t=NULL;
else{
*t=(bintree*)malloc(sizeof(bintree));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}

===============================
晕，关键是，在创建过程中，是动态分配内存，这个新得到的指针，把最初调用过程传入的指针冲掉了。
假设，有过程
void foo(int * p)
调用：
int i;
foo(&i);
在void foo(int *p)
{p++;
p=malloc(sizeof(int));
}
这里面的两个操作，对调用过程的i，完全没影响。
所以，改一下：
int *i;
foo(&i);
过程：
void foo(int **i)
{*i=malloc(2);
}