A text will take you to understand binary tree

introduction

Original link: A text will take you to understand binary tree I hope you can pay attention to my official account. There is a QR code at the end of the text. Thank you!

 

1. Basic concepts of binary tree

 

Binary tree definition: the degree of a node is at most 2

Five forms of binary tree:

  • Empty binary tree

  • There is only one root node

  • The root node has only the left subtree

  • The root node has only right subtree

  • The root node has both left and right subtrees

 

Special binary tree:

  • Skew tree: it is divided into left skew tree and right skew tree. In fact, it is a linear structure

  • Full binary tree: as shown in Figure 1.

  • Complete binary tree: as shown in Figure 2. A full binary tree must be a complete binary tree, but a complete binary tree is not necessarily full. The three trees in Figure 3 are not completely binary trees.

 

Figure 1

 

 

Figure 2

 

 

Figure 3

 

 

2. Properties of binary tree

 

  1. There are at most 2i-1 nodes on the i-th layer of the binary tree;

  2. A binary tree with a depth of K has at most 2k-1 nodes;

  3. For any binary tree T, if its leaf node number is n0 and the node number with degree 2 is n2, then n0=n2+1;

  4. The depth of a complete binary tree with n nodes is | log2n+1 | (| x | represents the largest integer not greater than x);

  5. The nodes of a complete binary tree with n nodes are numbered according to the sequence (from top to bottom, from left to right, as shown in Figure 4). For any node i (1 ≤ I ≤ n):

  • The left child of node i is 2i and the right child is 2i+1.

  • If I > n / 2, node i has no left child (node I is a leaf node).

  • If I > (n-1) / 2, node i has no right child.

Figure 4

 

 

Let's prove the above properties. 1. 2. 4 this is very understandable, and there is no need to prove it.

 

On the third point, why n0=n2+1? First of all, there is no doubt that n=n0+n1+n2.

Then we turn our attention to the branch line, not the node.

For a binary tree with n nodes, except that there is no branch line on the top of the root node to connect it, there is only one branch line on the top of the other nodes, so the total number of branch lines = n0+n1+n2-1.

There are 2 branch lines under the node with degree 2, 1 for degree 1 and 0 for degree 0, so the total number of branch lines = 2*n2+n1.

According to the above two formulas marked in red, we can draw a conclusion.

 

As for the fifth point, in fact, we only need to prove that the left child of node i is 2i. The following conclusions are based on this conclusion. The following proof relates to figure 4. Notice that this is a completely binary tree.

First, we prove whether the leftmost node i of each layer of the tree satisfies that the left child is 2I (the left child must be on the leftmost of the next layer of the node). For example, prove whether the left child of node 4 is 8. Assuming that node 4 is in layer K (of course, node 4 is in layer 3, and K is only for the general situation), then the value of node 4 is 2k-1 and the value of the left child of node 4 is 2K, so it is satisfied.

Next, it is proved whether the leftmost node i not in each layer satisfies that the left child is 2i. For example, prove whether the left child of node 5 is 10. Set the leftmost node as I, node 5 is offset by N units relative to the leftmost node of this layer (that is, node 5 is offset by 1 unit relative to node 4, n is only for general conditions), and the value of node 5 is i+n; The left child must be offset by 2n units, and the value bit 2i+2n of the left child of node 5 is satisfied.

 

 

3. Storage structure of binary tree

 

For general trees, it is not suitable to use sequential storage structure to store the logical relationship of trees, but binary trees, as a special tree, can do so. As shown in the figure below.

 

This chart shows that an array is used to store an ordinary binary tree. If a node does not exist, it is represented by a null value. For ordinary binary trees, sequential storage is obviously a waste of space, so the sequential storage structure is generally only suitable for complete binary trees.

 

The second is to use a binary linked list. Because as a binary tree, it is easy to think that each node should store the value of the node and the pointers of the left and right children. If you want to quickly find the parents of a node, you can also add a parent pointer. The binary linked list is shown in the figure below.

 

 

 

 

4. Traversal of binary tree

 

Traversal of binary tree: traverse all nodes in the tree once according to a certain order.

Traversal mode:

  • Preorder traversal

  • Ergodic middle order

  • Postorder traversal

  • Sequence traversal: from top to bottom, from left to right.

Among them, the front, middle and back are relative to the root node of any subtree.

 

The following three traversal methods are implemented in Java code.

First, define the node class.

public class Node{
    private Node left;
    private char data;
    private Node right;

    public Node(Node left, char data ,Node right) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    // Omit getter/setter method
}

 

Then define the traversal class, which has three methods, corresponding to the first, middle and last traversal respectively. Because the definition of the tree adopts the idea of recursion, the traversal of the tree also adopts recursion. In addition, this class also has a method to build a tree, as shown in the following figure. The last is the main method. I believe everyone can understand it.

 

public class BinaryTreeTraverse {
    /**
     * Preorder
     */
    public void firstTraverse(Node node){
        if(node == null){
            return;
        }
        System.out.print(node.getData());
        firstTraverse(node.getLeft());
        firstTraverse(node.getRight());
    }
    /**
     * Middle order
     */
    public void middleTraverse(Node node){
        if(node == null){
            return;
        }
        middleTraverse(node.getLeft());
        System.out.print(node.getData());
        middleTraverse(node.getRight());
    }
    /**
     * Post order
     */
    public void laterTraverse(Node node){
        if(node == null){
            return;
        }
        laterTraverse(node.getLeft());
        laterTraverse(node.getRight());
        System.out.print(node.getData());
    }

