1498 - 二叉排序树

1
2 
2
8 15 
4
21 10 5 39 

2 
2 
2 
8 15 
8 15 
15 8 
21 10 5 39 
5 10 21 39 
5 10 39 21 

C语言解答

#include<stdio.h>
#include<stdlib.h>
typedef int Treedata;
typedef struct Node
{
	Treedata data;
	struct Node *leftchild,*rightchild;
}treenode;
typedef treenode *tree;
treenode* creatTree(treenode *T,int x)
{
	if(T==NULL)
	{
		T=(treenode *)malloc(sizeof(treenode));
		    T->data=x;
			T->leftchild=NULL;
			T->rightchild=NULL;
	}
	else if(T->data>x)
	{
		T->leftchild=creatTree(T->leftchild,x);
	}
	else if(T->data<x)
	{
		T->rightchild=creatTree(T->rightchild,x);
	}
	else ;
	return T;
}
void preorder(treenode *T)
{
	if(T!=NULL)
	{	
		printf("%d ",T->data);
		preorder(T->leftchild);
		preorder(T->rightchild);
	}
}
void inorder(treenode *T)
{
	if(T!=NULL)
	{
		inorder(T->leftchild);
		printf("%d ",T->data);
		inorder(T->rightchild);
	}
}
void postorder(treenode *T)
{
	if(T!=NULL)
	{  
		postorder(T->leftchild);
		postorder(T->rightchild);		
		printf("%d ",T->data);
	}
}
void cleantree(treenode *T)
{
	if(T)
	{
		cleantree(T->leftchild);
		cleantree(T->rightchild);
		free(T);
	}
}
void main()
{
	int i,n,x;
	treenode *T;
	while(scanf("%d",&n)!=EOF)
	{   
		for(i=0,T=NULL;i<n;i++)
		{   
	        scanf("%d",&x);
          	T=creatTree(T,x);
		}
         preorder(T);
		 printf("\n");
         inorder(T);
         printf("\n");
         postorder(T);
         printf("\n");
         cleantree(T);
	}
}

C++解答

//
//题目描述：
//	输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
//	输入：
//	输入第一行包括一个整数n(1<=n<=100)。
//	接下来的一行包括n个整数。
//	输出：
//	可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
//	每种遍历结果输出一行。每行最后一个数据之后有一个空格。
//	样例输入：
//	5
//	1 6 5 9 8
//	样例输出：
//	1 6 5 9 8 
//	1 5 6 8 9 
//	5 8 9 6 1 
#include <stdio.h>
#include <stdlib.h>

typedef struct Tree{
	struct Tree *l;
	struct Tree *r;
	int data;
}Tree,*pTree;

void add(pTree boot,pTree tree){
	if(boot->data == tree->data)
		return;
	else if(boot->data > tree->data){
		if(boot->l != NULL)
			add(boot->l,tree);
		else
			boot->l = tree;
	}else{
		if(boot->r != NULL)
			add(boot->r,tree);
		else
			boot->r = tree;
	}
}

void pre_see(pTree tree){
	if( tree == NULL)
		return;
	printf("%d ",tree->data);
	pre_see(tree->l);
	pre_see(tree->r);
}

void mid_see(pTree tree){
	if(tree == NULL)
		return;	
	mid_see(tree->l);
	printf("%d ",tree->data);
	mid_see(tree->r);
}

 void last_see(pTree tree){
	if(tree == NULL)
		return;
	last_see(tree->l);
	last_see(tree->r);
	printf("%d ",tree->data);
}

int main()
{
	int n;
	while(scanf("%d",&n) != EOF){
		int i;
		pTree  boot  ;
		for(i=0; i<n; i++){
			if( i==0){
				boot = (pTree)malloc(sizeof(Tree));
				scanf("%d",&boot->data);
				boot->l = NULL;
				boot->r = NULL;
			}
			else{
				pTree temp;
				temp = (pTree)malloc(sizeof(Tree));
				scanf("%d",&temp->data);
				temp->l = NULL;
				temp->r = NULL;			
				add(boot,temp);
			}

		}

		pre_see(boot);printf("\n");
		mid_see(boot);printf("\n");
		last_see(boot);printf("\n");

	}
	return 0;
}