package com.kali.structure.binarytree.tree;

/**
 * 依据给定序列arr，构建一棵二叉排序树
 */
public class TestBinary {
    public static void main(String[] args) {
        //给定序列
        int[] arr = {50,66,60,26,21,30,70,68};
        BST bst = new BST();
        bst.createBst(arr);
        System.out.println("\n先序遍历");
        bst.preOrder(bst.root);
        System.out.println("\n中序遍历");
        bst.inOrder(bst.root);
        System.out.println("\n后序遍历");
        bst.postOrder(bst.root);
    }
}

/**
 * 排序二叉树
 */
class BST{
    public Node root;

    /*构建二叉排序树*/
    public void createBst(int[] tree){
        int i = 0;
        while (i < tree.length){
            insert(root,tree[i]);
            i ++;
        }

    }

    /*插入节点*/
    public void insert(Node node,int n){
        Node var = new Node(n);
        if(node == null){
            this.root = var;
            return;
        }
        if(node.var > n){
            if(node.left == null){
                node.left = var;
                return;
            }
            insert(node.left,n);
        }else if(node.var < n){
            if(node.right == null){
                node.right = var;
                return;
            }
            insert(node.right,n);
        }else{
            System.out.println(n + "已存在!");
        }
    }

    /*先序遍历*/
    public void preOrder(Node root){
        if(root != null){
            visitNode(root);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    /*中序遍历*/
    public void inOrder(Node root){
        if(root != null){
            inOrder(root.left);
            visitNode(root);
            inOrder(root.right);
        }
    }

    /*后续遍历*/
    public void postOrder(Node root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            visitNode(root);
        }
    }

    public void visitNode(Node node){
        System.out.print(node.toString() + " ");
    }
}

class Node{
    public Node left;
    public Node right;
    public int var;

    public Node(int var) {
        this.var = var;
    }

    @Override
    public String toString() {
        return " " + var;
    }
}

测试结果：