Detailed explanation of binary tree structure in Java

Binary tree is a common data structure in computer science and a commonly used data structure in Java programming. This article will introduce the binary tree structure in Java in detail.

1. What is a binary tree?

In computer science, a binary tree is a tree structure in which each node has at most two child nodes. Among them, the left child node is smaller than the parent node, and the right child node is larger than the parent node. In Java programming, binary trees are commonly used to represent sorting, searching and improving the efficiency of data query.

2. Binary tree implementation in Java

In Java, binary tree implementation usually uses node class (Node Class) and binary tree class (Binary Tree Class). The node class represents each node in the binary tree and can have bytes and attributes for storing data. The binary tree class represents the entire binary tree data structure and has functions such as inserting nodes, deleting nodes, and traversing. The following is a simple Java binary tree implementation:

public class Node {
    int key;
    String value;
    Node leftChild, rightChild;

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

public class BinaryTree {
    Node root;

    public void insert(int key, String value) {
        Node newNode = new Node(key, value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            while (true) {
                if (key < current.key) {
                    if (current.leftChild == null) {
                        current.leftChild = newNode;
                        return;
                    }
                    current = current.leftChild;
                } else {
                    if (current.rightChild == null) {
                        current.rightChild = newNode;
                        return;
                    }
                    current = current.rightChild;
                }
            }
        }
    }

    public Node find(int key) {
        Node current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.key + ": " + node.value);
            inOrderTraversal(node.rightChild);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.key + ": " + node.value);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.key + ": " + node.value);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50, "John");
        tree.insert(25, "Alice");
        tree.insert(75, "Bob");
        tree.insert(15, "Chris");
        tree.insert(33, "Diana");
        tree.insert(60, "Emily");
        tree.insert(90, "Fred");

        Node node = tree.find(33);
        System.out.println("Find key: " + node.key + ", value: " + node.value);

        System.out.println("In-order traversal:");
        tree.inOrderTraversal(tree.root);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(tree.root);

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal(tree.root);
    }
}

The above binary tree code includes three main functions: inserting nodes, searching nodes, and three different traversal methods. The insertion node uses a while loop to insert data in the order of the binary tree; the search node uses a while loop to traverse the tree to search for target data; all three traversal methods are implemented recursively.

3. Binary tree traversal methods

In the above Java code, the program implements three different binary tree traversal methods: in-order traversal, pre-order traversal and post-order traversal. This section will introduce these three traversal methods one by one.

1. In-order traversal

In-order traversal traverses the nodes in the tree in order from small to large. In Java code, the implementation of in-order traversal uses recursion: for each node, first call its own left node, then print the node data, and finally call its own right node. In this way, all nodes in the tree can be traversed in order from small to large.

2. Pre-order traversal

Pre-order traversal traverses the nodes in the tree in the order of parent node, left node, and right node. In Java code, the implementation of preorder traversal also uses recursion: for each node, first print the node data, then call its own left node, and finally call its own right node. In this way, all nodes in the tree can be traversed in the order of parent node, left node, and right node.

3. Post-order traversal

Post-order traversal traverses the nodes in the tree in the order of left node, right node, and parent node. In Java code, the implementation of post-order traversal also uses recursion: for each node, first call its own left node, then call its own right node, and finally print the node data. In this way, all nodes in the tree can be traversed in the order of left node, right node, and parent node.

4. Commonly used binary tree algorithms

The binary tree is a flexible and very useful data structure. In Java programming, the binary tree algorithm is often used. The following are commonly used binary tree algorithms:

1. Search

Search is one of the most basic functions of binary trees and is also a frequently used function. In Java code, the implementation of search is very simple: for each node, by comparing the size of the node value and the target value, search downwards layer by layer until the target value is found or the entire tree is traversed.

2. Insertion

Insertion is the function of adding new nodes to the binary tree. At the same time, the inserted new nodes will also follow the sorting order of the binary tree. In Java code, the implementation of insertion is also relatively simple: compare the size of the node to be inserted and the current node, and insert a new node when a suitable position is found.

3. Delete

Deletion is the function of removing nodes from a binary tree. In Java code, the implementation of deletion is more complicated and requires more considerations. If the deleted node has no child nodes, just delete it directly; if there is only one child node, just move the child node to the position of the deleted node; if the deleted node has two child nodes, you need to find the minimum value of the right child node. node and replace it with the location of the deleted node.

5. Summary

This article introduces the binary tree data structure in Java in detail, including the definition of binary tree, the implementation of nodes and binary tree classes, three different traversal methods and commonly used binary tree algorithms. Binary tree is a widely used data structure, and Java provides many functions and class libraries to assist in the implementation of binary trees. When programming in Java, being proficient in the use and implementation of binary trees can improve program efficiency and the accuracy of data queries.

The above is the detailed content of Detailed explanation of binary tree structure in Java. For more information, please follow other related articles on the PHP Chinese website!