The tree

Before we talk about binary trees, what is a tree

The definition of the tree

Tree is a very important data structure in our computer. It can describe many things in real life, such as family tree, organization structure of unit, and so on.
A tree is a set of hierarchical relationships composed of N (n>=1) finite nodes. It’s called a tree because it looks like an upside down tree, meaning it has roots up and leaves down.

Trees here

The characteristics of the tree

Each node has zero or more children;
A node with no parent is a root node;
Each non-root node has only one parent;
Each node and its descendants can be viewed as a tree, called a subtree of the parent of the current node;

Terminology for trees

Degree of node:

The number of subtrees a node contains is called the degree of the node;

Leaf node:

Nodes with degree 0 are called leaf nodes, or they can be called terminal nodes

Branch node:

Nodes whose degree is not zero are called branch nodes or non-terminal nodes

Hierarchy of nodes:

Starting at the root, the level of the root is 1, the level of its immediate successor is 2, and so on

Sequence number of nodes:

The nodes in the tree are arranged in a linear sequence from top to bottom and from left to right in the same layer, and they are arranged into continuous natural numbers.

Tree degrees:

The maximum degree of all nodes in the tree

Tree height (depth) :

The maximum level of nodes in a tree

Forest:

M (m>=0) sets of non-intersecting trees. If the root node of a non-empty tree is deleted, the tree becomes a forest. Add a uniform root to a forest and it becomes a tree

Child node:

The immediate successors of a node are called the children of that node, e.g. (H is the child of D)

Parent (parent) :

The immediate precursor of a node is called the parent of that node, e.g. (D is the parent of H)

Sibling node:

Children of the same parent are called siblings, e.g. (I and J are siblings)

Now that you have a basic definition of a tree, let’s take a look at a special type of tree: binary trees

Binary tree

define

A binary tree is a tree with a degree of 2 or less.

graphic

Two special binary trees

Full binary tree

A binary tree is a full binary tree if the number of nodes at each level is maximized.

The number of nodes in each layer from the root is 1,2,4,8,16…. The rule is 2 to the n minus 1.

Complete binary tree

Leaf nodes can only appear at the lowest and lower levels, and the nodes at the lowest level are concentrated in the binary tree at the leftmost positions of the layer

Attention should be paid to the definition and judgment of full and complete binary trees

Ordinary binary tree creation

We create it in the form of a linked list
We need a node class to record the left subtree, right subtree, key, and value of the current node

private class Node {
        public Key key;/ / key
        public Value value;/ / value
        public Node left;// Left child
        public Node right;// Right child

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right; }}Copy the code

Two variables are needed to record the root node and the number of elements in the tree

private Node root;/ / the root node
private int N;// The number of elements in the tree
Copy the code

Define some way to create a binary tree

Insert data into the binary tree

Public void put(Key Key, Value Value): Insert a key-value pair into the tree (Call the overloaded PUT method below)
Public Node put(Node x,Key Key, Value Value) : Adds a key-value pair to the specified tree x and returns the new tree

Ideas:

2. The tree is not empty. Start from the root node and determine the key of the new node and the key of the current node. 2.1 If the key of the new node is larger than the key of the current node, continue to search for the right child of the current node. 2.2 If the key of the new node is smaller than the key of the current node, continue to search for the left child of the current node. 2.3 If the key of the new node is equal to the key of the current node, replace the value of the current nodeCopy the code

Code implementation:

public Node put(Node x, Key key, Value value) {
        if (x == null) {/ / tree is empty
            N++;
            return new Node(key, value, null.null);
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key of the new node is larger than the key of the current node, continue to find the right child of the current node
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
            x.left = put(x.left, key, value);
        } else {// If the new node's key is the same as the current node's key, replace the current node's value
            x.value = value;
        }
        return x;
    }
Copy the code

Find the value of the key from the tree

Public Value get(Key Key) : find the Value of the Key from the tree (Call the overloaded GET method below)
Public Value get(Node x, Key Key): searches for the Value of the Key in the specified tree X

Ideas:

