All about Trees in Data Structures (Java Edition)

A picture of a tree I made when I was a young boy.

When you first learn coding, most people learn arrays as their primary data structure.

After that, you’ll learn about hash tables. If you’re a computer science major, you definitely need to take a course in data structures. You’ll also learn about linked lists, queues and stacks. These are collectively referred to as linear data structures because they logically have a beginning and an end.

When you start to learn about the data structure of trees and graphs, it can be so confusing. Because it’s not linear, they all have their own specific way of storing data.

This article will help you better understand tree data structures and help you solve your questions as much as possible. In this chapter we will learn

• What is a tree?
• An example of a simple tree
• Tree terminology and how it works
• How do YOU implement a tree structure in your code

define

When learning programming, it’s easier to understand linear data structures than tree and graph data structures.

Trees are well-known nonlinear data structures. They don’t store data in a linear fashion. They organize the data in hierarchies.

Let’s take a real life example

What exactly do we mean by hierarchical organization?

Think of our family tree: grandparents, parents, children, siblings, and so on. We usually organize our family tree in hierarchies.

My family tree

The picture above is my family tree. Tossico, Akikazu, Hitomi and Takemi are my grandparents.

Toshiaki and Juliana are my parents.

TK, Yuji, Bruno and Kaio are my parents’ children (me and my brothers).

Another example of a hierarchy is the organizational structure of an enterprise.

The structure of a company is also an example of a hierarchy

In HTML, the document Object Model (DOM) is a tree structure.

Document Object Model (DOM)

HTML tags contain other tags. We have a head tag and a body tag. These tags contain characteristic elements. The head tag contains the meta and title tags. The body tag has tags that are displayed in the user interface, such as H1, A, Li, and so on.

Tree terminology definition

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains values or dates, and each node may or may not have children.

The first node of the tree is called the root. If the root is connected to another node, then the root is the parent node and the root is connected to the child node.

All nodes are connected by edges. It is an important concept in the tree because it is responsible for managing the relationships between nodes.

Leaves, “leaves,” are the ends of a tree. They have no children. Like a real tree, we can see that it has roots, branches and leaves.

Height and depth of the tree

• The height of the tree is the length to the leaf node (the end of the tree)
• The depth of a node is its length from the root node

The term summary

• The root is the topmost node of the tree
• An edge is a connection between two nodes
• A child is a node with a parent
• A parent is a node connected to a child
• A leaf node is a node in a tree with no children (the end of the tree)
• Height is the length of the tree from the leaf node (the end of the tree)
• Depth is the length from node to root

Binary tree

Now let’s talk about a particular type of tree. Let’s call it a binary tree.

“In computer science, a binary tree is a tree data structure with up to two children per node, known as left child and right child” — Wikipedia

So let’s write a binary tree

The first thing we need to keep in mind when we implement a binary tree is that it’s a set of nodes. Each node has three attributes: value, left_child, and right_child.

So how can we implement a simple binary tree with these three properties?

Let’s implement an example of a binary tree

/**
 * Created on 2018/4/16.
 *
 * @author zlf
 * @since1.0 * /
public class BinaryTree {

    public BinaryTree left; / / the left node

    public BinaryTree right; / / right node

    public String data;  // The contents of the tree

    public BinaryTree(a) {}/** * constructor **@param data
     * @param left
     * @param right
     */
    public BinaryTree(String data, BinaryTree left, BinaryTree right) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    /** * constructor **@param data
     */
    public BinaryTree(String data) {
        this(data, null.null);
    }
Copy the code

Ok, so that’s our binary tree

When we instantiate an object, we pass the value (the data associated with the point) to the class as an argument. Look at the left and right child of the class above. Both are assigned null.

Why is that?

Because when we created the node, it didn’t have children, it just had node data.

