01-二叉搜索树

数据结构可视化：二叉搜索树

二叉搜索树

实现一个二叉搜索树，并实现插入、查找和删除操作。

public class BinarySearchTree {
    private Node root;

    private class Node {
        private int key;
        private Node left, right;
        private int size;

        public Node(int key, int size) {
            this.key = key;
            this.size = size;
        }
    }

    public boolean contains(int key) {
        return get(key) != null;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (node == null) return 0;
        else return node.size;
    }

    public void put(int key) {
        root = put(root, key);
    }

    private Node put(Node node, int key) {
        if (node == null) return new Node(key, 1);

        if (key < node.key) {
            node.left = put(node.left, key);
        } else if (key > node.key) {
            node.right = put(node.right, key);
        } else {
            node.key = key;
        }

        node.size = 1 + size(node.left) + size(node.right);
        return node;
    }

    public void delete(int key) {
        root = delete(root, key);
    }

    private Node delete(Node node, int key) {
        if (node == null) return null;

        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else {
            if (node.right == null) return node.left;
            if (node.left == null) return node.right;

            Node temp = node;
            node = min(temp.right);
            node.right = deleteMin(temp.right);
            node.left = temp.left;
        }

        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    private Node min(Node node) {
        if (node.left == null) return node;
        else return min(node.left);
    }

    private Node deleteMin(Node node) {
        if (node.left == null) return node.right;
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }

    public int get(int key) {
        Node node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return node.key;
            }
        }
        return null;
    }
}

这是一个基本的二叉搜索树类，具有方法：

• contains(int key): 查找树中是否包含指定的关键字，如果有，则返回 true，否则返回 false。
• isEmpty(): 返回树中是否包含任何元素。
• size(): 返回树中的元素数量。
• put(int key): 在树中添加一个新元素。
• delete(int key): 从树中删除指定元素。
• get(int key): 查找指定的元素是否存在于树中，如果存在则返回其关键字，否则返回 null。

二叉树求和路径

在一个二叉树中，求判定是否存在一条从根节点到叶节点的路径，同时， 如果存在的话将路径打印出来（如NodeA->NodeB->NodeC->NodeD） 这条路径上所有节点的值加起来的和等于给定的值。

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉树和路径
 */
public class BinaryTreeSumPath {

    public static void printPath(TreeNode root, int sum) {
        List<TreeNode> path = new ArrayList<>();
        printPathHelper(root, sum, 0, path);
    }

    private static void printPathHelper(TreeNode node, int sum, int curSum, List<TreeNode> path) {
        if (node == null) {
            return;
        }
        curSum += node.val;
        path.add(node);

        if (node.left == null && node.right == null && curSum == sum) {
            for (TreeNode n : path) {
                System.out.print(n.val + " ");
            }
            System.out.println();
        }

        printPathHelper(node.left, sum, curSum, path);
        printPathHelper(node.right, sum, curSum, path);

        path.remove(path.size() - 1); // 回溯
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        // 构造一棵二叉树
        BinaryTreeSumPath.TreeNode root = new BinaryTreeSumPath.TreeNode(5);
        root.left = new BinaryTreeSumPath.TreeNode(4);
        root.right = new BinaryTreeSumPath.TreeNode(8);
        root.left.left = new BinaryTreeSumPath.TreeNode(11);
        root.left.left.left = new BinaryTreeSumPath.TreeNode(7);
        root.left.left.right = new BinaryTreeSumPath.TreeNode(2);
        root.right.left = new BinaryTreeSumPath.TreeNode(13);
        root.right.right = new BinaryTreeSumPath.TreeNode(4);
        root.right.right.left = new BinaryTreeSumPath.TreeNode(5);
        root.right.right.right = new BinaryTreeSumPath.TreeNode(1);

        //调用 printPath 方法查找符合条件的路径
        //5 4 11 2
        //5 8 4 5
        BinaryTreeSumPath.printPath(root, 22);
    }
}

1. 首先定义一个变量 sum，表示当前路径上所有节点的值的和。
2. 从根节点开始遍历二叉树，每次遍历到一个节点时就将该节点的值加入到 sum 中。
3. 如果当前节点是叶子节点，并且 sum 的值等于给定的值，那么说明找到了一条符合要求的路径，将它打印出来即可。
4. 如果当前节点不是叶子节点，那么分别对它的左右子树进行递归处理。

其中，TreeNode 表示二叉树节点的类，包括 val（节点的值）和 left、right（左右子节点）三个属性。printPathHelper 方法是递归函数，用于遍历二叉树并查找符合要求的路径。在该函数中，path 参数表示从根节点到当前节点的路径。每次递归处理时，都将当前节点加入 path 中，并计算当前路径上所有节点的值的和。如果当前节点是叶子节点，并且 curSum 等于给定的 sum，那么就说明找到了一条符合要求的路径，将其打印出来即可。

在递归调用完左、右子树后，需要将 path 中的最后一个节点（即当前节点）删除，以便回溯到上一层节点进行下一次遍历。