实现思路

• 如果左子树不为空，那么左子树上的所有值都均小于它的根节点的值
• 如果右子树不为空，那么右子树上的所有值都均大于或等于它的根节点的值
• 左，右子树也为二叉排序树

二叉树节点定义

• 当前节点值
• 当前节点的左节点
• 当前节点的右节点

代码如下,set与get方法省略

 /**
     * 当前节点的值
     */
    T data;
    /**
     * 当前节点的左节点
     */
    Node left;
    /**
     * 当前节点的右节点
     */
    Node right;

二叉树实现

• 排序二叉树构建实现思路：

判断当前节点与新增的节点的大小，没有增加上，则变化当前节点为遍历的节点，继续遍历即可

• 前，中，后排序，使用递归的方式(前中后都是根据root来的)
• 层序遍历采用队列

package cn.gxm.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author GXM
 * @date 2019/5/13
 *
 * 排序二叉树相关实现
 */
public class Binarytree {
    private Node<Integer> root;

    public void insert(Integer data){
        Node<Integer> newNode = new Node<Integer>(data);
        if(root == null){
            root = newNode;
            return;
        }

        Node curNode = root;
        while (true){
            //小于当前节点去找左节点
            if((Integer)newNode.data < (Integer) curNode.data){
                if(curNode.left == null){
                    curNode.left = newNode;
                    break;
                }
                curNode = curNode.left;
            }else {
                //大于当前节点或者等于  都找找右节点
                if(curNode.right == null){
                    curNode.right = newNode;
                    break;
                }
                curNode = curNode.right;
            }
        }

    }

    /**
     * 根据数据构建有序二叉树
     * @param arr
     */
    public Node<Integer> buildTree(Integer []arr){
        for (Integer tmp : arr){
            insert(tmp);
        }
        return root;
    }

    /**
     * 前序遍历
     */
    public void preTraversing(Node<Integer> root){
        Node<Integer> cur = root;
        if (cur != null){
            System.out.print(cur.data);
            preTraversing(cur.left);
            preTraversing(cur.right);
        }
    }

    /**
     * 中序遍历
     */
    public void midTraversing(Node<Integer> root){
        Node<Integer> cur = root;
        if (cur != null){
            midTraversing(cur.left);
            System.out.print(cur.data);
            midTraversing(cur.right);
        }
    }

    /**
     * 后序遍历
     */
    public void postTraversing(Node<Integer> root){
        Node<Integer> cur = root;
        if (cur != null){
            postTraversing(cur.left);
            postTraversing(cur.right);
            System.out.print(cur.data);
        }
    }

    /**
     * 层序遍历
     * @param root
     */
    public void SequenceTraversing(Node<Integer> root){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        // 不空就一直取
        while (!queue.isEmpty()){
            // poll以后队列中就没有了，指针移到下一个node上，所以我们这里获取
            Node poll = queue.poll();
            System.out.print(poll.data);
            if(poll.left!=null){
                queue.add(poll.left);
            }
            if(poll.right!=null){
                queue.add(poll.right);
            }
        }
    }


   public static void main(String[] args) {
        Binarytree bt = new Binarytree();
        Node<Integer> root = bt.buildTree(new Integer[]{2, 8, 7, 4, 9, 3, 1, 6, 7, 5});
        System.out.println("前序");
        bt.preTraversing(root);

        System.out.println();
        System.out.println("中序");
        bt.midTraversing(root);

        System.out.println();
        System.out.println("后序");
        bt.postTraversing(root);

        System.out.println();
        System.out.println("层序");
        bt.SequenceTraversing(root);
    }
    }
}

结果

前序
2187436579
中序
1234567789
后序
1356477982
层序
2187947365

构建的有序二叉树如下