输入包含多组测试数据,每组测试数据两行。 第一行,一个数字N(N<=100),表示待插入的节点数。 第二行,N个互不相同的正整数,表示要顺序插入节点的关键字值,这些值不超过10^8。
输出共N行,每次插入节点后,该节点对应的父亲节点的关键字值。
5 2 5 1 3 4
-1 2 2 5 3
import java.util.*; public class Main { public static void main(String[] args) { Scanner in=new Scanner (System.in); int num; while(in.hasNext()==true) { num=in.nextInt(); tree t=new tree(); t.t=null; int i; for(i=1;i<=num;i++) { int key=in.nextInt(); System.out.println(insert(t,key)); } } in.close(); } public static int search(bitree t,bitree parent,int key,tree g) { if(t==null) { g.t=parent; return 0; } else { if(key==t.data) { g.t=t; return 1; } else if(key<t.data) return search(t.lchild,t,key,g); else return search(t.rchild,t,key,g); } } public static int insert(tree g,int key) { tree k=new tree(); k.t=null; bitree s; if(search(g.t, null, key, k)==1) return k.t.data; else { s=new bitree(); s.data=key; s.lchild=s.rchild=null; if(k.t==null) { g.t=s; return -1; } else if(key<k.t.data) k.t.lchild=s; else k.t.rchild=s; return k.t.data; } } } class bitree { int data; bitree lchild,rchild; } class tree { bitree t; }
import java.util.Scanner; public class Main { static class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; } } static void creat(TreeNode root, int value){ if (value<root.val){ if (root.left==null) { root.left = new TreeNode(value); System.out.println(root.val); } else creat(root.left,value); }else { if (root.right==null){ root.right= new TreeNode(value); System.out.println(root.val); }else creat(root.right,value); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()){ int n = scanner.nextInt(); TreeNode root = new TreeNode(scanner.nextInt()); System.out.println("-1"); for (int i = 1; i < n; i++) { creat(root,scanner.nextInt()); } } } }