详解二叉搜索树 |

鉴于不经常使用的东西会经常遗忘，于是，总结了一下，记下来，供后续翻阅。

要点：

增
1. 先判断树是否为空，为空则先init树
2. 从根节点遍历，如果大于根节点，找右边，否则找左边，递归，找到left或者right为null的
3. 插入
删
1. left != null 的找前继节点
2. right == null 的找后继节点
改
1. 先删
2. 后加
查
1. 从根节点遍历，如果大于根节点，找右边，否则找左边
2. 找不到的抛异常
前序遍历
1. 根左右
中序遍历
1. 左根右
后续遍历
1. 左右根
层次遍历
1. 引入队列

说明

使用了lombok插件,安装方式：

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <version>1.18.4</version>
    <scope>provided</scope>
</dependency>

源码

BinaryTree.java

import lombok.Data;

/**
 * 定义树结构
 */
@Data
public class BinaryTree {
    // 节点数据
    public int data;

    // 左节点
    public BinaryTree left;

    // 右节点
    public BinaryTree right;

    BinaryTree(int data){
        this.data = data;
    }
}

BinaryTreeImpl.java

import java.util.LinkedList;
import java.util.Queue;

/**
 * 实现二叉搜索树的增删改查 4种遍历
 */
public class BinaryTreeImpl {

    // 根节点
    public static BinaryTree root = null;

    public static Queue<BinaryTree> list = new LinkedList<BinaryTree>();


    /**
     * 初始化树
     */
    public static void init(int data){
        if(root == null){
            root = new BinaryTree(data);
            root.setLeft(null);
            root.setRight(null);
        }
    }

    /**
     * 添加
     * @param data
     */
    public static void add(int data){
        if(root == null){
            init(data);
        }else{
            addNode(root, data);
        }
    }

    /**
     * @param old_data
     * @param new_data
     */
    public static void update(int old_data, int new_data)  {
        try {
            delete(old_data);
            add( new_data);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }


    /**
     * 删除
     * @param data
     */
    public static void delete(int data){
        deleteNode(root, data);
    }

    /**
     *
     * @param binaryTree
     * @param data
     */
    public static void deleteNode(BinaryTree binaryTree, int data){
        //
        try {
            BinaryTree targetTree = findNode(root, data);
            if(targetTree.getLeft() != null){
                findAfter(targetTree);
            }
            if(targetTree.getRight() == null){
                findPre(root, data);
            }
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

    }

    /**
     * 找前继节点
     * @param binaryTree
     */
    public static void findPre(BinaryTree binaryTree, int data){
        if(binaryTree.getRight().getData() == data){
            binaryTree.setRight(null);
        }
        if(binaryTree.getData() > data){
            // left
            findPre(binaryTree.getLeft(), data);
        }
        if(binaryTree.getData() < data){
            // right
            findPre(binaryTree.getRight(), data);
        }
    }

    /**
     * 找后继节点
     * @param binaryTree
     */
    public static void findAfter(BinaryTree binaryTree){
        BinaryTree right = binaryTree.getRight();
        binaryTree.setData(right.getData());
        binaryTree.setRight(right.getRight());
    }

    /**
     * 查找
     * @param data
     */
    public static void find(int data){
        try {
            System.out.println(findNode(root, 3).getData());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }

    /**
     *
     * @param binaryTree
     * @param data
     * @return
     */
    public static BinaryTree findNode(BinaryTree binaryTree, int data) throws Exception{
        // check root first
        if(binaryTree.data == data){
            return binaryTree;
        }
        if(binaryTree.data > data && binaryTree.getLeft() != null){
            // left
            return findNode(binaryTree.getLeft(), data);
        }
        if(binaryTree.data < data && binaryTree.getRight() != null){
            // right
            return findNode(binaryTree.getRight(), data);
        }
        // not found
        throw new Exception("not found: " + data);
    }


    /**
     *
     * @param binaryTree
     * @param data
     * @return
     */
    public static void addNode(BinaryTree binaryTree, int data){
        // Don't consider equality
        if(binaryTree.data > data){
            if(binaryTree.getLeft() == null){
                binaryTree.setLeft(new BinaryTree(data));
            }else{
                addNode(binaryTree.getLeft(), data);
            }
        }else if(binaryTree.data < data){ // put data on right
            if(binaryTree.getRight() == null){
                binaryTree.setRight(new BinaryTree(data));
            }else{
                addNode(binaryTree.getRight(),data);
            }
        }
    }



    /**
     * 前序遍历
     * @param binaryTree
     */
    public static void preTraverse(BinaryTree binaryTree){
        // rules : root left right
        // print root data first
        System.out.println(binaryTree.data);

        if(binaryTree.getLeft() != null){
            preTraverse(binaryTree.getLeft());
        }

        if(binaryTree.getRight() != null){
            preTraverse(binaryTree.getRight());
        }

    }

    /**
     * 中序遍历
     * @param binaryTree
     */
    public static void midTraverse(BinaryTree binaryTree){
        // rules : left root right

        if(binaryTree.getLeft() != null){
            midTraverse(binaryTree.getLeft());
        }

        System.out.println(binaryTree.data);

        if(binaryTree.getRight() != null){
            midTraverse(binaryTree.getRight());
        }

    }

    /**
     * 后序遍历
     * @param binaryTree
     */
    public static void afterTraverse(BinaryTree binaryTree){
        // rules : left right root

        if(binaryTree.getLeft() != null){
            afterTraverse(binaryTree.getLeft());
        }

        if(binaryTree.getRight() != null){
            afterTraverse(binaryTree.getRight());
        }

        System.out.println(binaryTree.data);

    }

    /**
     * 层次遍历
     */
    public static void gradationTraverse(){
        enqueue(root);
        gradationTraverse(list);
    }

    /**
     *
     * @param list
     */
    public static void gradationTraverse(Queue<BinaryTree> list){
        for(;;){
            if(!list.isEmpty()){
                BinaryTree tree = list.poll();
                System.out.println(tree.getData());
                if(tree.getLeft() != null){
                    enqueue(tree.getLeft());
                }
                if(tree.getRight() != null){
                    enqueue(tree.getRight());
                }
            }else {
                break;
            }
        }
    }

    /**
     *
     * @param binaryTree
     */
    public static void enqueue(BinaryTree binaryTree){
        list.add(binaryTree);
    }


    public static void main(String[] args) {

        // 7 3 5 2 6 8 9
        add(7);
        add(3);
        add(5);
        add(2);
        add(6);
        add(8);
        add(9);

//        preTraverse(root);
//        update(3, 2);
//        find(3);
//        System.out.println("------");
        // 这里如果没有自平衡，更新后的树可能不是一个二叉搜索树了
        update(3, 99);
//        preTraverse(root);
//        gradationTraverse();
//        delete(9);
        preTraverse(root);


    }

}

Tags: 算法数据结构

← 如何快速用docker搭建一个php7的开发环境 Linux 如何定位文件锁的问题 →

赏

使用支付宝打赏

使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章