首页 > ACM题库 > 九度OJ > 九度-1201-二叉排序树[解题代码]
2013
12-13

九度-1201-二叉排序树[解题代码]

题目来源:2005年华中科技大学计算机保研机试真题

题目描述:

    输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。

输入:

    输入第一行包括一个整数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 
提示:

输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。


cpp 代码如下:
#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;
}
/**************************************************************
	Problem: 1201
	User: coder
	Language: C
	Result: Accepted
	Time:70 ms
	Memory:2360 kb
****************************************************************/


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  3. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  4. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的