首页 > 试题广场 >

二叉排序树

[编程题]二叉排序树
  • 热度指数：47563 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

输入描述:
输入第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数。


输出描述:
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个换行。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
示例1

输入

5
1 6 5 9 8

输出

1 6 5 9 8 
1 5 6 8 9 
5 8 9 6 1
算法知识视频讲解
添加回答
Java
LHC0512头像 LHC0512
Java 解法 ，清晰 
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();
        }
    }
}


发表于 2020-03-18 09:45:08 回复(0)
Java
鸿燕藏锋头像 鸿燕藏锋
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;
    }
} 

}

发表于 2017-05-30 16:19:37 回复(0)
Java
凹凸的记忆头像 凹凸的记忆

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;
    }
}

}

发表于 2017-04-22 11:32:53 回复(0)
Java
现实与梦幻交杂的狂想曲头像 现实与梦幻交杂的狂想曲 
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;
		}
	}
	
}


发表于 2017-04-09 19:09:20 回复(0)
Java
詆調壹點头像 詆調壹點 
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;
		}
	}
}

发表于 2017-02-28 23:17:15 回复(1)
Java
年少如歌头像 年少如歌 
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 + " ");
        }
    }
}
编辑于 2017-01-17 10:17:28 回复(0)
提交观点

问题信息

树 排序
难度：
8条回答 21345浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉排序树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号