首页 > ACM题库 > 九度OJ > 九度-1176-树查找[解题代码]
2013
12-13

九度-1176-树查找[解题代码]

题目来源:2010年北京邮电大学网院研究生机试真题

题目描述:
有一棵树,输出某一深度的所有节点,有则输出这些节点,无则输出EMPTY。该树是完全二叉树。

输入:
输入有多组数据。
每组输入一个n(1<=n<=1000),然后将树中的这n个节点依次输入,再输入一个d代表深度。

输出:
输出该树中第d层得所有节点,节点间用空格隔开,最后一个节点后没有空格。

样例输入:
4
1 2 3 4
2
样例输出:
2 3

java 代码如下:

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNextInt()){
			int n = s.nextInt();
			int[] tree = new int[n];
			for(int i=0; i<n; i++){
				tree[i] = s.nextInt();
			}
			int d = s.nextInt();
			int start = (int) Math.pow(2, d-1);
			int end = (int) Math.pow(2, d)-1;
			if(end > n)
				end = n;

			if(start > n){
				System.out.println("EMPTY");
				return;
			}

			for(int i=start; i<=end; i++){
				if(i != end)
					System.out.print(tree[i-1]+" ");
				else
					System.out.println(tree[i-1]);
			}
		}
	}

}

/**************************************************************
	Problem: 1176
	User: coder
	Language: Java
	Result: Accepted
	Time:340 ms
	Memory:20284 kb
****************************************************************/

 


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.