2. If the tree is not empty, start traversing from the root node to determine the key size of the node to be searched and the key size of the current node. 2.1 If the key of the node to be searched is larger than that of the current node, 2.2 If the key of the node to be searched is smaller than the key of the current node, the left child of the current node is searched. 2.3 If the key of the node to be searched is equal to the key of the current node, the value of the current node is returnedCopy the code

Code implementation:

    public Value get(Node x, Key key) {
        // The tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            return get(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            return get(x.left, key);
        } else {// Replace the value of the current node with the value of the current node
            returnx.value; }}Copy the code

Deletes the value of key from the tree

Public void delete(Key Key): deletes the value of the Key from the tree (Call the delete method overloaded below)
Public Node delete(Node x, Key Key): deletes the value of the Key in the specified tree X

Ideas:

1. Find the node to be deleted (same as get method), reduce the number of elements by 1 2. Find the smallest node in the right subtree of the node to be deleted minNode 2.1 Consider possible locations of the node to be deleted 2.1.1 The node to be deleted has no left child node 2.1.2 The node to be deleted has no right child node 2.1.3 The node to be deleted has left child node and right child node 3. Delete the smallest node in the right subtree 4. Make the left subtree of the deleted node the left subtree of the minNode, and make the right subtree of the deleted node the right subtree of the minNode 5. Make the parent of the deleted node point to minNode, the smallest nodeCopy the code

