树查找

[编程题]树查找

热度指数：12717 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有一棵树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。该树是完全二叉树。

输入描述:

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

输出描述:

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

示例1

输入

4
1 2 3 4
2

输出

2 3

算法知识视频讲解

Java

azzz1112

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] arr = new int[n];
			
			for (int i = 0; i < n; i++) {
				arr[i] = scanner.nextInt();
			}
			
			int d = scanner.nextInt();
			
			if ( n >= Math.pow(2, d)-1) {
				//树的层数至少有d+1
				for (int i = (int)Math.pow(2, d-1)-1; i < Math.pow(2, d)-1 ; i++) {
					System.out.print(arr[i] + " ");
				}
			}else if (n >= Math.pow(2, d-1) && n < Math.pow(2, d)-1) {
				//树的层数为d
				for (int i = (int)Math.pow(2, d-1)-1; i < n; i++) {
					System.out.print(arr[i]+" ");
				}
			}else {
				//树的层数小于d
				System.out.println("EMPTY");
			}
			
		}
	}
}

编辑于 2024-03-24 21:14:55 回复(0)

Java

LHC0512

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            int[] nodes= new int[n];
            for (int i = 0; i < n ;i++) nodes[i] = scanner.nextInt();
            int d = scanner.nextInt();
            int start = (int) Math.pow(2,d-1)-1;
            if (start>=n){
                System.out.println("EMPTY");
                continue;
            }
            int len  = (int)Math.pow(2,d-1);
            for (int i = start; i <start+len ; i++) System.out.print(nodes[i]+" ");
            System.out.println();
        }
    }
}

编辑于 2020-03-18 19:18:36 回复(0)

Java

带带程序员

import java.util.*;
public class Main{
    public static void main(String[] args){
       Scanner scan = new Scanner(System.in);
       while(scan.hasNext()){
           int n = Integer.parseInt(scan.nextLine());
           String[] arr = scan.nextLine().split(" ");
           int m = Integer.parseInt(scan.nextLine());
           String result = "";
           for(int k = (int)((Math.pow(2, m - 1) - 1)) ;k < arr.length && k < (int)(Math.min(Math.pow(2, m) - 1, n));k++){
               result = result + arr[k] + " ";
           }
           if(result.equals(""))
               System.out.println("EMPTY");
           else
               System.out.println(result.substring(0, result.length() - 1));
       }
    }
}

发表于 2019-03-06 20:42:16 回复(0)

Java

yyywww

import java.util.*;

//写完之后才发现我写的太多余了

public class Main{
private static void searchTree(Tree tree,int n,int k,ArrayList<Integer> list){
if(n==k){
list.add(tree.value);
}else{
    if (tree.left!=null) {
        searchTree(tree.left,n,k+1,list);

            }
    if (tree.right!=null) {

        searchTree(tree.right,n,k+1,list);
            }
}
}
private static void setTree(Tree tree,int[] values,int[] flag,int stop,int x){
if(flag[0]<stop){
flag[0]+=1;
tree.value = values[x];
if(2*x+1<stop) {
    tree.left = new Tree();
    setTree(tree.left,values,flag,stop,2*x+1);

}
if(2*x+2<stop) {
    tree.right = new Tree();
    setTree(tree.right,values,flag,stop,2*x+2);

}
}
}

public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] values = new int[n];
for(int i = 0;i<n;i++){
values[i] = scanner.nextInt();

}
Tree tree = new Tree();
int[] flag = new int[1];
flag[0] = 0;
//(int) (Math.log((double)n)/Math.log((double)2))
setTree(tree,values,flag,n,0);
// printTree(tree);
ArrayList<Integer> list = new ArrayList<>();
int fff = scanner.nextInt();

searchTree(tree,fff,1,list);

int i;
for(i = 0;i<list.size()-1;i++){
System.out.print(list.get(i));
System.out.print(" ");
}
if (list.size()>0) {

    System.out.print(list.get(i));
        } else {
            System.out.print("EMPTY");
        }
scanner.close();
}
// private static void printTree(Tree tree) {
//     if(tree!=null) {
//         System.out.println(tree.value+"==================");
//         printTree(tree.left);
//         printTree(tree.right);
//     }
// }
}
class Tree{
int value;
Tree left = null;
Tree right = null;
}

发表于 2018-12-27 19:45:44 回复(0)