Question

C语言课程设计，二叉树，源程序已给出，求三种便利程序和注释以及流程图！

以下是题目要求，哪位大仙可以帮我把这个搞定了。需要三种遍历，注释和流程图。可以发我邮箱：chziyang@foxmail.com。万分感谢！
【题目要求】

以下内容中，(1)、(2)、(3)为必做内容。

（1）下面是用链式结构实现二叉树的建立、查询和打印的源程序(见第三部分的设计示例)。读懂上述程序，为程序写出注释，并画出程序的框图（流程图）。

（2）请将他们输入计算机，编译、连接并运行。

（3）编写二叉排序树的前序遍历程序、中序遍历程序和后序遍历程序。

#include<iostream.h>
#include<stdio.h>

struct tree {
char info;
struct tree *left,*right;
};

struct tree *create_btree(struct tree *root,struct tree *r,char info);
struct tree *search_btree(struct tree *root,char key);
void print_btree(struct tree *r,int l);

main ()
{ char s[100],c,key=' ' ;
struct tree *root=0 ;
do {
printf("Enter a letter:");
gets(s);
if (!root)
root=create_btree(root,root,*s);
else
create_btree(root,root,*s);
} while (*s) ;
print_btree(root,0);
key='1';
while ( key)
{
printf("Enter a key to find:");
scanf("%s",&c);
root=search_btree(root,c);
printf("press to continue\n");
}
} /* Btree.C 结束 */

struct tree *create_btree(struct tree *root,struct tree *r,char info)
{ if (r ==0 )
{ r=new (struct tree);// same as function: malloc(sizeof())
if ( r == 0)
{ printf("Out of memory\n"); return 0 ; }
r->left= 0; r->right=0; r->info=info;
if (root)
{ if(info<root->info) root -> left=r;
else root -> right=r;
}
else
{ r->right=0; r->left = 0; }
return r;
} /* if = = 0 接下页 */
if (info < r->info)
create_btree(r,r->left,info);
if(info>=r->info)
create_btree(r,r->right,info);
} /* create_btree(root,r,info) */

struct tree *search_btree(struct tree *root,char key)
{ if (!root)
{ printf("Emptu btree\n"); return root; }
while(root->info!=key)
{ if(key<root->info)
root=root->left;
else
root=root->right;
if(root==0)
{ printf("Search Failure\n");
break ;
}
} /* while(root->info!=key) */
if (root !=0)
printf("Successful search\n key=%c\n",root->info);
return root ;
} /* *search_btree(root,key) */

void print_btree(struct tree *r,int l)

{ int i;
if (r == 0) return ;
print_btree(r->left,l+1);
for(i=0;i<l;i++)
printf(" ");
printf("%c\n",r->info);
print_btree(r->right,l+1);
}

Answer 1

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>

struct tree //定义结构体tree
{
char info;
struct tree *left,*right; //定义左树结点指针和右树结点指针
};
//声明函数
struct tree *create_btree(struct tree *root,struct tree *r,char info);
struct tree *search_btree(struct tree *root,char key);
void print_btree(struct tree *r,int l);
void pretra(struct tree *head);
void midtra(struct tree *head);
void afttra(struct tree *head);

main ()
{
char s[100],c,key=' ' ;
struct tree *root=0 ;
do
{
printf("Enter a letter:");
gets(s);
//下面这个条件是我添加的，如果没有这个条件最后会多一个info为NULL也就是0的值，因为是先gets(s)->赋值，最后才判断*s是否为空
if(*s==0)
break;
if (!root)
root=create_btree(root,root,*s);
else
create_btree(root,root,*s);
}while(*s) ;

//printf("%d",root->left);

print_btree(root,0);
printf("前序遍历:\n");
pretra(root);
printf("\n");
printf("中序遍历:\n");
midtra(root);
printf("\n");
printf("后序遍历:\n");
afttra(root);
printf("\n");
key='1';
while (key)
{
printf("Enter a key to find:");
scanf("%s",&c);
root=search_btree(root,c);
printf("press to continue\n");
}
} /* Btree.C 结束 */
//创建二叉树,实际上创建的是一个有序二叉树
struct tree *create_btree(struct tree *root,struct tree *r,char info)
{
if (r ==0 ) //也就是r==NULL
{
//r=new(struct tree);// same as function: malloc(sizeof())
r=(struct tree *)malloc(sizeof(struct tree)); //我这用前面那句老是编译不过
if ( r == 0) //如果内存申请失败，就报错然后退出
{
printf("Out of memory\n");
return 0;
}
r->left=0; //初始化这个新结点
r->right=0;
r->info=info; //将输入的字符赋值给这个结点
if (root) //如果root不为空
{
if(info<root->info) //如果info小于root的info，则新结点为root的左结点
root -> left=r;
else //否则为右结点
root -> right=r;
}
else
{
r->right=0; //如果root为空，那么新结点的左右结点都设置为空
r->left=0;
}
return r; //返回新结点的指针的地址
} /* if = = 0 接下页 */
if (info < r->info) //如果输入的info小于r的info
create_btree(r,r->left,info); //递归调用，目的是插入到合适的位置，小则跟左子结点比较，没有就加为左子结点
if(info>=r->info)
create_btree(r,r->right,info); //同理，没有右子节点就加为右子结点
} /* create_btree(root,r,info) */

//查询功能
struct tree *search_btree(struct tree *root,char key)
{
if (!root) //如果跟结点为空，输出该二叉树是一个空二叉树,并返回NULL
{
printf("Emptu btree\n");
return root;
}
while(root->info!=key) //如果当前结点不是要查找的结点
{
if(key<root->info) //如果要查找的结点小于当前结点，当前结点指向当前结点的左结点
root=root->left;
else
root=root->right; //如果key大于当前结点，则当前结点指向当前结点的右结点
if(root==0) //如果root为空，打印查找失败
{
printf("Search Failure\n");
break ;
}
} /* while(root->info!=key) */
if (root !=0) //如果root不为空，也就是上面找到了root->info==key的值
printf("Successful search\n key=%c\n",root->info); //那么返回找到的值
return root ; //分会该值的指针，如果没找到是NULL,找到的话就是找到结点的指针
} /* *search_btree(root,key) */

//二叉树的输出
void print_btree(struct tree *r,int l)
{
int i;
if (r == 0)
return ; //如果r指针为空，该次调用返回
print_btree(r->left,l+1); //调用传入结点的左子结点
for(i=0;i<l;i++) //打印l*2个空格
printf(" ");
printf("%c\n",r->info); //打印出该结点的info值
print_btree(r->right,l+1); //调用传入结点的又子结点
}

void pretra(struct tree *head) //前序遍历
{
if(NULL==head)
{
printf("这是一个空的二叉树!\n");
return;
}
else
{
printf("%c",head->info);
if(head->left!=NULL)
pretra(head->left);
if(head->right!=NULL)
pretra(head->right);
}
}

void midtra(struct tree *head) //中序遍历
{
if(NULL==head)
{
printf("这是一个空的二叉树!\n");
return;
}
else
{
if(head->left!=NULL)
midtra(head->left);
printf("%c",head->info);
if(head->right!=NULL)
midtra(head->right);
}
}

void afttra(struct tree *head) //后序遍历
{
if(NULL==head)
{
printf("这是一个空的二叉树!\n");
return;
}
else
{
if(head->left!=NULL)
afttra(head->left);
if(head->right!=NULL)
afttra(head->right);
printf("%c",head->info);
}
}