输入第一行包括一个整数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
import java.util.Scanner; public class Main { static class Node { int value; Node left; Node right; Node(int value) { this.value = value; } } // creat 写法一 static void creat1(Node root, int value) { if (value < root.value) { if (root.left == null) root.left = new Node(value); else creat1(root.left, value); } else if (value > root.value) { if (root.right == null) root.right = new Node(value); else creat1(root.right, value); } } // creat 写法二 static Node creat2(Node root,int value){ if (root==null) root=new Node(value); else if (value<root.value) root.left=creat2(root.left,value); else if (value>root.value) root.right=creat2(root.right,value); return root; } static void preOrder(Node root) { if (root != null) { System.out.print(root.value + " "); preOrder(root.left); preOrder(root.right); } } static void inOder(Node root) { if (root != null) { inOder(root.left); System.out.print(root.value + " "); inOder(root.right); } } static void postOrder(Node root) { if (root != null) { postOrder(root.left); postOrder(root.right); System.out.print(root.value + " "); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); Node root = new Node(scanner.nextInt()); for (int i = 1; i < n; i++) creat2(root, scanner.nextInt()); preOrder(root); System.out.println(); inOder(root); System.out.println(); postOrder(root); System.out.println(); } } }
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int[] s=new int[n];
TreeNode temp=null,root=null;
for(int i=0;i<s.length;i++){
int num=sc.nextInt();
if(root==null){
root=new TreeNode(num);
temp=root;
}else{
createTree(temp,new TreeNode(num));
}
}
DLR(root);
System.out.println();
LDR(root);
System.out.println();
LRD(root);
System.out.println();
}
}
private static void LRD(TreeNode root) {
// TODO Auto-generated method stub
if(root!=null){
LRD(root.left);
LRD(root.right);
System.out.print(root.value+" ");
}
}
private static void LDR(TreeNode root) {
// TODO Auto-generated method stub
if(root!=null){
LDR(root.left);
System.out.print(root.value+" ");
LDR(root.right);
}
}
private static void DLR(TreeNode root) {
// TODO Auto-generated method stub
if(root!=null){
System.out.print(root.value+" ");
DLR(root.left);
DLR(root.right);
}
}
private static void createTree(TreeNode temp,TreeNode treeNode) {
// TODO Auto-generated method stub
if(temp.value==treeNode.value){
return;
}else if(treeNode.value<temp.value){
if(temp.left!=null){
temp=temp.left;
createTree(temp,treeNode);
}else{
temp.left=treeNode;
}
}else if(treeNode.value>temp.value){
if(temp.right!=null){
temp=temp.right;
createTree(temp,treeNode);
}else{
temp.right=treeNode;
}
}
}
static class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.value=val;
}
}
}
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Main m = new Main(); while(sc.hasNext()){ int n = sc.nextInt(); Tree[] t = new Tree[n]; for(int i = 0; i < n; i++){ t[i] = m.new Tree(); t[i].setData(sc.nextInt()); } for(int i = 1; i < n; i++){ m.insertTree(t[i], t[0]); } m.outTreeDRL(t[0]); System.out.println(); m.outTreeLDR(t[0]); System.out.println(); m.outTreeLRD(t[0]); System.out.println(); } sc.close(); } public void outTreeDRL(Tree t) { System.out.print(t.getData() + " "); if(t.getLeft() != null){ outTreeDRL(t.getLeft()); } if(t.getRight() != null){ outTreeDRL(t.getRight()); } } public void outTreeLDR(Tree t){ if(t.getLeft() != null){ outTreeLDR(t.getLeft()); } System.out.print(t.getData() + " "); if(t.getRight() != null){ outTreeLDR(t.getRight()); } } public void outTreeLRD(Tree t){ if(t.getLeft() != null){ outTreeLRD(t.getLeft()); } if(t.getRight() != null){ outTreeLRD(t.getRight()); } System.out.print(t.getData() + " "); } public void insertTree(Tree t1, Tree t2){ if(t1.getData() > t2.getData()){ if(t2.getRight() == null){ t2.setRight(t1); }else{ insertTree(t1, t2.getRight()); } }else if(t1.getData() < t2.getData()){ if(t2.getLeft() == null){ t2.setLeft(t1); }else{ insertTree(t1, t2.getLeft()); } } } private class Tree{ private int data; private Tree left; private Tree right; public Tree() { // TODO 自动生成的构造函数存根 data = 0; left = null; right = null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Tree getLeft() { return left; } public void setLeft(Tree left) { this.left = left; } public Tree getRight() { return right; } public void setRight(Tree right) { this.right = right; } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i ++) { arr[i] = sc.nextInt(); } TreeNode root = new TreeNode(arr[0]); for (int i = 1; i < arr.length; i ++) { createBST(root, arr[i]); } DLR(root); System.out.println(); LDR(root); System.out.println(); LRD(root); System.out.println(); } } public static void createBST(TreeNode root, int value) { if(root.value == value) return; if(value < root.value) { if(root.left == null) root.left = new TreeNode(value); else createBST(root.left, value); } else { if(root.right == null) root.right = new TreeNode(value); else createBST(root.right, value); } } public static void DLR(TreeNode root) { if(root != null) { System.out.print(root.value + " "); DLR(root.left); DLR(root.right); } } public static void LDR(TreeNode root) { if(root != null) { LDR(root.left); System.out.print(root.value + " "); LDR(root.right); } } public static void LRD(TreeNode root) { if(root != null) { LRD(root.left); LRD(root.right); System.out.print(root.value + " "); } } static class TreeNode { private int value; private TreeNode left; private TreeNode right; public TreeNode(int value) { this.value = value; } } }
import java.util.Scanner; class BinaryTree{ int val; BinaryTree left; BinaryTree right; BinaryTree(int val){ this.val = val; left = null; right = null; } } public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int[] num = new int[n]; for(int i=0; i<n; i++) num[i] = sc.nextInt(); BinaryTree root = binarySort(num); preOrderTree(root); System.out.println(); inOrderTree(root); System.out.println(); afterOrderTree(root); System.out.println(); } } private static BinaryTree binarySort(int[] num) { if(num == null || num.length == 0) return null; BinaryTree root = new BinaryTree(num[0]); for(int i=1; i<num.length; i++){ if(searchBinaryTree(root, num[i])) { BinaryTree node = new BinaryTree(num[i]); root = insertNode(root, node); } } return root; } private static boolean searchBinaryTree(BinaryTree root, int n){ if(root != null){ if(root.val == n) return false; if(root.val > n) searchBinaryTree(root.left, n); if(root.val < n) searchBinaryTree(root.right, n); } return true; } private static BinaryTree insertNode(BinaryTree root, BinaryTree node){ if(root == null) root = node; else if(node.val < root.val) root.left = insertNode(root.left, node); else root.right = insertNode(root.right, node); return root; } private static void preOrderTree(BinaryTree root) { if(root != null){ System.out.print(root.val + " "); preOrderTree(root.left); preOrderTree(root.right); } } private static void inOrderTree(BinaryTree root) { if(root != null){ inOrderTree(root.left); System.out.print(root.val + " "); inOrderTree(root.right); } } private static void afterOrderTree(BinaryTree root) { if(root != null){ afterOrderTree(root.left); afterOrderTree(root.right); System.out.print(root.val + " "); } } }