Code implementation:

 public Node delete(Node x, Key key) {
        / / tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            x.right = delete(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            x.left = delete(x.left, key);
        } else {// If the current key is the same as the current key, the node to be deleted is found
            /* The number of elements to delete is reduced by 1. MinNode 1.1 Consider the possible location of the node to be deleted 1.1.1 The node to be deleted has no left child node 1.1.2 The node to be deleted has no right child node 1.1.3 The node to be deleted has left child node and right child node 2. Delete the smallest node in the right subtree. 3. Make the left subtree of the deleted node become the left subtree of minNode. Make the right subtree of the deleted node the right subtree of the minNode. Make the parent of the deleted node point to the smallest node minNode */
            // The number of elements is reduced by one
            N--;
            // The node to be deleted has no left child
            if (x.left == null) {
                return x.right;
            }
            // The node to be deleted has no right child node
            if (x.right == null) {
                return x.left;
            }
            // Find the smallest node in the right subtree of the node to be deleted
            Node minNode = x.right;
            // The smallest node in the right subtree of the node to be deleted is minNode
            while(minNode.left ! =null) {
                minNode = minNode.left;
            }
            // Delete the smallest node in the right subtree
            // Start from the right subtree of the node to be deleted and work your way to the left
            Node temp = x.right;
            while(temp.left ! =null) {
                if (temp.left.left == null) {
                    temp.left = null;// Delete is implemented here
                } else{ temp = temp.left; }}// make the left subtree of the deleted node the left subtree of the smallest node minNode
            minNode.left = x.left;
            // make the right subtree of the deleted node the right subtree of the smallest node minNode
            minNode.right = x.right;
            // Make the parent of the deleted node point to the smallest node minNode
            x = minNode;// Give x all the contents of minNode

        }

        return x;
Copy the code

Gets the number of elements in the tree

Public int size(): Gets the number of elements in the tree

Code implementation:

    // Get the number of elements in the tree
    public int size(a) {
        return N;
    }
Copy the code

Complete binary tree creation API

package com.study.tree;

import com.study.queue.queueAPI;

public class BinaryTreeAPI<Key extends Comparable<Key>, Value> {
    / / node class
    private class Node {
        public Key key;/ / key
        public Value value;/ / value
        public Node left;// Left child
        public Node right;// Right child

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right; }}private Node root;/ / the root node
    private int N;// The number of elements in the tree

    // Get the number of elements in the tree
    public int size(a) {
        return N;
    }

    // Add the key-value element to the entire tree
    // Call the overloaded method of put
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    /** * adds a key-value to the specified tree and returns the new tree * 1. If the tree is empty, the new node is used as the root node * 2. If the tree is not empty, judge the key of the new node and the key of the current node from the root node. * 2.1 If the key of the new node is larger than the key of the current node, continue to search for the right child of the current node * 2.2 If the key of the new node is smaller than the key of the current node, continue to search for the left child of the current node * 2.3 If the key of the new node is equal to the key of the current node, Replace the value */ of the current node
    public Node put(Node x, Key key, Value value) {
        if (x == null) {/ / tree is empty
            N++;
            return new Node(key, value, null.null);
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key of the new node is larger than the key of the current node, continue to find the right child of the current node
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
            x.left = put(x.left, key, value);
        } else {// If the new node's key is the same as the current node's key, replace the current node's value
            x.value = value;
        }
        return x;
    }

    // Query the value of the specified key in the entire tree
    public Value get(Key key) {
        return get(root, key);
    }

    // In the specified tree x, find the corresponding value of key
    public Value get(Node x, Key key) {
        // The tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            return get(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            return get(x.left, key);
        } else {// Replace the value of the current node with the value of the current node
            returnx.value; }}// Delete the value corresponding to the key in the tree
    public void delete(Key key) {
        delete(root, key);
    }

    /** * removes the value corresponding to the key in the specified tree and returns the deleted new tree * 1. Find the deleted node; * 2. Find the smallest node minNode * 3 in the right subtree of the deleted node. Delete the smallest node in the right subtree * 4. Make the left subtree of the deleted node the left subtree of minNode, * make the right subtree of the deleted node the right subtree of minNode * 5. Make the parent of the deleted node point to the smallest node minNode */
    public Node delete(Node x, Key key) {
        / / tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            x.right = delete(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            x.left = delete(x.left, key);
        } else {// If the current key is the same as the current key, the node to be deleted is found
            /* The number of elements to delete is reduced by 1. MinNode 1.1 Consider the possible location of the node to be deleted 1.1.1 The node to be deleted has no left child node 1.1.2 The node to be deleted has no right child node 1.1.3 The node to be deleted has left child node and right child node 2. Delete the smallest node in the right subtree. 3. Make the left subtree of the deleted node become the left subtree of minNode. Make the right subtree of the deleted node the right subtree of the minNode. Make the parent of the deleted node point to the smallest node minNode */
            // The number of elements is reduced by one
            N--;
            // The node to be deleted has no left child
            if (x.left == null) {
                return x.right;
            }
            // The node to be deleted has no right child node
            if (x.right == null) {
                return x.left;
            }
            // Find the smallest node in the right subtree of the node to be deleted
            Node minNode = x.right;
            // The smallest node in the right subtree of the node to be deleted is minNode
            while(minNode.left ! =null) {
                minNode = minNode.left;
            }
            // Delete the smallest node in the right subtree
            // Start from the right subtree of the node to be deleted and work your way to the left
            Node temp = x.right;
            while(temp.left ! =null) {
                if (temp.left.left == null) {
                    temp.left = null;// Delete is implemented here
                } else{ temp = temp.left; }}// make the left subtree of the deleted node the left subtree of the smallest node minNode
            minNode.left = x.left;
            // make the right subtree of the deleted node the right subtree of the smallest node minNode
            minNode.right = x.right;
            // Make the parent of the deleted node point to the smallest node minNode
            x = minNode;// Give x all the contents of minNode

        }

        returnx; }}Copy the code

Maximum and minimum keys in a binary tree

Train of thought

Because we created it on the basis that the left subtree of the root is smaller than the root, and the right subtree of the root is larger than the root, so we go to the right subtree for the largest key, and we go to the left subtree for the smallest key

Method implementation (I also put these in the binary tree creation API)

    // Find the largest key in the tree
    public Key max(a) {
        Node minNode = root; // Use a new node for the purpose of preventing root from being modified
        / / tree is empty
        if (minNode == null) {
            return null;
        }
        // The tree is not empty
        while(minNode.right ! =null) {
            if (minNode.right.right == null) {
                return minNode.right.key;
            } else{ minNode = minNode.right; }}return minNode.key;
    }

    // Find the smallest key in the tree
    public Key min(a) {
        Node maxNode = root;
        / / tree is empty
        if (maxNode == null) {
            return null;
        }
        // The tree is not empty
        while(maxNode.left ! =null) {
            if (maxNode.left.left == null) {
                return maxNode.left.key;
            } else{ maxNode = maxNode.left; }}return maxNode.key;
    }
