Java实现二叉查找树

树是一种非线性的数据结构，相对于线性的数据结构(数组，链表)来说，树的运行效率更高

树

树的分类有很多，在此文中，我们就讲述简单的二叉树。

• 每个节点不能多余两个儿子
• 一棵树至少有一个节点
• 一棵树是由一个数据域和两个指针组成

树节点定义

public class TreeNode {

    private TreeNode leftChild;//左孩子
    private TreeNode rightChild;//右孩子
    private int value;

    public TreeNode() {
    }

    public TreeNode(int value) {
        this.value = value;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

二叉搜索树

假设我们有一个数组： int[]arrays={3,2,1,4,5};

那么创建二叉树的步骤是这样的：

• 首先将3作为根节点

  
  第一步.png

• 随后2进来了，我们跟3做比较，比3小，那么放在3的左边

  
  第二步.png

• 随后1进来了，我们跟3做比较，比3小，那么放在3的左边，此时3的左边有2了，因此跟2比，比2小，放在2的左边

  
  第三步.png

• 随后4进来了，我们跟3做比较，比3大，那么放在3的右边

  
  第四步.jpg

• 随后5进来了，我们跟3做比较，比3大，那么放在3的右边，此时3的右边有4了，因此跟4比，比4大，放在4的右边

  
  第五步.jpg

/**
 * 二叉搜索树
 */
public class BinaryTree {

    private TreeNode root;
    private int size;

    public BinaryTree() {
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 动态创建二叉树
     * @param value
     */
    public void createTree(int value){
        TreeNode newTreeNode = new TreeNode(value);
        if(root == null){
            root = newTreeNode;
        }else{
            while (root != null){
                if(value > root.getValue()){
                    if(root.getRightChild() == null){
                        root.setRightChild(newTreeNode);
                        return;
                    }else{
                        root = root.getRightChild();
                    }
                } else{
                    if(root.getLeftChild() == null){
                        root.setLeftChild(newTreeNode);
                        return;
                    }else{
                        root = root.getLeftChild();
                    }
                }
            }
        }
    }


    /**
     * 先序遍历
     * @param treeNode
     */
    public void firstTraverseBTree(TreeNode treeNode){
        if ( treeNode != null){
            System.out.println(""+treeNode.getValue());

            firstTraverseBTree(treeNode.getLeftChild());
            firstTraverseBTree(treeNode.getRightChild());
        }
    }

    /**
     * 中序遍历
     * @param treeNode
     */
    public void midTraverseBtrr(TreeNode treeNode){
        if ( treeNode != null){
            firstTraverseBTree(treeNode.getLeftChild());

            System.out.println(""+treeNode.getValue());

            firstTraverseBTree(treeNode.getRightChild());
        }
    }

    /**
     * 后序遍历
     * @param treeNode
     */
    public void lastTraverseBtrr(TreeNode treeNode){
        if ( treeNode != null){
            firstTraverseBTree(treeNode.getLeftChild());
            firstTraverseBTree(treeNode.getRightChild());
            System.out.println(""+treeNode.getValue());
        }
    }
}