1. package com.zhangyong.DataStructures.Tree.BinaryTree;
    3. import com.zhangyong.DataStructures.Queue.ArrayQueue;
    4. import com.zhangyong.DataStructures.Queue.Queue;
    5. import com.zhangyong.DataStructures.Stack.ArrayStack;
    6. import com.zhangyong.DataStructures.Stack.Stack;
    8. /**
    9.  * <p>ClassName:  </p>
    10.  * <p>Description: 二分搜索树 </p>
    11.  * @author zhangyong
    12.  * @version 1.0.0
    13.  * @date 2018/9/11 8:06
    14.  */
    15. public class BinarySearchTree<E extends Comparable<E>> {
    17.     private class Node {
    18.         public E e;
    19.         public Node left, right;
    21.         public Node(E e) {
    22.             this.e = e;
    23.             this.left = null;
    24.             this.right = null;
    25.         }
    27.         //打印根节点及其儿子节点
    28.         @Override
    29.         public String toString() {
    30.             return "Node{" +
    31.                     "e=" + e +
    32.                     ", node.left=" + left.e +
    33.                     ", right=" + right.e +
    34.                     '}';
    35.         }
    36.     }
    38.     //BST根节点
    39.     private Node root;
    40.     //表示存储了多少元素;
    41.     private int size;
    43.     //无参构造器
    44.     public BinarySearchTree() {
    45.         root = null;
    46.         size = 0;
    47.     }
    49.     public int size() {
    50.         return size;
    51.     }
    53.     public boolean isEmpty() {
    54.         return size == 0;
    55.     }
    57.     //向二分搜索树中添加元素
    58.     public void add(E e) {
    59.         root = add(root, e);
    60.     }
    62.     /*public void add(E e) {
    63.         if (root == null) {
    64.             root = new Node(e);
    65.             ++size;
    66.         } else {
    67.             add(root, e);
    68.         }
    69.     }
    70.     //(私有方法)向以node为根的二分搜索树中插入元素e,递归实现;
    71.     private void add(Node node, E e) {
    72.         //元素覆盖
    73.         if (e.equals(node.e)) {
    74.             return;
    75.         } else if (e.compareTo(node.e) < 0 && node.left == null) {
    76.             //左子树为空的话,直接插入;
    77.             node.left = new Node(e);
    78.             ++size;
    79.             return;
    80.         } else if (e.compareTo(node.e) > 0 && node.right == null) {
    81.             node.right = new Node(e);
    82.             ++size;
    83.             return;
    84.         }
    85.         if (e.compareTo(node.e) < 0) {
    86.             add(node.left, e);
    87.         } else {
    88.             add(node.right, e);
    89.         }
    90.     }*/
    91.     //向以node为根的二分搜索树中插入元素e,递归实现;
    92.     private Node add(Node node, E e) {
    93.         //递归结束标识
    94.         if (node == null) {
    95.             ++size;
    96.             return new Node(e);
    97.         }
    98.         if (e.compareTo(node.e) < 0) {
    99.             node.left = add(node.left, e);
    100.         } else {
    101.             node.right = add(node.right, e);
    102.         }
    103.         return node;
    104.     }
    106.     //看二分搜索树中是否包含元素e
    107.     public boolean contains(E e) {
    108.         return contains(root, e);
    109.     }
    111.     //看以Node为根的二分搜索树中是否包含元素e,递归算法;
    112.     private boolean contains(Node node, E e) {
    113.         if (node == null) {
    114.             return false;
    115.         }
    116.         if (e.compareTo(node.e) == 0) {
    117.             return true;
    118.         } else if (e.compareTo(node.e) < 0) {
    119.             return contains(node.left, e);
    120.         } else {
    121.             return contains(node.right, e);
    122.         }
    123.     }
    125.     //二分搜索树的前序遍历,递归算法实现
    126.     public void preOrder() {
    127.         preOrder(root);
    128.     }
    130.     //二分搜索树的前序遍历,非递归算法实现
    131.     public void preOrderNR() {
    132.         if (root == null) {
    133.             return;
    134.         }
    135.         Stack<Node> stack = new ArrayStack<Node>();
    136.         stack.push(root);
    137.         while (!stack.isEmpty()) {
    138.             Node node = stack.pop();
    139.             System.out.print(node.e + " ");
    140.             if (node.right != null) {
    141.                 stack.push(node.right);
    142.             }
    143.             if (node.left != null) {
    144.                 stack.push(node.left);
    145.             }
    146.         }
    147.     }
    148.     //前序遍历以node为根的二分搜索树,递归算法;
    149.     //打印顺序: 根+左+右
    150.     private void preOrder(Node node) {
    151.         if (node == null) {
    152.             return;
    153.         }
    154.         System.out.print(node.e + " ");
    155.         preOrder(node.left);
    156.         preOrder(node.right);
    157.     }
    159.     //中序遍历以node为根节点的二分搜索树,递归算法;
    160.     //打印顺序: 左+根+右
    161.     public void inOrder() {
    162.         inOrder(root);
    163.     }
    165.     public void inOrder(Node node) {
    166.         if (node == null) {
    167.             return;
    168.         }
    169.         inOrder(node.left);
    170.         System.out.print(node.e + " ");
    171.         inOrder(node.right);
    172.     }
    174.     //中序遍历二分搜索树,非递归算法;
    175.     //打印顺序: 左+根+右
    176.     public void inOrderNR() {
    177.         Stack<Node> stack = new ArrayStack<Node>();
    178.         Node node = root;
    179.         while (node != null || !stack.isEmpty()) {
    180.             if (node != null) {
    181.                 stack.push(node);
    182.                 node = node.left;
    183.             } else {
    184.                 node = stack.pop();
    185.                 System.out.print(node.e + " ");
    186.                 node = node.right;
    187.             }
    188.         }
    189.     }
    191.     //后序遍历以node为根节点的二分搜索树,递归算法
    192.     //打印顺序: 左 + 右 + 根
    193.     public void postOrder() {
    194.         postOrder(root);
    195.     }
    197.     /**
    198.      * 后序遍历:递归
    199.      * @param node
    200.      */
    201.     public void postOrder(Node node) {
    202.         if (node == null) {
    203.             return;
    204.         }
    205.         postOrder(node.left);
    206.         postOrder(node.right);
    207.         System.out.print(node.e + " ");
    208.     }
    210.     //后序遍历以node为根节点的二分搜索树,非递归遍历
    211.     //打印顺序: 左+右+根
    212.     public void postOrderNR() {
    213.         ArrayStack<Node> stack = new ArrayStack<Node>();
    214.         Node node = root;
    215.         while (node != null || !stack.isEmpty()) {
    217.         }
    218.     }
    219.     //二分搜索树层序遍历(BFS,广度优先搜索遍历)
    220.     public void levelOrder() {
    221.         if (root == null) {
    222.             return;
    223.         }
    224.         Queue<Node> queue = new ArrayQueue<>();
    225.         queue.enqueue(root);
    226.         while (!queue.isEmpty()) {
    227.             Node node = queue.dequeue();
    228.             System.out.println(node.e);
    229.             if (node.left != null) {
    230.                 queue.enqueue(node.left);
    231.             }
    232.             if (node.right != null) {
    233.                 queue.enqueue(node.right);
    234.             }
    235.         }
    236.     }
    238.     //寻找二叉搜索树的最小值
    239.     public E minimum() {
    240.         if (size == 0) {
    241.             throw new IllegalArgumentException("二叉树为空,无法获取最小值");
    242.         }
    243.         return minimum(root).e;
    244.     }
    246.     //返回以node为根的二分搜索树的最小值的根节点
    247.     private Node minimum(Node node) {
    248.         if (node.left == null) {
    249.             return node;
    250.         }
    251.         return minimum(node.left);
    252.     }
    254.     //寻找二叉搜索树的最大值
    255.     public E maximum() {
    256.         if (size == 0) {
    257.             throw new IllegalArgumentException("二叉树为空,无法查询最大值");
    258.         }
    259.         return maximum(root).e;
    260.     }
    262.     //返回以node为根的二分搜索树的最大值的根节点
    263.     private Node maximum(Node node) {
    264.         if (node.right == null) {
    265.             return node;
    266.         }
    267.         return maximum(node.right);
    268.     }
    270.     //删除掉以Node为根的二分搜索树中的最小节点
    271.     //返回删除节点后新的二分搜索树的根;
    272.     private Node removeMin(Node node) {
    273.         if (node.left == null) {
    274.             //定义临时节点保存右子树
    275.             Node rightNode = node.right;
    276.             // help gc
    277.             node.right = null;
    278.         }
    279.         node.left = removeMin(node.left);
    280.         return node;
    281.     }
    283.     public E removeMin() {
    284.         E minimum = minimum();
    285.         root = removeMin(root);
    286.         return minimum;
    287.     }
    289.     //删除掉以Node为根的二分搜索树中的最大值
    290.     //返回删除节点后新的二分搜索树的根;
    291.     private Node removeMax(Node node) {
    292.         if (node.right == null) {
    293.             Node leftNode = node.left;
    294.             // help gc
    295.             node.left = null;
    296.         }
    297.         node.right = removeMax(node.right);
    298.         return node;
    299.     }
    301.     public E removeMax() {
    302.         E maximum = maximum();
    303.         root = removeMax(root);
    304.         return maximum;
    305.     }
    307.     //从二分搜索树中删除元素为e的节点
    308.     public void remove(E e) {
    309.         root = remove(root, e);
    310.     }
    311.     public Node remove(Node node, E e) {
    312.         if (node == null) {
    313.             return null;
    314.         }
    315.         if (e.compareTo(node.e) < 0) {
    316.             node.left = remove(node.left, e);
    317.             return node;
    318.         } else if (e.compareTo(node.e) > 0) {
    319.             node.right = remove(node.right, e);
    320.             return node;
    321.         } else {
    322.             if (node.left == null) {
    323.                 Node rightNode = node.right;
    324.                 node.right = null;
    325.                 size--;
    326.                 return rightNode;
    327.             }
    328.             if (node.right == null) {
    329.                 Node leftNode = node.left;
    330.                 node.left = null;
    331.                 size--;
    332.                 return leftNode;
    333.             }
    334.             //s为d的后继节点
    335.             Node s = minimum(node.right);
    336.             s.right = removeMin(node.right);
    337.             s.left = node.left;
    338.             return s;
    339.         }
    340.     }
    341.     @Override
    342.     public String toString() {
    343.         StringBuilder sb = new StringBuilder();
    344.         generateBSTString(root, 0, sb);
    345.         return sb.toString();
    346.     }
    348.     //生成以node为根节点,深度为depth的描述二叉树的字符串;
    349.     private void generateBSTString(Node node, int depth, StringBuilder res) {
    350.         if (node == null) {
    351.             res.append(generateDepthString(depth) + "null\n");
    352.             return;
    353.         }
    354.         res.append(generateDepthString(depth) + node.e + "\n");
    355.         generateBSTString(node.left, depth + 1, res);
    356.         generateBSTString(node.right, depth + 1, res);
    357.     }
    359.     private String generateDepthString(int depth) {
    360.         StringBuilder sb = new StringBuilder();
    361.         for (int i = 0; i < depth; i++) {
    362.             sb.append("--");
    363.         }
    364.         return sb.toString();
    365.     }
    367.     public static void main(String[] args) {
    368.         BinarySearchTree<Integer> tree = new BinarySearchTree<>();
    369.         int[] nums = new int[]{
    370.                 5, 3, 6, 8, 4, 2, 7
    371.         };
    372.         /////////////////
    373.         //      5      //
    374.         //    /   \    //
    375.         //   3    6    //
    376.         //  / \    \   //
    377.         // 2  4     8
    378.         //         /
    379.         //        7
    380.         /////////////////
    381.         for (int num : nums) {
    382.             tree.add(num);
    383.         }
    384.         System.out.print("先序遍历二分搜索树:");
    385.         tree.preOrder();
    386.         System.out.println();
    387.         System.out.println("先序遍历二分搜索树非递归实现:");
    388.         tree.preOrderNR();
    389.         System.out.println();
    391.         System.out.println("中序遍历二分搜索树:");
    392.         tree.inOrder();
    393.         System.out.println();
    394.         System.out.print("中序遍历二分搜索树非递归实现:");
    395.         tree.inOrderNR();
    396.         System.out.println();
    398.         System.out.print("后序遍历二分搜索树:");
    399.         tree.postOrder();
    400.         System.out.println();
    401.         System.out.println("后序遍历二分搜索树非递归实现");
    402.         tree.postOrderNR();
    403.         System.out.println();
    404.     }
    405. }