Copy the code

Traversal of binary trees

With the following binary tree traversal to illustrate three ordinary traversal and an advanced traversal

The former sequence traversal

Traverse order: root node -> left subtree -> right subtree

Ideas:

Put the key of the current node into the queue
Find the left subtree of the current node, if not empty, recursively traverse the left subtree
Find the right subtree of the current node, if not empty, recursively traverse the right subtree

    // First access the root node, then the left subtree, then the right subtree
    // Get all keys of the entire tree
    public queueAPI<Key> preErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        preErgodic(root, queue);
        return queue;
    }

    // Get all the keys of the specified tree and put them in the queue
    public void preErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // put the key of node X into the queue
        queue.enqueue(x.key);

        // Recursively traverse the left subtree of x
        if(x.left ! =null) {
            preErgodic(x.left, queue);
        }
        // Recursively traverse the right subtree of x
        if(x.right ! =null) { preErgodic(x.right, queue); }}Copy the code

In the sequence traversal

Traversal order: left subtree -> root node -> right subtree

Ideas:

Find the left subtree of the current node, if not empty, recursively traverse the left subtree
Put the key of the current node into the queue;
Find the right subtree of the current node, if not empty, recursively traverse the right subtree

     // Middle traversal: first access the left subtree, then access the root, then access the right subtree
    public queueAPI<Key> midErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        midErgodic(root, queue);
        return queue;
    }

    public void midErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // Recursively traverse the left subtree, looking for the leftmost element
        if(x.left ! =null) {
            midErgodic(x.left, queue);
        }
        // when x. eft equals null, the current node x is the leftmost element and is added directly to the queue
        queue.enqueue(x.key);
        // Recursively traverse the right subtree
        if(x.right ! =null) { midErgodic(x.right, queue); }}Copy the code

After the sequence traversal

Traversal order: left subtree -> right subtree -> root node

Ideas:

Find the left subtree of the current node, if not empty, recursively traverse the left subtree
Find the right subtree of the current node, if not empty, recursively traverse the right subtree
Put the key of the current node into the queue;

    // Order traversal: first access the left subtree, then access the right subtree, then access the root
    public queueAPI<Key> afterErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        afterErgodic(root, queue);
        return queue;
    }

    public void afterErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // Recursively traverse the left subtree
        if(x.left ! =null) {
            afterErgodic(x.left, queue);
        }
        // Recursively traverse the right subtree
        if(x.right ! =null) {
            afterErgodic(x.right, queue);
        }
        // when x. eft equals null, yes, the current node x is the leftmost element and is added directly to the queue
        queue.enqueue(x.key);

    }
Copy the code

Sequence traversal

Traversal order: start from the root node (the first layer) and then go down to obtain the values of all nodes of each layer.

Ideas:

Create a queue to store nodes, putting the head node in first
Each time a node in the queue is popped, the key of the node is obtained
See if the node that pops up has a left child and put it in if it does
See if the node that pops up has a right child and put it in if it does

The illustration

public queueAPI<Key> layerErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();// Store sorted elements
        queueAPI<Node> nodes = new queueAPI<>();// Store the node
        // Put the first node into the node queue
        nodes.enqueue(root);
        // Iterate over the Nodes queue
        while(! nodes.isEmpty()){// Pop the first node in the queue each time
            Node node = nodes.dequeue();
            // Put the key of the pop-up node into the sorted queue
            queue.enqueue(node.key);
            // Check whether the popup node has a left child node. If so, add it to the node queue
            if(node.left! =null){
                nodes.enqueue(node.left);
            }
            // See if the node that pops up has a right child node. If it does, add it to the node queue
            if(node.right! =null){ nodes.enqueue(node.right); }}return queue;
    }
Copy the code

The depth of a binary tree

Depth: The number of nodes along the longest path from the root node of the tree to the farthest leaf node

Ideas:

If the root is empty, the maximum depth is 0.
Calculate the maximum depth of the left subtree;
Calculate the maximum depth of the right subtree;
The maximum depth of the current tree = the greater of the maximum depth of the left subtree and the maximum depth of the right subtree +1

