java数据结构

树结构

将数据使用数结构储存后 查找十分高效 常见的树结构：二分搜索树、平衡二叉树（AVL）、红黑树、堆、并查集、线段树、Trie（字段树、前缀树）

二叉树

• 二叉树具有天然递归结构
• 每一个节点的左子树也是二叉树、每一个节点的右子节点也是二叉树

public class Node<E> {

    E e;
    Node left;
    Node right;

}

二分搜索树

• 二分搜索树是二叉树
• 每个节点的值要大于其左子节点的所有值，每个节点的值小于其右子节点的所有的值
• 每一个字树也是二分搜索树
• 储存的元素必须有可比较性

public class BST<E extends Comparable<E>> {

    private Node root;
    private int size;

    public BST() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 向二分搜索树中添加元素
     * @param e
     */
    public void add(E e) {
        root = addByRecursive(root, e);
    }

    /**
     * 在二分搜索树中查找指定元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        return containsByRecursive(root, e);
    }


    /**
     * 递归的向node中添加元素e
     * 返回插入新节点后二分搜索树的根
     * @param node
     * @param e
     */
    private Node addByRecursive(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo((E) node.e) < 0) {
            node.left = addByRecursive(node.left, e);
        } else {
            node.right = addByRecursive(node.right, e);
        }
        return node;
    }

    /**
     * 递归的向node中查找元素e
     * @param node
     * @param e
     */
    public boolean containsByRecursive(Node node, E e){
        if(node == null){
            return false;
        }
        if(e.compareTo((E) node.e) == 0){
            return true;
        }else if(e.compareTo((E) node.e) < 0){
            return containsByRecursive(node.left, e);
        }else{
            return containsByRecursive(node.right, e);
        }
    }
}

前序遍历（深度优先）

• 先遍历二叉树的根节点 之后再遍历左右子节点（常使用递归方法进行遍历）

    /**
     * 前序遍历
     */
    public void preOrder(){
        preOrderByRecursive(root);
    }

    /**
     * 递归的前序遍历
     * @param node
     */
    private void preOrderByRecursive(Node node){
        if(node == null){
            return ;
        }
        System.out.println(node.e);
        preOrderByRecursive(node.left);
        preOrderByRecursive(node.right);
    };

中序遍历

• 先遍历二叉树的所有左子树，之后遍历根节点 再遍历所有右节点
• 二分搜索树的中序遍历结果是顺序的（先左 后中 再右）

    /**
     * 中序遍历
     */
    public void inOrder(){
        inOrderByRecursive(root);
    }

    /**
     * 递归的中序遍历
     * @param node
     */
    public void inOrderByRecursive(Node node){
        if(node == null){
            return ;
        }
        inOrderByRecursive(node.left);
        System.out.println(node.e);
        inOrderByRecursive(node.right);
    }

后序遍历

• 先遍历二叉树的所有左子树，再遍历所有右节点 之后遍历根节点
• 先释放的左右子节点 最后释放根节点

    /**
     * 后序遍历
     */
    public void psotOrder(){
        psotOrderByRecursive(root);
    }

    /**
     * 递归的后序遍历
     * @param node
     */
    public void psotOrderByRecursive(Node node){
        if(node == null){
            return ;
        }
        psotOrderByRecursive(node.left);
        psotOrderByRecursive(node.right);
        System.out.println(node.e);
    }

层序遍历（广度优先）

• 针对二叉树从根节点开始 一层一层的解析（使用队列工具）
• 常用于算法设计中-最短路径、更快的找到问题的解

    /**
     * 层序遍历
     */
    public void levelOrder(){
        Queue<Node> q = new LinkedList();
        q.add(root);
        while (!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);
            if(cur.left != null){
                q.add(cur.left);
            }
            if(cur.right != null){
                q.add(cur.right);
            }
        }
    }

删除最小的元素

    /**
     * 删除最小元素
     * @return
     */
    public E  removeMin(){
        E ret = minnum();
        root = removeMinByRecursive(root);
        return ret;
    }

    /**
     * 递归删除最小元素  返回删除元素后的根
     * @param node
     */
    private Node removeMinByRecursive(Node node) {
        if(node.left == null){
            Node rightNode = node.right;
            node.left = null;
            size --;
            return rightNode;
        }
        node.left = removeMinByRecursive(node.left);
        return node;
    }

删除任意元素

• 删除只有左子数 或 只有右子树的节点很简单：直接同上删除最小元素或最大元素即可

• 删除有左右子数的 方法一：
  1.先找到节点的前驱值s=max(d -> left) 即当前节点的左子树的最大节点
  2.把前驱值替换掉要删除的元素即可

• 删除有左右子数的 方法二：
  1.先找到节点的后继值s=min(d -> right) 即当前节点的右子树的最小节点
  2.把后继值替换掉要删除的元素即可

    /**
     * 删除任意元素
     * 删除只有左子数 或 只有右子树的节点很简单：直接同上删除最小元素或最大元素即可
     * 删除有左右字数的：先找到节点的后继值s=min(d -> right) 即当前节点的右子树的最小节点
     *                  把后继值替换掉要删除的元素即可
     * @param e
     * @return
     */
    public void remove(E e){
        root = removeByRecursive(root, e);
    }

    /**
     * 递归删除任意元素
     * 返回删除元素的根
     * @param node
     * @param e
     * @return
     */
    private Node removeByRecursive(Node node, E e) {
        if(node == null){
            return null;
        }
        //删除左子树
        if(e.compareTo((E) node.e) < 0){
            node.left = removeByRecursive(node.left, e);
            return node;
        }
        //删除右子树
        if(e.compareTo((E) node.e) > 0){
            node.right = removeByRecursive(node.right, e);
            return node;
        }
        //删除当前元素
        else {
            //待删除节点左子树为空的情况
            if(node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size --;
                return rightNode;
            }
            //待删除节点右子树为空的情况
            if(node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }
            //待删除节点左/右子树都不为空
            //找到后继值节点[即待删除节点的右子树中的最小节点] 替换掉要删除的元素
            Node successor = minnumByRecursive(node.right);
            successor.right = removeMinByRecursive(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    } 

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2025/03/19 09:37