Detailed explanation of Java binary tree implementation and specific application cases

Detailed explanation of Java binary tree implementation and specific application cases

Binary tree is a data structure often used in computer science, which can perform very efficient search and sorting operations. In this article, we will discuss how to implement a binary tree in Java and some of its specific application cases.

Definition of Binary Tree

Binary tree is a very important data structure, consisting of the root node (the top node of the tree) and several left subtrees and right subtrees. Each node has at most two child nodes, the child node on the left is called the left subtree, and the child node on the right is called the right subtree. If a node does not have any child nodes, it is called a leaf node or terminal node.

Binary tree implementation in Java

The Node class can be used in Java to represent binary tree nodes. This class contains an int type value and two Node type references left and right, which represent the left side respectively. child node and right child node. The following is a sample code:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Implement the basic operations of a binary tree

1. Create a binary tree

You can create a binary tree recursively, first create the root node , and then create left subtree and right subtree respectively. The following is a sample code:

public class TreeBuilder {
    public TreeNode buildTree(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        return build(array, 0, array.length - 1);
    }

    private TreeNode build(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = build(array, start, mid - 1);
        root.right = build(array, mid + 1, end);
        return root;
    }
}

2. Find Node

The search operation of the binary tree is very efficient. Generally, it is determined whether to search the left child by comparing the size of the node value and the target value. The tree is still the right subtree. The following is a sample code:

public class TreeSearch {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (root.val > target) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }
}

3. Insert node

When inserting a new node into a binary tree, you need to compare the value of the node and the size of the inserted value, and decide based on the comparison result Whether to insert the new node into the left subtree or the right subtree. The following is a sample code:

public class TreeInsert {
    public TreeNode insert(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode(target);
        }
        if (root.val > target) {
            root.left = insert(root.left, target);
        } else if (root.val < target) {
            root.right = insert(root.right, target);
        }
        return root;
    }
}

4. Delete node

Deleting a node is a relatively complex operation and needs to be discussed in several situations. Assume that node A is to be deleted, which can be divided into the following three situations:

• A is a leaf node and can be deleted directly.
• A has only one child node, just replace the child node with its position.
• A has two child nodes. You need to find the smallest node B in its right subtree, replace A with the value of B, and then delete B.

The following is a sample code:

public class TreeDelete {
    public TreeNode delete(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (root.val > target) {
            root.left = delete(root.left, target);
        } else if (root.val < target) {
            root.right = delete(root.right, target);
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = findMin(root.right);
                root.val = min.val;
                root.right = delete(root.right, min.val);
            }
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

Specific application cases

Binary trees can solve some common data structure problems, such as finding the kth element, finding the smallest k elements, search the depth of the binary tree, etc.

The following are specific application cases:

1. Find the k-th element

The result of in-order traversal of a binary tree is in order, so it can be used Inorder traversal to find the kth element. The following is a sample code:

public class TreeFindKth {
    private int cnt = 0;

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int left = kthSmallest(root.left, k);
        if (left != Integer.MAX_VALUE) {
            return left;
        }
        cnt++;
        if (cnt == k) {
            return root.val;
        }
        return kthSmallest(root.right, k);
    }
}

2. Find the smallest k elements

To find the smallest k elements in a binary tree, you can also use in-order traversal, taking the top k elements. The following is a sample code:

public class TreeFindMinK {
    public List<Integer> kSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            if (result.size() == k) {
                return result;
            }
            current = current.right;
        }
        return result;
    }
}

3. Finding the depth of a binary tree

You can use recursion to find the depth of a binary tree. The following is a sample code:

public class TreeDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

Summary

This article introduces the implementation of binary trees in Java and some specific application cases. Binary tree is a very efficient data structure that is often used when processing large amounts of data. In practical applications, we can choose different implementation methods according to the characteristics of specific problems to obtain better performance.

The above is the detailed content of Detailed explanation of Java binary tree implementation and specific application cases. For more information, please follow other related articles on the PHP Chinese website!