Look officer, don’t be angry, I did not scold you nor despise you, today is to simply share with everyone the tree related knowledge, but I still want to say that as a programmer, there is no tree in my heart? Do you run out of credits? Trees are one of the most commonly used data structures. There are many kinds of trees, such as binary trees, binary search trees, balanced binary trees, red-black trees, B trees, B+ trees and so on. Today, we are going to talk about binary tree related trees.

What is a tree?

The first thing we need to know is what is a tree? We have a tree that branches up and doesn’t have a closed loop, and the tree in the data structure looks like the tree that we see, actually looks like the root of the tree, and I drew a picture to give you a better understanding of the tree.

Height, depth, and layer are three other concepts associated with a tree. Let’s first look at the definitions of these three terms:

Height: The longest path from a node to a leaf node, counting from 0

Depth: The number of edges experienced by a node to this node, counting from 0

Layer: the distance between a node and the root node, counting from 1

Now that we know the concepts of the three nouns, we use a picture to better represent them.

So that’s the basic idea of trees, there are many kinds of trees, and we’re going to focus on binary trees.

Binary tree

As its name suggests, a binary tree has at most two nodes per element, called the left node and the right node. Of course, not every element needs to have two nodes, some may have only the left node, some may have only the right node. Just like the country allows two children, not everyone needs to have two children. Let’s look at a typical binary tree.

In order to make better use of storage space, binary trees are divided into complete binary trees and incomplete binary trees. Let’s first look at what are complete binary trees and incomplete binary trees?

The definition of a complete binary tree is: all the leaves are in the bottom two layers, all the leaves in the last layer are arranged to the left, and the number of nodes in all layers except the last layer is maximized

Maybe it’s confusing just looking at the definition, but let’s look at a couple of pictures, and you’ll see what a complete binary tree is and what a partial binary tree is.

1. Complete binary trees

2. Incomplete binary trees

We have said that the tree-based storage mode is different, and can be divided into complete binary tree and incomplete binary tree, so let’s look at the tree storage mode.

Storage mode of binary tree

There are two storage modes of binary tree, one is binary chain storage method based on pointer or reference, and the other is sequential storage method based on array

Binary chain storage

Chain storage is relatively simple and easy to understand. Each node has three fields, one containing the value of the node and two containing references to the left and right nodes. We can easily string the whole tree together by following the bytes, and the chain storage looks something like this.

Sequential storage method

Sequential storage is based on an array, which is an ordered memory space. If we place the coordinates of the nodes I =1, the left node will be 2 * I = 2, the right node will be 2 * I + 1 = 3, and so on, each node will do the same, and then we convert the tree to an array, and the other way around, We can also convert an array into a tree by following this rule. I think you see some disadvantages here, if this is an unbalanced binary tree is it going to waste a lot of space? Yeah, that’s why you have a complete binary tree and an incomplete binary tree. Take a look at the array-based storage patterns of these two trees.

Complete binary tree sequential storage method

Incomplete binary tree sequential storage method

After converting trees into arrays in the figure, it can be seen that a complete binary tree uses arrays to store only one subscript 0 storage space, while a binary incomplete binary tree wastes a lot of space. If the tree is a complete binary tree, array storage saves space compared to chain storage because array storage does not need to store information about the left and right nodes

Above we have learned the definition, type and storage of binary tree. Next we will learn about binary tree traversal. The traversal of binary tree is also a problem often encountered in interviews.

Binary tree traversal

To understand the traversal of binary trees, we first need to instantiate a binary tree. We define the tree by means of chain storage. To instantiate the tree, we need the node information of the tree, which is used to store the information of the node.

/** * define a tree */
public class TreeNode {
    / / stored value
    public int data;
    // Store the left node
    public TreeNode left;
    // Store the right node
    public TreeNode right;

    public TreeNode(int data) {
        this.data = data; }}Copy the code

After defining the node information, we can initialize a tree. Here is how to initialize the tree:

public static TreeNode buildTree(a) {
    // Create a binary tree for testing
    TreeNode t1 = new TreeNode(1);
    TreeNode t2 = new TreeNode(2);
    TreeNode t3 = new TreeNode(3);
    TreeNode t4 = new TreeNode(4);
    TreeNode t5 = new TreeNode(5);
    TreeNode t6 = new TreeNode(6);
    TreeNode t7 = new TreeNode(7);
    TreeNode t8 = new TreeNode(8);

    t1.left = t2;
    t1.right = t3;
    t2.left = t4;
    t4.right = t7;
    t3.left = t5;
    t3.right = t6;
    t6.left = t8;

    return t1;
}
Copy the code

After the above steps, our tree should look like the one shown below, with numbers representing the value of the node.

Once we have a tree, we can traverse the tree. There are three ways to traverse the binary tree, namely, pre-order traversal, middle-order traversal and follow-up traversal. The three traversal modes are related to the order of node output. Let’s look at each of the three traversal methods.

The former sequence traversal

Pre-order traversal: For any node in the tree, print the node first, then its left subtree, and finally its right subtree.

In order to facilitate everyone’s understanding, I made dynamic diagrams of the execution process of the three traversal methods based on the binary tree defined above. I hope it will be helpful for your reading. Let’s first look at the dynamic diagram of the execution process of the preceding traversal.

// The recursive implementation prints itself first, then the left node, then the right node
public static void preOrder(TreeNode root) {

    if (root == null) {
        return;
    }
    // Output itself
    System.out.print(root.data + "");
    // Iterate over the left node
    preOrder(root.left);
    // Iterate over the right node
    preOrder(root.right);
}
Copy the code

In the sequence traversal

Middle-order traversal: For any node in the tree, print its left subtree first, then itself, and finally its right subtree.

As with the previous order traversal, let’s look at the dynamic diagram of the execution flow of order traversal.

// Print the left node, then print itself, and finally print the right node
public static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrder(root.left);
    System.out.print(root.data + "");
    inOrder(root.right);
}
Copy the code

After the sequence traversal

Back-order traversal: For any node in the tree, print its left subtree, then its right subtree, and finally print the node itself.

Just like the previous two iterations, once we understand the concept, let’s look at a picture.

// The left node is printed, the right node is printed, and the left node is printed
public static void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.data + "");
}
Copy the code

Binary tree traversal is very simple, although there are three kinds of traversal method, but is the same, just different output order, after learning so much above, I believe you must have knowledge of binary tree has many, here we are to get to know a kind of common and special binary tree, binary search trees

Binary search tree

Binary search tree is also called binary search tree, from the name we can know that this tree must have a superior advantage in search, the fact is indeed so, binary search tree is really born for search, but it not only supports fast search data, but also supports fast insertion and deletion of a data. So how does it do this? Let’s start with the concept of a binary search tree.

Binary search tree: At any node in the tree, the value of each node in the left subtree is less than the value of this node, and the value of the right subtree node is greater than the value of this node.

Hard to understand? Can’t remember? It doesn’t matter. Now I’ve defined a binary search tree, and we’re going to look at the tree and understand it.

All left nodesIs less than 62,All right nodes

Binary search tree since the name with the word search, then we start from the binary search tree search binary search tree.

The search operation of a binary search tree

Because of the nature of binary search trees, we need to find something, compare it to the root node, if it’s equal to the root node, return the root node, if it’s less than the root node, it must be on the left side of the subtree, just recursively find the left subtree, if it’s greater, it’s on the right side of the subtree, recurse on the right side of the subtree. This enables fast lookup, because each lookup reduces the data in half. Similar to binary lookup, fast insert and delete are implemented with this feature.

Let’s use a dynamic diagram to enhance our understanding of the binary search tree search process. We need to find the value of 37 nodes in the binary search tree above. Let’s see how the flowchart is implemented.

  • 1, compare 37 with 62, 37 < 62, continue to search in the left subtree
  • 2, the node value of the left subtree is 58, 37 < 58, continue to search in the left subtree
  • 3, the node value of the left subtree is 47, 37 < 47, continue to search in the left subtree
  • 4. If the node value of the left subtree is 35, 37 > 35, search in the right subtree
  • 5. If the value of the node in the right subtree is 37, 37 = 37, return the node

After talking about the concept of search, let’s take a look at the binary search tree search operation code implementation

