去哪儿的二叉树那题用java如何输入一个完整的树啊
发布于 2017-09-20 11:10 2122 次浏览 0 赞 来自 我要提问  

思路都有,就是输入不知道怎么表示,怎么存,而且也不知道输入多少个节点,好尴尬。。

8 条回复

输入好存

主要是思路 递归方法   我用的3个ArrayList存储的  一个存根  一个存左 一个右  但是写递归的时候不知道怎么办了  

2017-09-20 11:14

package cs;


import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

import java.util.Scanner;

import java.util.Set;


/**

 * 

5

5:4|7

4:3|8

7:2|-1

3:-1|-1

8:-1|-1

2:-1|-1

 * [@author](/user/author) 

 *

 */

public class quna {

static int isT=1;

static List<Integer> tem=new ArrayList<>();

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

List<Integer> list=new ArrayList<>();

Set<Integer> set= new HashSet<>();

int n=in.nextInt();

list.add(n);

set.add(n);

while(set.size()!=0){

String s=in.next();

String[] root = s.split(":");

int rt=Integer.parseInt(root[0]);

if(set.contains(rt)){

set.remove(rt);

}

else{

set.add(rt);

}

int lch=Integer.parseInt(root[1].substring(0, root[1].indexOf("|")));

int rch=Integer.parseInt(root[1].substring(root[1].indexOf("|")+1,root[1].length()));

if(lch!=-1){

list.add(lch);

set.add(lch);

}

if(rch!=-1){

list.add(rch);

set.add(rch);

}

}

//List<Integer> tem=new ArrayList<>();

//tem.add(list.get(0));

zhong(list,0);

for(int i=0;i<tem.size()-1;i++){

//System.out.println(tem.get(i));

if(tem.get(i)>tem.get(i+1)){

System.out.println(0);

return;

}

}

System.out.println(1);

}

public static void zhong(List<Integer> list,int i){

int l=(i+1)*2-1;

int r=(i+1)*2;

if(i>=list.size()){

return;

}

if(i>=list.size()){

return;

}

if(l<list.size()){

zhong(list,l);

}

tem.add(list.get(i));

if(r<list.size()){

zhong(list,r);

}


}

}


2017-09-20 11:19
1

反正是看中序,用vector保存,每一次找到父节点,把左右子节点插在父节点两遍就行了,最后看是不是从小到大

2017-09-20 11:21

我跟你一样啊,不知道如何解决输入的问题 ,已经写出来了 ,就是不知道输入怎么解决 。。。。。。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;


/*
 * 
5
5:4|7
4:3|8
7:2|-1
3:-1|-1
8:-1|-1
2:-1|-1
 * */
public class Main_2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<Integer, Integer[]> map = new HashMap<>();
		String s = br.readLine();
		Integer rootval = Integer.parseInt(s.charAt(0) + "");
		String str = null;
		while((str = br.readLine()) != null){
			
			Integer temp1 = Integer.parseInt(str.charAt(0) + "");
			Integer[] temp2 = new Integer[2];
			
			int startIndex = str.indexOf(":")+1;
			int endIndex = str.indexOf("|");
			String s1 = str.substring(startIndex, endIndex);
			String s2 = str.substring(endIndex+1);
			
			
			temp2[0] = Integer.parseInt(s1);
			System.out.println(temp2[0]);
			temp2[1] = Integer.parseInt(s2);
			System.out.println(temp2[1]);
			map.put(temp1, temp2);
		}

		TreeNode root = creatTree(rootval, map);
		ArrayList<Integer> arr = new ArrayList<>();
		inOrderTraversal(root, arr);
		
		boolean flag = isOrdered(arr);
		
		if(flag)
			System.out.println(1);
		else
			System.out.println(0);
	}
	public static TreeNode creatTree(Integer rootVal, HashMap<Integer, Integer[]> map){
		LinkedList<TreeNode> queue = new LinkedList<>();  // 队列
		TreeNode root = new TreeNode(rootVal);  //构造根节点
		
		queue.add(root);
		
		while(!queue.isEmpty()){
			TreeNode node = queue.poll();
			Integer[] values = map.get(node);
			if(values[0] != -1){  //有左儿子
				TreeNode leftChild = new TreeNode(values[0]);
				node.left = leftChild;
				queue.add(leftChild);
			}
			if(values[1] != -1){  //有右儿子
				TreeNode rightChild = new TreeNode(values[1]);
				node.right = rightChild;
				queue.add(rightChild);
			}
		}
		return root;
	}
	
	public static void inOrderTraversal(TreeNode root, ArrayList<Integer> arr){
		if(root == null)
			return;
		inOrderTraversal(root.left, arr);
		arr.add(root.val);
		inOrderTraversal(root.right, arr);
	}
	public static boolean isOrdered(ArrayList<Integer> arr){
		int temp = arr.get(0);
		for (int i = 1; i < arr.size(); i++) {
			if(temp < arr.get(i))
				temp = arr.get(i);
			else
				return false;
		}
		return true;
	}
}

class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val){
		this.val = val;
	}
}


2017-09-20 11:22


                Scanner sc=new Scanner(System.in);
		int rt=Integer.parseInt(sc.nextLine());
		Pattern p=Pattern.compile("[:|]");
		String[]a= p.split(sc.nextLine());
		for(int i=0;i<a.length;i++) {
			System.out.println(a[i]);
		}


2017-09-20 11:30
先用leftmap, rightmap分别存储左右儿子值;
private static Map<Integer, Integer> leftmap = new HashMap<Integer, Integer>();
private static Map<Integer, Integer> leftmap = new HashMap<Integer, Integer>();
树结构 public static class TreeNode{
                            int val;
                            TreeNode left;
                            TreeNode right;
                            TreeNode(int val) { this.val = val;}
                      }
建立根节点  root = new TreeNode(val);
获得树 getTree(root);
public  void getTree(TreeNode root){
        if (leftmap.containsKey(root.val)){
            if (leftmap.get(root.val) != -1){
                root.left = new TreeNode(leftmap.get(root.val));
                getTree(root.left);
            }
            if (rightmap.get(root.val) != -1){
                root.right = new TreeNode(rightmap.get(root.val));
                getTree(root.right);
            }
        }
    }


2017-09-20 11:30
1
一只菜鸡 回复 一只菜鸡

这就可以保留输入了

2017-09-20 11:31
coder_YVFEK326 回复 一只菜鸡

能取出每次输入的根节点左右儿子的值,但是并不知道有多少次输入啊,也就是说整棵树不知道有多少个节点


2017-09-20 11:37
添加回复
回到顶部