Code implementation:

 public int maxDepth(a){
        return maxDepth(root);
    }
    // Find the maximum depth of the tree
    public int maxDepth(Node x){
        if (x==null) {return 0;
        }
        int left = 0; // The maximum depth of the left subtree
        int right = 0; // The maximum depth of the right subtree
        int max = 0; // The larger of the left and right subtrees
        if(x.left! =null) {// Calculate the maximum depth of the left subtree;
            left=maxDepth(x.left);
        }
        if(x.right! =null) {// Calculate the maximum depth of the right subtree;right = maxDepth(x.right); } max = left>right? left+1:right+1;
        return max;

    }
Copy the code

Binary tree summary

The above method implementation is summarized into a binary tree implementation API, the total code is:

package com.study.tree;

import com.study.queue.queueAPI;

public class BinaryTreeAPI<Key extends Comparable<Key>, Value> {
    private Node root;/ / the root node
    private int N;// The number of elements in the tree

    // Get the number of elements in the tree
    public int size(a) {
        return N;
    }

    // Add the key-value element to the entire tree
    // Call the overloaded method of put
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    /** * adds a key-value to the specified tree and returns the new tree * 1. If the tree is empty, the new node is used as the root node * 2. If the tree is not empty, judge the key of the new node and the key of the current node from the root node. * 2.1 If the key of the new node is larger than the key of the current node, continue to search for the right child of the current node * 2.2 If the key of the new node is smaller than the key of the current node, continue to search for the left child of the current node * 2.3 If the key of the new node is equal to the key of the current node, Replace the value */ of the current node
    public Node put(Node x, Key key, Value value) {
        if (x == null) {/ / tree is empty
            N++;
            return new Node(key, value, null.null);
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key of the new node is larger than the key of the current node, continue to find the right child of the current node
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {// If the key of the new node is smaller than the key of the current node, continue to find the left child of the current node
            x.left = put(x.left, key, value);
        } else {// If the new node's key is the same as the current node's key, replace the current node's value
            x.value = value;
        }
        return x;
    }

    // Query the value of the specified key in the entire tree
    public Value get(Key key) {
        return get(root, key);
    }

    // In the specified tree x, find the corresponding value of key
    public Value get(Node x, Key key) {
        // The tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            return get(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            return get(x.left, key);
        } else {// Replace the value of the current node with the value of the current node
            returnx.value; }}// Delete the value corresponding to the key in the tree
    public void delete(Key key) {
        delete(root, key);
    }

    /** * removes the value corresponding to the key in the specified tree and returns the deleted new tree * 1. Find the deleted node; * 2. Find the smallest node minNode * 3 in the right subtree of the deleted node. Delete the smallest node in the right subtree * 4. Make the left subtree of the deleted node the left subtree of minNode, * make the right subtree of the deleted node the right subtree of minNode * 5. Make the parent of the deleted node point to the smallest node minNode */
    public Node delete(Node x, Key key) {
        / / tree is empty
        if (x == null) {
            return null;
        }
        // The tree is not empty
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {// If the key is larger than the current key, continue to search for the right child of the current node
            x.right = delete(x.right, key);
        } else if (cmp < 0) {// If the key is smaller than the key of the current node, continue to find the left child of the current node
            x.left = delete(x.left, key);
        } else {// If the current key is the same as the current key, the node to be deleted is found
            /* The number of elements to delete is reduced by 1. MinNode 1.1 Consider the possible location of the node to be deleted 1.1.1 The node to be deleted has no left child node 1.1.2 The node to be deleted has no right child node 1.1.3 The node to be deleted has left child node and right child node 2. Delete the smallest node in the right subtree. 3. Make the left subtree of the deleted node become the left subtree of minNode. Make the right subtree of the deleted node the right subtree of the minNode. Make the parent of the deleted node point to the smallest node minNode */
            // The number of elements is reduced by one
            N--;
            // The node to be deleted has no left child
            if (x.left == null) {
                return x.right;
            }
            // The node to be deleted has no right child node
            if (x.right == null) {
                return x.left;
            }
            // Find the smallest node in the right subtree of the node to be deleted
            Node minNode = x.right;
            // The smallest node in the right subtree of the node to be deleted is minNode
            while(minNode.left ! =null) {
                minNode = minNode.left;
            }
            // Delete the smallest node in the right subtree
            // Start from the right subtree of the node to be deleted and work your way to the left
            Node temp = x.right;
            while(temp.left ! =null) {
                if (temp.left.left == null) {
                    temp.left = null;// Delete is implemented here
                } else{ temp = temp.left; }}// make the left subtree of the deleted node the left subtree of the smallest node minNode
            minNode.left = x.left;
            // make the right subtree of the deleted node the right subtree of the smallest node minNode
            minNode.right = x.right;
            // Make the parent of the deleted node point to the smallest node minNode
            x = minNode;// Give x all the contents of minNode

        }

        return x;
    }

    // Find the largest key in the tree
    public Key max(a) {
        Node minNode = root; // Use a new node for the purpose of preventing root from being modified
        / / tree is empty
        if (minNode == null) {
            return null;
        }
        // The tree is not empty
        while(minNode.right ! =null) {
            if (minNode.right.right == null) {
                return minNode.right.key;
            } else{ minNode = minNode.right; }}return minNode.key;
    }

    // Find the smallest key in the tree
    public Key min(a) {
        Node maxNode = root;
        / / tree is empty
        if (maxNode == null) {
            return null;
        }
        // The tree is not empty
        while(maxNode.left ! =null) {
            if (maxNode.left.left == null) {
                return maxNode.left.key;
            } else{ maxNode = maxNode.left; }}return maxNode.key;
    }

    // First access the root node, then the left subtree, then the right subtree
    // Get all keys of the entire tree
    public queueAPI<Key> preErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        preErgodic(root, queue);
        return queue;
    }

    // Get all the keys of the specified tree and put them in the queue
    public void preErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // put the key of node X into the queue
        queue.enqueue(x.key);

        // Recursively traverse the left subtree of x
        if(x.left ! =null) {
            preErgodic(x.left, queue);
        }
        // Recursively traverse the right subtree of x
        if(x.right ! =null) { preErgodic(x.right, queue); }}// Middle traversal: first access the left subtree, then access the root, then access the right subtree
    public queueAPI<Key> midErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        midErgodic(root, queue);
        return queue;
    }

    public void midErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // Recursively traverse the left subtree, looking for the leftmost element
        if(x.left ! =null) {
            midErgodic(x.left, queue);
        }
        // when x. eft equals null, the current node x is the leftmost element and is added directly to the queue
        queue.enqueue(x.key);
        // Recursively traverse the right subtree
        if(x.right ! =null) { midErgodic(x.right, queue); }}// Order traversal: first access the left subtree, then access the right subtree, then access the root
    public queueAPI<Key> afterErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();
        afterErgodic(root, queue);
        return queue;
    }

    public void afterErgodic(Node x, queueAPI<Key> queue) {
        if (x == null) {
            return;
        }
        // Recursively traverse the left subtree
        if(x.left ! =null) {
            afterErgodic(x.left, queue);
        }
        // Recursively traverse the right subtree
        if(x.right ! =null) {
            afterErgodic(x.right, queue);
        }
        // when x. eft equals null, yes, the current node x is the leftmost element and is added directly to the queue
        queue.enqueue(x.key);

    }

    // sequence traversal
    // 1. Create a queue to store nodes
    // 2. Each time a node in the queue is popped,
    // 3. Check if the popup node has a left child node. If so, put it in
    // 4. Check if the popup node has a right child node, if so, put it in
    public queueAPI<Key> layerErgodic(a) {
        queueAPI<Key> queue = new queueAPI<>();// Store sorted elements
        queueAPI<Node> nodes = new queueAPI<>();// Store the node
        // Put the first node into the node queue
        nodes.enqueue(root);
        // Iterate over the Nodes queue
        while(! nodes.isEmpty()){// Pop the first node in the queue each time
            Node node = nodes.dequeue();
            // Put the key of the pop-up node into the sorted queue
            queue.enqueue(node.key);
            // Check whether the popup node has a left child node. If so, add it to the node queue
            if(node.left! =null){
                nodes.enqueue(node.left);
            }
            // See if the node that pops up has a right child node. If it does, add it to the node queue
            if(node.right! =null){ nodes.enqueue(node.right); }}return queue;
    }
    // Find the maximum depth of the whole tree
    // 1. Find the maximum depth of the left subtree
    // 2. Find the maximum depth of the right subtree
    // 3. Take the maximum value of left and right subtrees +1 as the depth
    public int maxDepth(a){
        return maxDepth(root);
    }
    // Find the maximum depth of the tree
    public int maxDepth(Node x){
        if (x==null) {return 0;
        }
        int left = 0; // The maximum depth of the left subtree
        int right = 0; // The maximum depth of the right subtree
        int max = 0; // The larger of the left and right subtrees
        if(x.left! =null){
            left=maxDepth(x.left);
        }
        if(x.right! =null){ right = maxDepth(x.right); } max = left>right? left+1:right+1;
        return max;

    }
    / / node class
    private class Node {
        public Key key;/ / key
        public Value value;/ / value
        public Node left;// Left child
        public Node right;// Right child

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right; }}}Copy the code

