数据结构与算法-树-二分搜索树(一)

二分搜索树

今天我们尝试构建一颗二分搜索树，很多同学只有理论，并没有对树有其编码实践。通过一步步的实现一颗二分搜索树，加深对数据结构树的理解。
二分搜索树，又名二分排序树，有人也叫它二分查找树。

特点

二分搜索树是二叉树，每个节点的值大于所有左子树节点的值；小于所有右子树节点的值。

每一课子树都是二分搜索树。

二分搜索树java实现

定义树中的节点

public class Node<E>{
    public  E data;
    public Node<E> left;
    public Node<E> right;

    public Node(E data) {
        this.data = data;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    public Node<E> getLeft() {
        return left;
    }

    public void setLeft(Node<E> left) {
        this.left = left;
    }

    public Node<E> getRight() {
        return right;
    }

    public void setRight(Node<E> right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

构建树模型

第一种方式

使用递归的方式插入节点，构建二分搜索树模型

public class BinaryTree<E extends Comparable<E>> {
    private int size; //定义树中的节点数量


    public Node<E> insert(Node<E> root, E data) {
        if (root == null) {
            root = new Node<>(data);
            size++;
            return root;
        }
        if (data.compareTo(root.data) < 0) {
            root.left = insert(root.left, data);
        }
        if (data.compareTo(root.data) > 0) {
            root.right = insert(root.right, data);
        }
        return root;
    }

测试程序

Node<Integer> root = new Node<>(35);

BinaryTree<Integer> bst = new BinaryTree<>();
bst.insert(root, 32);
bst.insert(root, 12);
bst.insert(root, 55);
bst.insert(root, 10);
bst.insert(root, 77);
bst.insert(root, 11);
bst.insert(root, 6);
bst.insert(root, 72);
bst.insert(root, 53);

new TreePrint<Integer>().print(root);

第二种方式

使用循环的方式检查是否存在节点，如果没有节点则添加节点。

public class BinaryTreex<E extends Comparable<E>> {
    private Node<E> root;

    public BinaryTreex(E data) {
        this.root = new Node<>(data);
    }

    public Node<E> getRoot(){
        return this.root;
    }

    public void insert(E data) {
        Node<E> currNode = root;

        while (currNode != null) {
            if (data.compareTo(currNode.data) > 0) {
                if (currNode.right == null) {
                    currNode.right = new Node<>(data);
                    return;
                }
                currNode = currNode.right;
            } else {
                if (currNode.left == null) {
                    currNode.left = new Node<>(data);
                    return;
                }
                currNode = currNode.left;
            }
        }
    }
}

运行结构

附录：图形打印二叉树

参考引用来自：https://blog.csdn.net/m0_37550986/article/details/126013196。稍作修改

我们采用中序方式遍历所有节点，使用层序方式从上到下打印节点。

package com.ffyc.tree.bst;

import java.util.*;

/**
 * 中序图形效果打印
 *
 * @param <E>
 */
public class TreePrint<E> {
    private final List<Node<E>> mid = new ArrayList<>();//记录bst树的节点
    private final Map<Node<E>, Integer> map = new HashMap<>();//记录节点及位置

    private Queue<E> queue = new ArrayDeque<>();
    private Node<E> root;

    public TreePrint() {
    }

    public TreePrint(Node<E> root) {
        this.root = root;
    }

    /**
     * 中序遍历
     *
     * @param root 树的根节点
     */
    public void inOrder(Node<E> root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        mid.add(root);
        inOrder(root.right);
    }

    /**
     * 使用Map记录节点及位置
     *
     * @param root
     */
    public void init(Node<E> root) {
        if (root == null) {
            return;
        }
        inOrder(root);
        for (int i = 0; i < mid.size(); i++) {
            map.put(mid.get(i), i);
        }
    }

    /**
     * 打印同一层的节点,使用|线和值进行拼接打印
     *
     * @param nodes
     */
    void printLevelNodes(List<Node<E>> nodes) {
        StringBuilder VLine = new StringBuilder();
        StringBuilder dataLine = new StringBuilder();
        StringBuilder line = new StringBuilder();
        int lastNodeIndex = 0;
        int lastRightIndex = 0;

        for (Node<E> node : nodes) {
            int x = map.get(node);
            String addEmpty = getEmpty(x - lastNodeIndex);
            lastNodeIndex = x;
            VLine.append(addEmpty).append("|");//竖线拼接
            dataLine.append(addEmpty).append(node.data); //值拼接

            Node<E> left = node.left;
            Node<E> right = node.right;
            String leftLine = null;
            String rightLine = null;

            int leftIndex = -1;
            int rightIndex = -1;
            if (left != null) {
                leftIndex = map.get(left);
                leftLine = getLineToChildren(x - leftIndex);
            }
            if (right != null) {
                rightIndex = map.get(right);
                rightLine = getLineToChildren(rightIndex - x);
            }

            String curLine = (leftLine == null ? "" : leftLine) + "|" + (rightLine == null ? "" : rightLine);
            if (leftLine == null && rightLine == null) curLine = "";
            //线段之间的间隔
            int dif = (leftIndex == -1 ? x : leftIndex) - lastRightIndex;
            String difEmpty = getEmpty(dif);
            line.append(difEmpty).append(curLine);//拼接线段
            lastRightIndex = rightIndex == -1 ? x : rightIndex;
        }
        System.out.println(VLine + "\n" + dataLine + "\n" + line);
    }

    String getEmpty(int x) {
        StringBuilder empty = new StringBuilder();
        for (int i = 0; i < x; i++) {
            empty.append("\t");
        }
        return empty.toString();
    }


    //链接子线段的长度
    String getLineToChildren(int end) {
        StringBuilder line = new StringBuilder();
        if (end == 0) return line.toString();
        for (int i = 0; i < end; i++) {
            line.append("____");
        }
        return line.toString();
    }

    /**
     * 扫描每一行中每一个节点的左右节点
     *
     * @param lineNodes 每一行的节点
     */
    public void topToDownLevelPrint(List<Node<E>> lineNodes) {
        if (lineNodes.isEmpty()) return;

        printLevelNodes(lineNodes);//打印同一层的节点

        List<Node<E>> children = new ArrayList<>();  //记录当前节点下的所有子节点
        //记录当前节点下的所有左右节点
        for (Node<E> currentNode : lineNodes) {
            if (currentNode.left != null) children.add(currentNode.left);
            if (currentNode.right != null) children.add(currentNode.right);
        }
        topToDownLevelPrint(children);//递归打印下一层节点
    }
    
    /**
     *  调用此方法完成二分搜索树打印
     *  @param root : 根节点
     */
    public void print(Node<E> root) {
        init(root);
        topToDownLevelPrint(new ArrayList<Node<E>>() {{
            add(root);
        }});
    }
}