本文共 6237 字，大约阅读时间需要 20 分钟。

package treeplay.tree;import java.util.LinkedList;import java.util.List;import static java.lang.Math.max;/** * @Author lyr * @create 2020/6/30 13:20 */public class SimpleBstTree implements Tree {
       @Override    public void add(int value) {
           insert(value);    }    @Override    public boolean contains(int value) {
           return find(value);    }    private static class Node {
           private int value;        private Node leftChild;        private Node rightChild;        public Node(int v) {
               this.value = v;        }        @Override        public String toString() {
               return "Node={" + this.value + "}";        }    }    private Node root;    private boolean isEmpty() {
           return this.root == null;    }    public void insert(int value) {
           var node = new Node(value);        if (isEmpty()) {
               this.root = node;            return;        }        var current = root;        while (true) {
               if (value < current.value) {
                   if (current.leftChild == null) {
                       current.leftChild = node;                    break;                }                current = current.leftChild;            } else {
                   if (current.rightChild == null) {
                       current.rightChild = node;                    break;                }                current = current.rightChild;            }        }    }    public boolean find(int value) {
           var current = root;        while (current != null) {
               if (value < current.value) {
                   current = current.leftChild;            } else if (value > current.value) {
                   current = current.rightChild;            } else {
                   return true;            }        }        return false;    }    private void traversePreOrder(Node root) {
           if (root == null) {
               return;        }        System.out.print(root.value + " -> ");        traversePreOrder(root.leftChild);        traversePreOrder(root.rightChild);    }    private void traverseInOrder(Node root) {
           if (root == null) {
               return;        }        traverseInOrder(root.leftChild);        System.out.print(root.value + " -> ");        traverseInOrder(root.rightChild);    }    public void traversePreOrderPrint() {
           traversePreOrder(root);        System.out.println();    }    public void traverseInOrderPrint() {
           traverseInOrder(root);        System.out.println();    }    /**     * @return 1+max(height(left),height(right))     */    @Override    public int height() {
           return height(root);    }    private int height(Node root) {
           if (root == null) return -1;        if (root.leftChild == null && root.rightChild == null) {
               return 0;        }        return max(height(root.leftChild), height(root.rightChild)) + 1;    }    public int minimum() {
           if (root == null) {
               throw new IllegalStateException();        }        var current = root;        while (current != null) {
               if (current.leftChild == null) {
                   return current.value;            }            current = current.leftChild;        }        return Integer.MIN_VALUE;    }    private boolean isLeaf(Node node) {
           return node.leftChild == null && node.rightChild == null;    }    @Override    public boolean equals(Object obj) {
           if (this == obj) {
               return true;        }        if (obj == null) return false;        if (obj instanceof SimpleBstTree) {
               return equals(((SimpleBstTree) obj).root, this.root);        }        return false;    }    private boolean equals(Node first, Node second) {
           if (first == null && second == null) return true;        if (first != null && second != null) {
               return first.value == second.value                    && first.leftChild == second.leftChild                    && first.rightChild == second.rightChild;        }        return false;    }    public boolean isBinarySearchTree() {
           return isBinarySearchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);    }    private boolean isBinarySearchTree(Node root, int min, int max) {
           if (root == null) return true;        if (root.value < min || root.value > max) {
               return false;        }        return isBinarySearchTree(root.leftChild, min, root.value - 1)                && isBinarySearchTree(root.rightChild, root.value, max);    }    private List
   
     getNodesAtDistance(int distance) {
           var list = new LinkedList
    
     ();        printNodesAtDistance(root, distance, list);        return list;    }    public void printNodesAtDistance(Node root, int distance, List
     
       list) {
           if (root == null) return;        if (distance == 0) {
               list.add(root.value);            return;        }        printNodesAtDistance(root.leftChild, distance - 1, list);        printNodesAtDistance(root.rightChild, distance - 1, list);    }    public void levelOrderTraversePrint() {
           var h = height();        for(int i=0;i<=h;++i) {
               var list = getNodesAtDistance(i);            for(var value:list) {
                   System.out.print(value+" ->");            }            System.out.println();        }    }}
     
    
   

import treeplay.tree.SimpleBstTree;/** * @Author lyr * @create 2020/6/30 13:11 */public class Main {
       public static void main(String[] args) {
           var tree = new SimpleBstTree();        tree.add(-1);        tree.add(41);        tree.add(-100);        tree.add(-100);        tree.add(-100);        // tree.add(10);        // tree.add(2);        // tree.add(3);        //        // tree.add(2);        tree.traverseInOrderPrint();        System.out.println(                tree.find(3)        );        // tree.traversePreOrderPrint();        System.out.println(tree.height());        System.out.println(tree.minimum());        System.out.println(tree.isBinarySearchTree());       tree.levelOrderTraversePrint();    }    // public static int factorial(int n) {
       //     if(n<=1)return 1;    //     return n*(factorial(n-1));    // }}

转载地址：http://ahuzi.baihongyu.com/