The test code

   /** * Build the tree */
    public static void testCreate(a) {
        BinaryTree node = new BinaryTree("a");

        System.out.println("[node data] :" + node.getData());
        System.out.println("[node left data] : + (node.left==null?"null":node.left.getData()));
        System.out.println("[node right data] : + (node.right==null?"null":node.right.getData()));
    }
Copy the code

Output:

【node data】:a
【node left data】:null
【node right data】:null
Copy the code

We can pass the string ‘a’ as an argument to the binary tree. If we output the value, the left child node, and the right child node, we can see this value.

Let’s start the insert section. So what do we need to do?

There are two requirements:

• If the current node has no left child, we create a new node and set it to the left of the current node.

• If we already have a left node, we create a new one and place it where the current left node is. And then I’m going to take the value of the old left node to the left node of the new left node.

The graph is as follows:

Here is the code to insert:

 /** * insert the node, if the current node does not have a left node, we create a new node and set it to the left node of the current node. * *@param node
     * @param value
     */
    public static void insertLeft(BinaryTree node, String value) {
        if(node ! =null) {
            if (node.left == null) {
                node.setLeft(new BinaryTree(value));
            } else {
                BinaryTree newNode = newBinaryTree(value); newNode.left = node.left; node.left = newNode; }}}Copy the code

Again, if the current node has no left, we create a new node and set it to the left of the current node. Otherwise, you put the new node where the left node is, and then you put the old left node where the new left node is.

Again, we write the code that inserts the right node

/** * insert the left node *@param node
    * @param value
    */
   public static void insertRight(BinaryTree node, String value) {
       if(node ! =null) {
           if (node.right == null) {
               node.setRight(new BinaryTree(value));
           } else {
               BinaryTree newNode = newBinaryTree(value); newNode.right = node.right; node.right = newNode; }}}Copy the code

But this is not done. We have to test it.

Let’s construct a tree that looks like this:

• We have one root
• B is the left node
• C is the right node
• The nodule of B is D (b has no left node)
• The left node of C is e
• The right node of c is f
• E and f have no children

Here is the implementation code for this tree:

/**
     * 测试插入结点
     */
    public static void testInsert(a) {
        BinaryTree node_a = new BinaryTree("a");
        node_a.insertLeft(node_a, "b");
        node_a.insertRight(node_a, "c");

        BinaryTree node_b = node_a.left;
        node_b.insertRight(node_b, "d");

        BinaryTree node_c = node_a.right;
        node_c.insertLeft(node_c, "e");
        node_c.insertRight(node_c, "f");

        BinaryTree node_d = node_b.right;
        BinaryTree node_e = node_c.left;
        BinaryTree node_f = node_c.right;

        System.out.println("[node_a data] : + node_a.getData());
        System.out.println([node_b data] : + node_b.getData());
        System.out.println("[node_c data] : + node_c.getData());
        System.out.println("[node_d data] : + node_d.getData());
        System.out.println("[node_e data] : + node_e.getData());
        System.out.println("[node_f data] : + node_f.getData());
    }
Copy the code

Output:

Node_a data: A node_B data: B node_C data: C node_D data: D node_e data: E node_F data :fCopy the code

Insert is done

Now, let’s consider tree traversal.

Tree traversal has two options, depth-first search (DFS) and breadth-first search (BFS).

DFS is an algorithm for traversing or searching tree data structures. Starting at the root, explore as far as possible along each branch before backtracking. – Wikipedia

BFS is an algorithm for traversing or searching tree data structures. Starting from the root node, neighbors at the same level are explored before exploring neighbor nodes at the next level. – Wikipedia

Let’s take a closer look at each of these traversal algorithms.

Depth-first Search (DFS)

DFS finds a path to a leaf before backtracking and searching for other paths. Let’s look at an example of this type of traversal.

The output is 1-2-3-4-5-6-7

Why is that?

Let’s break it down:

1. We start at root (1). The output
2. Enter the left node (2). The output
3. Then enter the left child (3). The output
4. Backtrack and enter right child (4). The output
5. Go back to the root and enter its right child (5). The output
6. Enter the left child (6). The output
7. Backtrack and enter right child (7). The output
8. complete

Backtracking as we get down to the leaves, this is called the DFS algorithm.

Now that we are familiar with this traversal algorithm, we will discuss the types of DFS: pre-order, mid-order, and post-order.

The former sequence traversal

This is basically similar to what we did in the example above.

1. Prints the value of the node
2. Enter its left node and print. If and only if it has a left node.
3. Enter the right node and print. If and only if it has a right node

/** * traverses ** in order@param node
     */
    public static void preOrder(BinaryTree node) {
        if(node ! =null) {

            System.out.println(node.data);

            if(node.left ! =null) {
                node.left.preOrder(node.left);
            }

            if(node.right ! =null) { node.right.preOrder(node.right); }}}Copy the code

In the sequence traversal

The result of the middle-order algorithm for this tree in the example is 3-2-4-1-6-5-7.

The left takes precedence, then the middle, and then the right.

Code implementation:

/ sequence traversal in the * * * * *@param node
     */
    public static void inOrder(BinaryTree node) {
        if(node ! =null) {
            if(node.left ! =null) {
                node.left.inOrder(node.left);
            }

            System.out.println(node.data);

            if(node.right ! =null) { node.right.inOrder(node.right); }}}Copy the code

1. Enter the left node and print it. If and only if it has a left node.
2. Prints the value of the root.
3. Enter the nodule and exit it. If and only if it has nodules.

After the sequence traversal

The result of the back-order algorithm based on this tree is 3 — 4 — 2 — 6 — 7 — 5 — 1.

The left node takes precedence, the right node takes precedence, and the root node comes last.

Code implementation:

/ sequence traversal after * * * * *@param node
     */
    public static void postOrder(BinaryTree node) {
        if(node ! =null) {
            if(node.left ! =null) {
                node.left.postOrder(node.left);
            }

            if(node.right ! =null) { node.right.postOrder(node.right); } System.out.println(node.data); }}Copy the code

1. Go to the left node and output,
2. Enter the output of the right node
3. Output root

Breadth First Search (BFS)

BFS is a step-by-step traversal algorithm

The following example is to help us better explain the algorithm.

Let’s walk through the tree layer by layer. In this case, 1-2-5-3-4-6-7.

• Layer 0 / depth 0: only nodes with a value of 1
• Layer 1 / depth 1: nodes with values 2 and 5
• Layer 2 / depth 2: nodes with values of 3, 4, 6, 7

Code implementation:

/** ** width sort **@param node
     */
    public static void bfsOrder(BinaryTree node) {
        if(node ! =null) {
            Queue<BinaryTree> queue = new ArrayDeque<BinaryTree>();
            queue.add(node);

            while(! queue.isEmpty()) { BinaryTree current_node = queue.poll(); System.out.println(current_node.data);if(current_node.left ! =null) {
                    queue.add(current_node.left);
                }
                if(current_node.right ! =null) { queue.add(current_node.right); }}}}Copy the code

To implement the BFS algorithm, we need to use a data structure called a queue.

What exactly is a queue for?

Please see the explanation below.

1. The root node is first added to the queue using the add method.
2. Iterates when the queue is not empty.
3. Gets the first node in the queue and prints its value
4. Add the left and right nodes to the queue
5. With the help of the queue we are going to print each node value layer by layer

Binary search tree

Binary search trees are sometimes called binary ordered trees or binary sort trees. The values of binary search trees are stored in ordered order. Therefore, lookup tables and other operations can use the principle of split search. – Wikipedia

An important property of binary search tree is that the value of a node in binary search tree is greater than its left node, but less than its right node

• It’s an inverse binary search tree. Subtree 7-5-8-6 should be on the right, and subtree 2-1-3 should be on the left.
• Is the only correct choice. It satisfies the properties of a binary search tree
• There is a problem: the node with the value of 4 should be to the left of the root node, because the value of this node is less than the value of 5.

Code to achieve binary tree search

Insert: Adds new nodes to our tree

Now imagine that we have an empty tree and we want to add nodes to the tree. The values of these nodes are: 50, 76, 21, 4, 32, 100, 64, 52.

The first thing we need to know is whether 50 is the root of this tree.

Now let’s start inserting nodes one by one

• 76 is bigger than 50, so 76 is inserted on the right-hand side.
• 21 is less than 50, so 21 is inserted on the left.
• 4 is less than 50. But 50 already has a left value of 21. And then 4 is less than 21, so I put it to the left of 21.
• 32 is less than 50. But 50 already has a left value of 21. And then 32 is bigger than 21, so I put it to the right of 21.
• 100 is greater than 50. But 50 already has a right node of 76. And then 100 is bigger than 76, so I put it to the right of 76.
• 64 is greater than 50. But 50 already has a right node of 76. And then 64 is less than 76, so I put it to the left of 76.
• 52 is greater than 50. But 50 already has a right node of 76. 52 is smaller than 76, but 76 also has a left value of 64. 52 is less than 64, so I insert 52 to the left of 64.

Do you notice a pattern here?

Let’s break it down.

1. Is the value of the new node greater or less than the current node?
2. If the value of the new node is greater than the value of the current node, go to the right node. If the current node has no right node, insert a new node there, otherwise return to Step 1.
3. If the value of the new node is less than the value of the current node, it goes to the left node. If the current node has no left node, insert a new node there, otherwise return to Step 1.
4. We’re not dealing with special cases here. When the value of the new node is equal to the current value of the node, use rule 3. Consider inserting equal values to the left of the child.

Code implementation:

/** * insert tree **@param node
     * @param value
     */
    public void insertNode(BinaryTree node, Integer value) {
        if(node ! =null) {
            if(value <= Integer.valueOf(node.data) && node.left ! =null) {
                node.left.insertNode(node.left, value);
            } else if (value <= Integer.valueOf(node.data)) {
                node.left = new BinaryTree(String.valueOf(value));
            } else if(value > Integer.valueOf(node.data) && node.right ! =null) {
                node.right.insertNode(node.right, value);
            } else {
                node.right = newBinaryTree(String.valueOf(value)); }}}Copy the code

It looks simple enough.

The power of this algorithm is in its recursive section, lines 9 and 13. Both lines of code call the insertNode method and use it for its left and right nodes, respectively. Lines 11 and 15 insert new nodes at child nodes.

Search node

The algorithm we’re going to build now is about search. For a given value (integer), we search to find out if our binary search tree has or does not have that value.

One important thing to note is how we define the tree insertion algorithm. First we have the root. All left children have node values smaller than the root. All right subtrees have greater values than the root node.

Let’s look at an example.

So let’s say we have this tree.

Now we want to know if there’s a node that has a value of 52.

Let’s break it down.

1. We start with the root as the current node. Is the given value less than the current node value? If it is, then I will look for it in the left subtree.
2. Is the given value greater than the current node value? If it is, then we will look for it in the right subtree.
3. If rules #1 and #2 are both false, we can compare the current node value to the given value. If it returns true, then we can say: “Yes, our tree has the given value.” Otherwise, we say, “No, our tree doesn’t have a given value.”

Code implementation:

/** * find if the node has **@param node
     * @param value
     * @return* /
    public boolean findNode(BinaryTree node, Integer value) {
        if(node ! =null) {
            if(value < Integer.valueOf(node.data) && node.left ! =null) {
                return node.left.findNode(node.left, value);
            }
            if(value > Integer.valueOf(node.data) && node.right ! =null) {
                return node.right.findNode(node.right, value);
            }
            return value == Integer.valueOf(node.data);
        }
        return false;
    }

Copy the code

Code analysis:

• Lines 8 and 9 fall under rule #1.
• Lines 10 and 11 fall under rule #2.
• Line 13 goes to rule #3.

Delete: Removes and reorganizes the tree

Deletion is a more complex algorithm because we need to deal with different cases. For a given value, we need to delete the node that has this value. Imagine the following scenario for this node: it has no children, one child, or two children.

A node with no children (leaf node).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|
Copy the code

If the node to be deleted has no children, we simply delete it. This algorithm does not require tree reorganization.

A node with only one child (left or right).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|
Copy the code

In this case, our algorithm needs to make the node’s parent point to its child. If the node is a left child, make its parent point to its child. If the node is a right child, make its parent point to its child.

Node with two children.

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|      
Copy the code

When a node has two children, you need to find the node with the smallest value, starting with the child to the right of the node. We will place the node with the minimum at the position of the deleted node.

Code implementation:

    /** * Delete node *@param node
     * @param value
     * @param parent
     * @return* /
    public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {
        if(node ! =null) {
            if(value < Integer.valueOf(node.data) && node.left ! =null) {
                return node.left.removeNode(node.left, value, node);
            } else if (value < Integer.valueOf(node.data)) {
                return false;
            } else if(value > Integer.valueOf(node.data) && node.right ! =null) {
                return node.right.removeNode(node.right, value, node);
            } else if (value > Integer.valueOf(node.data)) {
                return false;
            } else {
                if (node.left == null && node.right == null && node == parent.left) {
                    parent.left = null;
                    node.clearNode(node);
                } else if (node.left == null && node.right == null && node == parent.right) {
                    parent.right = null;
                    node.clearNode(node);
                } else if(node.left ! =null && node.right == null && node == parent.left) {
                    parent.left = node.left;
                    node.clearNode(node);
                } else if(node.left ! =null && node.right == null && node == parent.right) {
                    parent.right = node.left;
                    node.clearNode(node);
                } else if(node.right ! =null && node.left == null && node == parent.left) {
                    parent.left = node.right;
                    node.clearNode(node);
                } else if(node.right ! =null && node.left == null && node == parent.right) {
                    parent.right = node.right;
                    node.clearNode(node);
                } else {
                    node.data=String.valueOf(node.right.findMinValue(node.right));
                    node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);
                }
                return true; }}return false;
    }
Copy the code

1. First: Pay attention to the parametersvalue 和 parent. We want to find the value equal to thisvalue 的 nodeAnd thenodeThe parent node of thenodeIs of the utmost importance.
2. Second: Note the return value. Our algorithm will return a Boolean value. Our algorithm returns when the node is found and deletedtrue. Otherwise returnsfalse 。
3. Lines 2 through 9: We start looking for something equal to the given thing we’re looking forvalue 的 node. If thevalueLess thancurrent nodeValue, we enter the left subtree, recursively processing (if and only if,current nodeHave left child). If the value is greater than, the right subtree is entered. Recursive processing.
4. Line 10: Let’s start thinking about the deletion algorithm.
5. Lines 11 through 13: We deal with nodes that have no children and are left children of the parent node. We delete the parent node by making the left child of the parent node empty.
6. Lines 14 and 15: We deal with nodes that have no children and are the right child of the parent node. We delete the parent node by making the right child of the parent node empty.
7. How to clear the node: I will present the code for clear_node in a future article. This function sets the left child, right child, and value of the node to null.
8. Lines 16 to 18: We deal with a node that has only one child (the left child) and is the left child of its parent. We set the left child of the parent node to the left child of the current node (which is the only child it has).
9. Lines 19 to 21: We deal with a node that has only one child (the left child) and is the right child of its parent. We set the right child of the parent node to the left child of the current node (which is the only child it has).
10. Lines 22 through 24: We deal with a node that has only one child (the right child) and is the left child of its parent. We set the left child of the parent node to the right child of the current node (which is its only child).
11. Lines 25 to 27: We deal with a node that has only one child (the right child) and is the right child of its parent. We set the right child of the parent node to the right child of the current node (which is its only child).
12. Lines 28 through 30: We deal with nodes that have both left and right children. We get the node with the minimum value (shown in the code later) and set its value to the current node. Remove a node by deleting the smallest node.
13. Line 32: If we find the node we are looking for, we need to returntrue. From lines 11 through 31, we deal with these cases. So just go backtrueThat’s enough.

• Clear_node method: Set three attributes of the node to null — (value, left_Child, and right_child)

/** * Clear the n node **@param node
     */
    public void clearNode(BinaryTree node) {
        node.data = null;
        node.left = null;
        node.right = null;
    }
Copy the code

• Find_minimum_value method: Go all the way down to the left. If we can’t find any nodes, we find the smallest of them

/** * find the minimum value in the tree */
    public Integer findMinValue(BinaryTree node) {
        if(node ! =null) {
            if(node.left ! =null) {
                return node.left.findMinValue(node.left);
            } else {
                returnInteger.valueOf(node.data); }}return null;
    }
Copy the code

Everything you need to know about tree data structures

Code download:

All about Trees in Data Structures (Java Edition)

Recommend the article

1. Java creates the blockchain family
2. Spring Security source code analysis series
3. Spring Data Jpa series

🙂🙂🙂 focus on wechat small program Java architect journey Bored on the commute? Still reading novels, news? Don’t know how to improve your skills? Here’s the Java architecture article you need. 1.5W + Java engineers are reading it. What are you waiting for?