/** * find tree * by value@paramdata&emsp; Value *@return* /
public TreeNode find(int data) {
    TreeNode p = tree;
    while(p ! =null) {
        if (data < p.data) p = p.left;
        else if (data > p.data) p = p.right;
        else return p;
    }
    return null;
}
Copy the code

Insert operations in binary lookup trees

Insertion is similar to search. It starts from the root node. If the data to be inserted is larger than the data of the node and the right subtree of the node is empty, the new data is directly inserted to the position of the right child node. If it is not empty, the right subtree is recursively traversed to find the insertion location. Similarly, if the data to be inserted is smaller than the value of the node and the left subtree of the node is empty, the new data is inserted at the position of the left child node. If it is not empty, the left subtree is recursively traversed to find the insertion location.

Let’s say we want to insert 63, and let’s use a dynamic diagram to see how it works.

  • 1, 63 > 62, continue to search in the right subtree.
  • 2. If 63 < 88, continue the search in the left subtree
  • 3. 63 < 73, because 73 is a leaf node, 63 becomes the left subtree of 73.

Let’s look at the binary search tree insert operation implementation code

/** * insert tree *@param data
 */
public void insert(int data) {
    if (tree == null) {
        tree = new TreeNode(data);
        return;
    }

    TreeNode p = tree;

    while(p ! =null) {
        // If the value is greater than the value of the node, the new tree is the right subtree of the node
        if (data > p.data) {
            if (p.right == null) {
                p.right = new TreeNode(data);
                return;
            }
            p = p.right;
        } else { // data < p.data
            if (p.left == null) {
                p.left = new TreeNode(data);
                return; } p = p.left; }}}Copy the code

Delete operation of binary lookup tree

The logic of delete is more complex than that of search and insert. There are three cases of delete:

Case 1: If the node to be deleted has no children, we simply set the pointer to the node to be deleted to NULL in the parent node. For example, delete node 51 in the figure.

In the second case, if the node to be deleted has only one child (only left child or right child), we only need to update the pointer in the parent node to point to the child of the node to be deleted. For example, delete node 35 in the figure.

The third case is more complicated if the node to be deleted has two children. We need to find the smallest node in the right subtree of this node and replace it with the node we want to delete. Then delete the smallest node, because the smallest node definitely has no left children (if it has left children, it is not the smallest node), so we can apply the above two rules to delete the smallest node. For example, delete node 88 in the figure

The first two cases are a little easier, and in the third case, I made a dynamic diagram that I hope will help you.

Let’s take a look at the binary search tree delete operation code

public void delete(int data) {
    TreeNode p = tree; // p points to the node to be deleted and initialization points to the root node
    TreeNode pp = null; // pp records the parent of p
    while(p ! =null&& p.data ! = data) { pp = p;if (data > p.data) p = p.right;
        else p = p.left;
    }
    if (p == null) return; // Not found

    // The node to be deleted has two children
    if(p.left ! =null&& p.right ! =null) { // Find the smallest node in the right subtree
        TreeNode minP = p.right;
        TreeNode minPP = p; // minPP indicates the parent node of minP
        while(minP.left ! =null) {
            minPP = minP;
            minP = minP.left;
        }
        p.data = minP.data; // Replace minP data with p
        p = minP; // Delete minP
        pp = minPP;
    }

    // Delete node is leaf node or has only one child node
    TreeNode child; // child node of p
    if(p.left ! =null) child = p.left;
    else if(p.right ! =null) child = p.right;
    else child = null;

    if (pp == null) tree = child; // Delete the root node
    else if (pp.left == p) pp.left = child;
    else pp.right = child;
}
Copy the code

We understand the above some bintree related knowledge, since binary search trees in extreme cases can degenerate into a linked list, each node has only one left node, for example, it’s time complexity becomes a O (n), in order to avoid this kind of situation, there is a new kind of tree is called balanced binary search trees, because the article is a bit long, I believe that you are a little tired to see here, and I will not introduce the relevant knowledge of balanced binary search tree here.

The last

Play a small advertisement, welcome to scan the code to pay attention to the wechat public number: “The technical blog of the flathead brother”, progress together.

The resources

  • The Beauty of Data Structures and Algorithms (Geek Time)