image.png

    1. package com.atguigu.binarysorttree;
    3. /**
    4.  * 二叉排序树
    5.  *
    6.  * @author Dxkstart
    7.  * @create 2022-04-10-15:48
    8.  */
    9. public class BinarySortTreeDemo {
    10.     public static void main(String[] args) {
    12.         int[] arr = new int[]{7,3,10,12,5,1,9};
    14.         BinarySortTree binarySortTree = new BinarySortTree();
    16.         // 向树中添加
    17.         for (int i = 0; i < arr.length; i++) {
    18.             binarySortTree.add(new Node(arr[i]));
    19.         }
    21.         // 遍历
    22.         binarySortTree.infixOrder();
    24.     }
    25. }
    27. // 创建二叉排序树
    28. class BinarySortTree {
    30.     private Node root;
    32.     // 添加节点的方法
    33.     public void add(Node node) {
    34.         // 如果是空树
    35.         if (root == null) {
    36.             root = node;
    37.         } else {
    38.             root.add(node);
    39.         }
    40.     }
    42.     // 中序遍历
    43.     public void infixOrder() {
    44.         if (root != null) {
    45.             root.infixOrder();
    46.         }else {
    47.             System.out.println("此二叉排序树为空");
    48.         }
    49.     }
    51. }
    54. class Node {
    56.     int value;
    57.     Node left;
    58.     Node right;
    60.     public Node(int value) {
    61.         this.value = value;
    62.     }
    64.     // 添加节点的方法
    65.     public void add(Node node) {
    67.         if (node == null) {
    68.             return;
    69.         }
    71.         // 判断传入的节点的值，和当前子树的根节点的值的关系
    72.         if (node.value < this.value) {
    73.             // 如果当前节点的左节点为空
    74.             if (this.left == null) {
    75.                 // 直接将该节点挂在this节点的左边
    76.                 this.left = node;
    77.                 return;
    78.             } else {
    79.                 // 继续向左递归
    80.                 this.left.add(node);
    81.             }
    82.             // 当前节点大于this节点的值
    83.         } else if (node.value > this.value) {
    84.             // 如果this节点的右节点为空
    85.             if (this.right == null) {
    86.                 // 直接将该节点挂在this节点的右边
    87.                 this.right = node;
    88.                 return;
    89.             } else {
    90.                 //继续向右递归
    91.                 this.right.add(node);
    92.             }
    93.         }
    95.     }
    98.     // 中序遍历
    99.     public void infixOrder() {
    100.         if (this.left != null) {
    101.             // 向左递归
    102.             this.left.infixOrder();
    103.         }
    105.         // 中间节点
    106.         System.out.println(this.value);
    108.         if (this.right != null) {
    109.             // 向右递归
    110.             this.right.infixOrder();
    111.         }
    112.     }
    115.     @Override
    116.     public String toString() {
    117.         return "Node{" +
    118.                 "value=" + value +
    119.                 '}';
    120.     }
    121. }

    image.png