Let’s test the code again:

package com.study.tree;

import com.study.queue.queueAPI;

public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTreeAPI<Integer, String> bt = new BinaryTreeAPI<>();
        bt.put(5."Zhang");
        bt.put(2."Bill");
        bt.put(7."Fifty");
        bt.put(1."Daisy");
        bt.put(4."Xin wu");
        bt.put(6."Zhao four");
        bt.put(8."Wu lei");
        bt.put(3."Lin");
        System.out.println("After adding elements, the total number of elements is:"+bt.size());
        System.out.println(bt.get(2));
        bt.delete(2);
        System.out.println("After deleting elements, the total number of elements is:"+bt.size());
        System.out.println("After the element is deleted, the value of the element with key 2 is:"+bt.get(2));
        bt.put(2."Bill");
        Integer min = bt.min();
        System.out.println(The element with the smallest bond is:+min);
        Integer max = bt.max();
        System.out.println("The largest element of the bond is:"+max);
        System.out.println("Sequential traversal:");
        queueAPI<Integer> prequeue = bt.preErgodic();
        for (Integer i : prequeue) {
            System.out.println(i+"-"+bt.get(i));
        }
        System.out.println(Middle order traversal:);
        queueAPI<Integer> queue = bt.midErgodic();
        for (Integer i : queue) {
            System.out.println(i+"-"+bt.get(i));
        }
        System.out.println("After traversal:");
        queueAPI<Integer> afqueue = bt.afterErgodic();
        for (Integer i : afqueue) {
            System.out.println(i+"-"+bt.get(i));
        }
        System.out.println("Sequence traversal:");
        queueAPI<Integer> layerqueue = bt.layerErgodic();
        for (Integer i : layerqueue) {
            System.out.println(i+"-"+bt.get(i));
        }
        int maxDepth = bt.maxDepth();
        System.out.println(The depth of the tree is:+maxDepth); }}Copy the code

Add an element to the tree, delete an element from the tree, and obtain the value of the specific key in the tree

The former sequence traversal

In the sequence traversal

After the sequence traversal

Sequence traversal

The depth of the tree

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structure and algorithm — binary tree

The tree

Binary tree

Two special binary trees

Ordinary binary tree creation

Maximum and minimum keys in a binary tree

Traversal of binary trees

The former sequence traversal

In the sequence traversal

After the sequence traversal

Sequence traversal

The depth of a binary tree

Binary tree summary

Data structure and algorithm — binary tree

The tree

Binary tree

Two special binary trees

Ordinary binary tree creation

Maximum and minimum keys in a binary tree

Traversal of binary trees

The former sequence traversal

In the sequence traversal

After the sequence traversal

Sequence traversal

The depth of a binary tree

Binary tree summary

Related Posts

2020 annual summary | of android small Yu Denver annual essay

Home appliance enterprise 2.3 billion big single, hidden is cloud service empowerment

Best practice | OceanBase transaction engine of technology innovation