    /**
     * Build a binary tree and return the root node
     */
    public Node buildTree(){
        Node node_k = new Node(null, 'K', null);
        Node node_h = new Node(null, 'h', node_k);
        Node node_d = new Node(node_h, 'd', null);
        Node node_e = new Node(null, 'e', null);
        Node node_b = new Node(node_d, 'b', node_e);
        Node node_i = new Node(null, 'i', null);
        Node node_j = new Node(null, 'j', null);
        Node node_f = new Node(node_i, 'f', null);
        Node node_g = new Node(null, 'g', node_j);
        Node node_c = new Node(node_f, 'c', node_g);
        Node node_a = new Node(node_b, 'a', node_c);
        return node_a;
    }

    public static void main(String[] args) {
        BinaryTreeTraverse traverse = new BinaryTreeTraverse();
        Node root = traverse.buildTree();
        //Preorder traversal 
        traverse.firstTraverse(root);
        System.out.println();

        //Ergodic middle order
        traverse.middleTraverse(root);
        System.out.println();
        //Postorder traversal
        traverse.laterTraverse(root);

    }

}

 

 

5. Establishment of binary tree

 

The above mentioned traversal of binary tree, but if we don't have a binary tree in our memory, where can we get traversal? So let me talk about the establishment of binary tree.

The above example actually includes the establishment of binary tree, but it is established through hard coding, which is not in line with the general situation.

We can reverse construct the binary tree through the traversal results of the binary tree. For example, the preorder traversal can build a binary tree according to its preorder traversal results. In addition, we need to add some virtual nodes to ensure that we can successfully build a binary chain in memory.

 

The binary tree prototype built this time is shown in the figure below.

Then we add some virtual nodes, as shown in the figure below.

 

The original preorder traversal result should be: ABDHKECFIGJ. We record the virtual node as # (other symbols can also be used), and the preorder traversal result will become: abdh#k####e##cfi###g#j##, which is easy to make mistakes. We must be careful, otherwise the input (i.e. the traversal result is regarded as input and the constructed binary tree is regarded as output) is wrong, then the constructed binary tree must also be wrong.

 

The construction of binary tree is also realized by recursion. The following is implemented with Java code to build a binary tree through the result of preorder traversal.

The first is the Node class.

public class Node{
    private Node left;
    private char data;
    private Node right;

    public Node(Node left, char data ,Node right) {
        this.left = left;
        this.right = right;
        this.data = data;
    }
    // Omit getter/setter method

    @Override
    public String toString() {
        return "Node{" +
                "left=" + (left==null?"null":left.getData()) +
                ", data=" + data +
                ", right=" + (right==null?"null":right.getData()) +
                '}';
    }
}

 

Then is the specific implementation logic.

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeBuilder {
    private List<Node> nodes;
    /**
     * For index tracking, add 1 for each node built, including virtual nodes
     */
    private int index;

    /**
     * Building a node is only applicable to pre order construction
     * @param curIndex The index of the node. The index cannot only be stored in the method inn
     */
    public void buildNode(int curIndex){
        index++;
        //If the node to be built is a virtual node, you don't need to build a left subtree and a right subtree. return directly;
        if(null == nodes.get(curIndex)){
            return;
        }
        // Recursive construction of left subtree
        buildLeft(curIndex);
        // Recursive construction of right subtree
        buildRight(curIndex);
    }

    /**
     * Construct left subtree
     * @param curIndex To build the index of the left child's node
     */
    public void buildLeft(int curIndex){
        //Set left child
        nodes.get(curIndex).setLeft(nodes.get(index));
        //Build the left child node, so the incoming index is the left child's index
        buildNode(index);
    }

    /**
     * Constructing right subtree
     * @param curIndex To build the index of the node of the right child
     */
    public void buildRight(int curIndex){
        //Set right child
        nodes.get(curIndex).setRight(nodes.get(index));
        //Build the right child node, so the incoming index is the right child's index
        buildNode(index);
    }

    public void initNodes(char[] arr){
        nodes = new ArrayList<>();
        for (char c : arr) {
            if(c=='#'){
                nodes.add(null);
            }else{
                nodes.add(new Node(null,c,null));
            }
        }
    }

    /**
     * After the construction is completed, print the construction results
     */
    public void buildOK(){
        for (Node node : nodes) {
            if(null == node){
                continue;
            }
            System.out.println(node.getData()
                    +" -(Left child->"+(node.getLeft()==null?"null":(node.getLeft().getData()+" "))+")"
                    +" -(Right child->"+(node.getRight()==null?"null":(node.getRight().getData())+" ")+")");
        }
    }

    public void buildTree(char[] arr,String charArrType){
        initNodes(arr);
        if("Preorder construction".equals(charArrType)){
            buildNode(0);
        }else if("Middle order construction".equals(charArrType)){
            // Please refer to the buildNode pre order construction method to realize the medium order construction

        }else if("Post order construction".equals(charArrType)){
            // Please refer to the buildNode pre order construction method to realize the post order construction

        }else{
            return;
        }
        buildOK();
    }

    public static void main(String[] args) {
        BinaryTreeBuilder builder = new BinaryTreeBuilder();
        builder.buildTree("ABDH#K###E##CFI###G#J##". toCharArray()," build in sequence ");
    }
}

 

 

Finally, run the program, and the constructed results are shown in the figure below.

 

I carefully verified that there is no problem. As for the logic of constructing binary tree according to the middle and post order traversal results, it's up to you to use your brain to realize it!

 

I think it's well written. Please scan the code and pay attention to my official account. Thank you!

Tags: data structure Binary tree

Posted by fahrvergnuugen on Sat, 30 Apr 2022 01:27:55 +0300