二叉排序树的建立与搜索 【用c语言编写的完整程序，包括main()函数】

Question

实验要求:
1、定义含有字符型DATA和左右子树指针和父结点指针的二叉链表；
2、建立链表结构（含一个指向根结点的头结点）；
3、通过键盘输入链表的DATA，第一个字符为根，其他输入的字符，与根字符比较后，分别进入左、右子树；
4、确定特殊字符为结束符；
5、按照先序、中序、后序原则输出结点序列。

Answer 1

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

struct tree
{
char data;
tree *lchild,*rchild;
tree *father;
};

tree *Creat(tree *root,char p)
{
if(root==NULL)
{
root=(tree *)malloc(sizeof(tree));
root->lchild=NULL;
root->rchild=NULL;
root->father=NULL;
root->data = p;
}
else
{
if(root->data>=p)
{
root->lchild=Creat(root->lchild,p);
root->father = root->lchild;
}
else {
root->rchild=Creat(root->rchild,p);
root->father = root->rchild;
}
}
return root;
}

void PreOrderTraverse(tree *root)
{
if(root!=NULL)
{
PreOrderTraverse(root->lchild);
printf("%c ", root->data);
PreOrderTraverse(root->rchild);
}
}

void InOrderTraverse(tree *root) {
if ( root != NULL ) {
printf("%c ", root->data);
InOrderTraverse(root->lchild);
InOrderTraverse(root->rchild);
}
}

void PostOrderTraverse(tree *root) {
if ( root != NULL ) {
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%c ", root->data);
}
}

int main()
{
tree *root=NULL;
char p;
while( p = getchar() )
{
if ( p == ' ' || p == '\n' ) continue;
if ( p == '#' ) break;
root=Creat(root,p);
}
printf("先序： ");
InOrderTraverse(root);// 先序
printf("\n");
printf("中序： ");
PreOrderTraverse(root); // 中序
printf("\n后序： ");
PostOrderTraverse(root);// 后序
return 0;
}

Answer 2

#include <stdio.h>//二叉树排序
#include <stdlib.h>
typedef struct btree//结构
{
int a;
struct btree *L;
struct btree *R;
};
btree *create(int n)//建表
{
if(--n){
btree *p;
p=(btree *)malloc(sizeof(btree));
p->a=n;
p->L=create(n);
p->R=create(n);
return p;
}
else return NULL;
}
void commute(btree *p,btree *pre)//交换两个数的值
{
int t;
t=p->a;
p->a=pre->a;
pre->a=t;
}
void endpre(btree *p,btree *pre)//后序遍历 +排序
{
if(p){
endpre(p->L,p);//pre保持指向p的上层...
endpre(p->R,p);
if(pre->a > p->a)commute(pre,p);//孩子父母对换..
}
}
void headpre(btree *p)//前序遍历
{
if(p){

printf("%d ",p->a);
headpre(p->L);
headpre(p->R);
}
}
void depth(btree *p,int lev,int *pe)//求二叉树深度
{
if(p){
if(lev>*pe)*pe=lev;
depth(p->L,lev+1,pe);
depth(p->R,lev+1,pe);
}
}
int main()
{
btree *p;
int n,i=1,j=0;
scanf("%d",&n);
p=create(n);
headpre(p);
printf("\n");
depth(p,i,&j);//求二叉树深度
for(;j>0;j--)endpre(p,p);//这个循环次数为二叉树深度减一
headpre(p);
system("pause");
return 0;