二叉排序树的创建和遍历

快来打我* 2021-07-24 23:28 390阅读 0赞

# 一 二叉排序树的引入  #

有一个数列 (7, 3, 10, 12, 5, 1, 9)，要求能够高效的完成对数据的查询和添加。

有以下几种解决方案。

## 1 使用数组 ##

a 数组未排序情况

优点：直接在数组尾添加，速度快。

缺点：查找速度慢。

b 数组已排序情况

优点：可以使用二分查找，查找速度快。

缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。

## 2 使用链式存储-链表 ##

不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。

以上解决方案都不是最优解决方案。

> 使用二叉排序树可以弥补上面方案的不足。

# 二 二叉排序树介绍 #

二叉排序树：BST(Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点。

比如：针对前面的数据 (7, 3, 10, 12, 5, 1, 9) ，对应的二叉排序树见下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 三 二叉排序树创建和遍历 #

## 1 需求 ##

一个数组创建成对应的二叉排序树，并使用中序遍历二叉排序树。

比如: 数组为 Array(7, 3, 10, 12, 5, 1, 9) ， 创建成对应的二叉排序树为 :

![20210322212200928.png][]

## 2 代码 ##

package com.atguigu.binarysorttree;
    
    /**
    * @className: BinarySortTreeDemo
    * @description: 二叉排序树
    * @date: 2021/3/22
    * @author: cakin
    */
    public class BinarySortTreeDemo {
        /**
         * 功能描述：二叉排序树测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/3/22
         */
        public static void main(String[] args) {
            int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
            BinarySortTree binarySortTree = new BinarySortTree();
            // 循环的添加结点到二叉排序树
            for (int i = 0; i < arr.length; i++) {
                binarySortTree.add(new Node(arr[i]));
            }
            // 中序遍历二叉排序树
            System.out.println("中序遍历二叉排序树：");
            binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
        }
    }
    
    /**
    * @className: BinarySortTreeDemo
    * @description: 二叉排序树
    * @date: 2021/3/22
    * @author: cakin
    */
    class BinarySortTree {
        // 根节点
        private Node root;
    
        public Node getRoot() {
            return root;
        }
    
        /**
         * 功能描述：添加结点
         *
         * @param node 节点
         * @author cakin
         * @date 2021/3/22
         */
        public void add(Node node) {
            if (root == null) {
                root = node; // 如果root为空则直接让root指向node
            } else {
                root.add(node);
            }
        }
    
        /**
         * 功能描述：中序遍历
         *
         * @author cakin
         * @date 2021/3/22
         */
        public void infixOrder() {
            if (root != null) {
                root.infixOrder();
            } else {
                System.out.println("二叉排序树为空，不能遍历");
            }
        }
    }
    
    /**
    * @className: Node
    * @description: 节点
    * @date: 2021/3/22
    * @author: cakin
    */
    class Node {
        // 节点值
        int value;
        // 左子树根节点
        Node left;
        // 右子树根节点
        Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "Node [value=" + value + "]";
        }
    
        /**
         * 功能描述：添加节点到二叉排序树
         *
         * @param node 节点
         * @author cakin
         * @date 2021/3/22
         */
        public void add(Node node) {
            if (node == null) {
                return;
            }
    
            // 传入的结点的值小于当前子树的根结点的值
            if (node.value < this.value) {
                // 当前结点左子树根结点为null
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 递归的向左子树添加
                    this.left.add(node);
                }
            } else { // 传入的结点的值大于当前子树的根结点的值
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 递归的向右子树添加
                    this.right.add(node);
                }
            }
        }
    
        /**
         * 功能描述：中序遍历
         *
         * @author cakin
         * @date 2021/3/22
         */
        public void infixOrder() {
            if (this.left != null) {
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.infixOrder();
            }
        }
    }

## 3 测试 ##

中序遍历二叉排序树：
    Node [value=1]
    Node [value=2]
    Node [value=3]
    Node [value=5]
    Node [value=7]
    Node [value=9]
    Node [value=10]
    Node [value=12]

## 4 说明 ##

二叉排序树的中序遍历结果是排序的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/ad1bde8588d44e0e9c52a1e73655c633.png
[20210322212200928.png]: /images/20210724/19d5ca2d9b2e443f88f9cfd0144e847d.png