Data Structures and Algorithms 5 - Nonlinear - Trees

A total of eight articles in the data structure and algorithm series

Introduce a tool

1. Concept

1-1. What is a tree

A tree is a data structure composed of nodes or vertices and edges (possibly non-linear) without any cycles.
A tree without nodes is called an empty (null or empty) tree. A non-empty tree consists of a root node and (probably) multiple additional nodes, all of which form a multi-level hierarchy.

1-2. degrees

Degree is divided into

  • The degree of the node, which contains several child nodes (sons)
  • A node with a degree of 0 is called a leaf node
  • The top layer used to be the root node root
  • Nodes whose degree is not 0 are called internal nodes except the root
  • The degree of the tree, the maximum degree of each node is called the degree of the tree (m-ary tree)

1-3. Depth

Depth (depth) is also called level (level),root is the first layer, its child node is the second layer, the child's child is the third layer... and so on

1-4. Classification of trees

order points

If the nodes of the tree are in order, it is an ordered tree, and if there is no order, it is unordered

Node points

According to all nodes in the tree, the maximum tree of the child nodes of a node is m, that is, the m-ary tree (based on the most, that is, the degree of the tree)

number of trees

Multiple trees make up a forest, and a tree is just a special forest.

1-5. Relationship between nodes

Direct relationship

  • Parent node: a node directly preceding the node
  • Child node: a node directly after the node
  • Sibling nodes: other nodes of the same parent node

indirect relationship

  • Ancestors: All nodes on the branch from the root to the node;
  • Descendants: Any node in the subtree rooted at a node is called the descendant of the node.
  • Cousins โ€‹โ€‹Node: Nodes whose parents are on the same layer are cousins โ€‹โ€‹of each other

2. Binary tree

A binary tree is a special tree whose m-ary tree is 2 (ie: the degree of the tree is less than or equal to 2).

2-1. Binary tree features

If you are interested, you can see the proof

2-2. Binary tree classification

2-2-1. Full binary tree

A binary tree of height k and 2k+1−12^{k+1}-12k+1−1 nodes.

2-2-2. Complete Binary Tree

Based on a full binary tree, at the bottom layer, several adjacent leaf nodes are removed from the far right, and the resulting binary tree is called a complete binary tree.

2-3. Storage structure of binary tree

  • sequential array storage
  • chain structure storage

2-3-1. Sequential array storage

If it is a complete binary tree, using sequential storage is fine. But if it is not a complete binary tree, there will be space left in the middle, occupying space.

2-3-2. Chain structure storage

The linked list structure is more suitable for binary tree storage. Node node structure: left child node, data, right child node.

Such a data structure can only guarantee that the parent finds the child, but cannot guarantee that the child finds the parent. (If the child needs to find the parent, it needs to add more parent node storage)

3. Traverse

Binary tree traversal is divided into three types according to the position of the root

  • Preorder Traversal: Root-Left-Right DLR
  • Inorder Traversal: Left-Root-Right LDR
  • Postorder Traversal: Left-Right-Root LRD

3-1. Preorder traversal

Mantra: First visit the root, then traverse the left subtree in preorder, and finally traverse the right subtree in preorder

traditional analysis

1. Find root-1, then child node-4 on the left and node-1 on the right. got 1 4_ 2_
2. Re-analyze the node-4 on the left, the left child node of node-4 is not, and the right child node is node-5. got 1 4 5 2_
3. No on the left, in the analysis on the right node-2, the left child node-3 of node-2, and the right child node-6. got 1 4 5 2 3 6 _
4. Re-analyze node-3, there are no left and right child nodes, it is leaf
5. Re-analyze node-6, the left child node has no, and the right child node-7. got 1 4 5 2 3 6 7

personal skills

Note the direction of the arrow above. From the top left, one layer at a time, the result is the preorder result.

Use our little trick to try the previous binary tree and see if you get the same result.

3-2. Inorder traversal

Mantra: First traverse the left subtree in inorder, then visit the root, and finally traverse the right subtree in inorder

traditional analysis

1. Find root-1 and put it in the middle, then the left sub node-4 is placed on the left, and the right sub node-1 is placed on the right. Get _4_ 1 2_ (the underscores are 4 and 2 at this time)
2. Re-analyze the node-4 on the left, the left child node of node-4 is not, and the right child node is node-5. Get 4 5 1 _2_ (the underscore is 2 at this time)
3. There is no left side, in the analysis of the right node-2, the left child node-3 of node-2 is placed on the left, and the right child node-6 is placed on the right. Get 4 5 1 _3_2_6_ (the underscores are 3 and 6 at this time)
4. Re-analyze node-3, there are no left and right child nodes, it is leaf. 4 5 1 3 2_6_(3 has no left and right, then delete the left and right underscores of 3)
5. Re-analyze node-6, the left child node does not have it, and the right child node-7 is put on the right test. got 4 5 1 3 2 6 7

personal skills

Because the root is in the middle, isn't that the same as our binary tree!!! (left root right, LDR), so flattening the binary tree directly to a line, isn't that the required order? Isn't it so easy๐Ÿ˜€!
I believe that when you see this, you definitely want to pull the article to the end, give me a big like๐Ÿ‘ or comment (go, don’t stop you ๐Ÿ˜„, remember to come back to me, and then look down).

Use our little trick to try the previous binary tree and see if you get the same result.

3-3. Post-order traversal

Mantra: First traverse the left subtree in inorder, then traverse the right subtree in inorder, and finally visit the root

traditional analysis

1. Find the root-1 and put it at the end, then put the left child node-4 on the left 1 side, and the right child node-1 on the left 2 side. Get _4 _2 1 (the underscores are 4 and 2 at this time)
2. Re-analyze the node-4 on the left, the left child node of node-4 does not have it, and the right child node is node-5 on the left 2 side. Get 5 4 _2 1 (the underscore is 2 at this time)
3. There is no left side, in the analysis of the right node-2, the left child node-3 of node-2 is placed on the left side, and the right child node-6 is placed on the left 2 side. Get 5 4 _3 _6 2 1 (the underscores are 3 and 6 at this time)
4. Re-analyze node-3, there are no left and right child nodes, it is leaf. 5 4 3 _6 2 1 (3 has no left and right, then delete the left and right underscores of 3)
5. Re-analyze node-6, the left child node does not have it, and the right child node-7 is placed on the left 2 side. got 5 4 3 7 6 2 1

personal skills

This little trick is not as intuitive as the two above. But it can also come out, which is more verbose. Say it, use what you can understand, and use traditional methods if you don't understand

Formula: from left to right, from bottom to top (left has higher priority than bottom). First look left, then right, and then look straight ahead (similar to Chinese-style crossing the road, look left, then right, and look forward at the end. The right explanation is explained below), every time you encounter a fork in the root, put the root in the final position. (Because it is a post-order traversal, the root one is encountered, and it is directly placed in the last position of the local domain)

  1. Although 6 is lower than 9, 6 is to the left of 9, and the priority of left is higher than that of lower. At the beginning of 6, look up the ancestors until the 4 fork is encountered. Look left, then right, and finally forward. Put 2 at the end. The result is: 7 6 4 _ 2 (the underscore is 2 at this time)
  2. Continue to find the left branch, the leftmost node that has not been processed at the bottom is 9. Go up to find ancestors until 2 does not encounter a fork. The result is: 7 6 4 9 8 5 2
  3. 2 continued to look for ancestors and encountered 1 branch. Put 1 at the end. The result is: 7 6 4 9 8 5 2 _ 1 (the underline is 1 at this time, which means that the right node of 1 traverses the data)
  4. Look at the leftmost and the bottom layer of the right test is 10, and look up the ancestors until you encounter the 1 fork. The result is: 7 6 4 9 8 5 2 10 12 11 3 1

A few points to note here:

  • The priority of the left is higher than that of the lower: although 6 is lower than 9, but 6 is to the left of 9, and the priority of left is higher than that of lower. (While 9 is on tier 5, 6 and 4 are on tier 4 and 3). Because left has higher priority than level (bottom).
  • First look left, then right, and finally look forward: meaning 6 is the left node of 4, and 7 is on the right child of 4. That's the order of 6 first, then 7 and last 4.

Talk about the process of getting off the road: (Everyone knows that the traffic rules in China are on the right), just go to the picture above

1. When crossing the road, before halfway through, look to the left first, because cars drive on the right to prevent cars from rushing over.
2. After halfway through, look to the left to prevent the other half of the car from rushing over
3. After crossing the road, the left and right are safe, and finally look forward and walk

4. Code combat

4-1. Interface

interface

public interface ITree {
    /**
     * empty tree
     *
     * @return
     */
    public boolean isEmpty();

    /**
     * number of tree nodes
     *
     * @return
     */
    public int size();

    /**
     * Get the height of a binary tree
     *
     * @return
     */
    public int getHeight();

    /**
     * Query the node for the specified value
     *
     * @param value
     * @return
     */
    public TreeNode findKey(int value); // find

    /**
     * Preorder recursive traversal
     */
    public void preOrderTraverse();

    /**
     * Inorder traversal recursive operation
     */
    public void inOrderTraverse();

    /**
     * Post-order traversal recursive operation
     */
    public void postOrderTraverse();

    /**
     * Inorder traversal non-recursive operations
     * 1)For any node current, if the node is not empty, the node is pushed onto the stack, and the left subtree node is set to current, and this operation is repeated until current is empty.
     * 2)If the left subtree is empty, the top node of the stack is popped, and after accessing the node, the right subtree of the node is set to current
     * 3) Repeat steps 1 and 2 until current is empty and the nodes in the stack are empty.
     */
    public void inOrderByStack();

    /**
     * Preorder traversal non-recursive operations
     * 1)For any node current, if the node is not empty, visit the node and then push the node to the stack, and set the left subtree node as current, repeat this operation until current is empty.
     * 2)If the left subtree is empty, the top node of the stack is popped, and the right subtree of this node is set to current
     * 3) Repeat steps 1 and 2 until current is empty and the nodes in the stack are empty.
     */
    public void preOrderByStack();

    /**
     * Postorder traversal non-recursive operations
     * 1)For any node current, if the node is not empty, visit the node and then push the node to the stack, and set the left subtree node as current, repeat this operation until current is empty.
     * 2)If the left subtree is empty, take the right subtree of the top node of the stack, if the right subtree is empty or the right subtree has just been visited, visit the node and set preNode to this node
     * 3) Repeat steps 1 and 2 until current is empty and the nodes in the stack are empty.
     */
    public void postOrderByStack();

    /**
     * Traverse a binary tree hierarchically
     */
    public void levelOrderByQueue();

}

Definition of binary node

public class TreeNode {

    private Object data;

    private TreeNode leftChild;

    private TreeNode rightChild;

    public TreeNode(Object data, TreeNode leftChild, TreeNode rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

    @Override
    public String toString() {
        return "TreeNode{" + "data=" + data + ", leftChild=" + leftChild.getData() + ", rightChild=" + rightChild.getData() + '}';
    }
}

4-2. Implementation code

The overall implementation code is finally given as a whole, and each fragment is given first and analyzed.

I tried my best to explain it, but if I really don’t understand it, I have to figure it out by myself.

4-2-1. Empty judgment

public class MyListBinaryTree implements ITree {

    private TreeNode root;

    public MyListBinaryTree(TreeNode root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }
}

Just check if root is empty

4-2-2. Size

public int size() {
        return size(this.root);
    }

private int size(TreeNode node) {
    // Returns 0 if null, plus one if not null
    if (node == null) {
        return 0;
    }
    int leftSize = size(node.getLeftChild());
    int rightSize = size(node.getRightChild());
    // The left and right child nodes will drop once, so as long as the node is null, just add one by yourself
    return leftSize + rightSize + 1;
}

Using recursion, pass in the left child and right child each time. When empty, return 0, otherwise add 1

4-2-3. Tree depth

@Override
    public int getHeight() {
        // Find the depth, that is, who is the longest child node from the root
        return getHeight(root);
    }

private int getHeight(TreeNode node) {
    if (node == null) {
        return 0;
    }
    // left child node
    int leftNum = getHeight(node.getLeftChild());

    // right child node
    int rightNum = getHeight(node.getLeftChild());

    // return big +1
    return leftNum > rightNum ? leftNum + 1 : rightNum + 1;
}

Using recursion, pass in the left child and right child each time. When it is empty, it will return 0, otherwise it will add one to the larger of the left and right return values.

4-2-4. Find

@Override
    public TreeNode findKey(Object value) {
        return this.findKey(value, root);
    }

private TreeNode findKey(Object value, TreeNode node) {
    if (node == null) {
        return null;
    }

    if (node.getData().equals(value)) {
        return node;
    }

    TreeNode leftNode = findKey(value, node.getLeftChild());

    TreeNode rightNode = findKey(value, node.getRightChild());

    if (leftNode != null) {
        return leftNode;
    }

    if (rightNode != null) {
        return rightNode;
    }

    return null;
}

recursive search

4-2-5. Preorder traversal

Implemented recursively

@Override
public void preOrderTraverse() {
    this.preOrderTraverse(root);
}

private void preOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // d output
    System.out.print(node.getData() + " ");
    // l Handling
    preOrderTraverse(node.getLeftChild());
    // r processing
    preOrderTraverse(node.getRightChild());
}

Shit, I don't know where to start. (If you understand it, you can understand it at a glance. If you don’t understand it, words can’t explain it.)
Recursive:
1. Given the termination condition, node is empty and terminated
2. Pass the root node to the method, because of the preorder traversal, so output d first
3. Then pass the left child node to the method as the root to continue processing
4. Pass the right child node to the recursive method as the root to continue processing

stack implementation

@Override
public void preOrderByStack() {
    Deque<TreeNode> stack = new LinkedList<>();
    if (root == null) {
        return;
    }

    // Mind method: move with the current node, and how to access the stack according to the order of DLR, LDR, LRD
    // Point to the current mobile node of the tree
    TreeNode current = root;
    List<Object> result = new ArrayList<>();
    while (current != null || !stack.isEmpty()) {
        // Put all the left child nodes of the current node on the stack, and loop consistently until the left child node is null
        while (current != null) {
            // output
            result.add(current.getData());
            stack.push(current);
            // To move the position of the current node to the current node (ie the left node)
            current = current.getLeftChild();
        }

        // If the stack is not empty, pop the top element from the stack
        // Give the right node of the current node to the current node for the next loop to find all its left node s
        if (!stack.isEmpty()) {
            current = stack.pop();
            current = current.getRightChild();
        }
    }
    System.out.println(result);
}

The above code is commented
General idea:
From the root, put all the left nodes into the stack (from the top of the stack to the end of the stack: 6, 4, 2, 1), because of the preorder traversal, it will be output at this time, and the current is empty and jumps out of the interior the while loop
When the if judgment is reached, the top 6 of the stack is popped from the stack and assigned to current, and the right child node 7 of 6 is assigned to current (nothing). At this time, 4 is the top of the stack.
Loop a while, pop 4 from the stack, and give the right child of 4 to current. At this time, 2 becomes the top of the stack.
Do the while loop again, and process all the nodes below 7 aside. Found no, continue to pop up 2... (and so on)

4-2-6. In-order traversal

Implemented recursively

@Override
public void inOrderTraverse() {
    this.inOrderTraverse(root);
}

private void inOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // l Handling
    inOrderTraverse(node.getLeftChild());
    // d output
    System.out.print(node.getData() + " ");
    // r processing
    inOrderTraverse(node.getRightChild());
}

Recursive:
1. Given the termination condition, node is empty and terminated
2. Pass the root node to the method, because of the in-order traversal, so put d between l and r first

stack implementation

@Override
public void inOrderByStack() {
    Deque<TreeNode> stack = new LinkedList<>();
    if (root == null) {
        return;
    }

    // Mind method: move with the current node, and how to access the stack according to the order of DLR, LDR, LRD
    // Point to the current mobile node of the tree
    TreeNode current = root;
    List<Object> result = new ArrayList<>();
    while (current != null || !stack.isEmpty()) {
        // Put all the left child nodes of the current node on the stack, and loop consistently until the left child node is null
        while (current != null) {
            stack.push(current);
            // To move the position of the current node to the current node (ie the left node)
            current = current.getLeftChild();
        }

        // If the stack is not empty, pop the top element from the stack and output
        // Give the right node of the current node to the current node for the next loop to find all its left node s
        if (!stack.isEmpty()) {
            current = stack.pop();
            result.add(current.getData());
            current = current.getRightChild();
        }
    }
    System.out.println(result);
}

The above code is commented
General idea:
From the root, push all left nodes into the stack (from the top of the stack to the end of the stack: 6, 4, 2, 1), when current is empty, jump out of the internal while loop
When the if judgment is reached, the top 6 of the stack is popped from the stack and assigned to current. Because it is an in-order traversal, it is output when the stack is popped, and then the right child node of 6 is given to current (null). At this time, 4 becomes the stack. top.
Do another while loop, pop the top 4 from the stack, and assign the right child node 7 of 4 to current, this is 2 becomes the top of the stack
Do the while loop again, and process all the nodes below 7 aside. Found no, continue to pop up 2... (and so on)

4-2-7. Post-order traversal

Implemented recursively

@Override
public void postOrderTraverse() {
    this.postOrderTraverse(root);
}

private void postOrderTraverse(TreeNode node) {
    if (node == null) {
        return;
    }
    // l Handling
    postOrderTraverse(node.getLeftChild());
    // r processing
    postOrderTraverse(node.getRightChild());
    // d output
    System.out.print(node.getData() + " ");
}

Recursive:
1. Given the termination condition, node is empty and terminated
2. Pass the root node to the method, because of the in-order traversal, so put d first after l and r

stack implementation 1

@Override
public void postOrderByStack() {

    // method one:
    Deque<TreeNode> stack = new LinkedList<>();
    if (root == null) {
        return;
    }
    List<Object> result = new ArrayList<>();
    // Point to the current mobile node of the tree
    TreeNode current = null;
    // Points to one of the children of the currently moved node (ie, the previous top of the stack)
    TreeNode tmpChildNode = null;

    stack.push(root);
    while (!stack.isEmpty()) {
        current = stack.peek();
        if ((current.getLeftChild() == null && current.getRightChild() == null) || current.getLeftChild() == tmpChildNode || current
                .getRightChild() == tmpChildNode) {
            result.add(current.getData());
            stack.pop();
            tmpChildNode = current;
        } else {
            // Add the right child node first, because the stack is LIFO
            if (current.getRightChild() != null) {
                stack.push(current.getRightChild());
            }
            // Add the left child node, because the stack is LIFO
            if (current.getLeftChild() != null) {
                stack.push(current.getLeftChild());
            }
        }
    }
    System.out.println(result);
}

Thought:
Push the node into the stack, and then use the top element of the stack to determine whether there is a child node.
Print the result when popping the stack. Note that the conditions for printing two

  • No child nodes, i.e. leaf, need to be printed
  • The node that is popped from the stack has child nodes, but the node that was popped from the previous stack also needs to be printed

Stack implementation 2

 @Override
public void postOrderByStack() {
    // Method 2
    Deque<TreeNode> stack = new LinkedList<>();
    if (root == null) {
        return;
    }

    // Mind method: move with the current node, and how to access the stack according to the order of DLR, LDR, LRD
    // Point to the current mobile node of the tree
    TreeNode current = root;
    List<Object> result = new ArrayList<>();
    while (current != null || !stack.isEmpty()) {
        // Put all the right child nodes of the current node on the stack, and loop consistently until the right child node is null
        while (current != null) {
            stack.push(current);
            // To move the position of the current node to the current node (ie the right node)
            result.add(current.getData());
            current = current.getRightChild();
        }

        // If the stack is not empty, pop the top element from the stack and output
        // Give the left node of the current node to the current node for the next loop to find all its right node s
        if (!stack.isEmpty()) {
            current = stack.pop();
            current = current.getLeftChild();
        }
    }
    // Invert the result
    Collections.reverse(result);
    System.out.println(result);
}

Ideas:
This should be understood in conjunction with the traversal of the pre-order stack (the pre-order stack method, with the left child node as the first, has been pressed while looping), and the post-order stack method, the right is the first to push the stack
But in the end, the meal needs to be reversed

4-2-8. Horizontal Traversal

@Override
public void levelOrderByQueue() {
    Deque<TreeNode> queue = new LinkedList<>();
    if (root == null) {
        return;
    }
    List<Object> result = new ArrayList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int len = queue.size();
        // Traverse to pop elements in the stack
        for (int i = 0; i < len; i++) {
            TreeNode node = queue.poll();
            result.add(node.getData());
            TreeNode leftChild = node.getLeftChild();
            TreeNode rightChild = node.getRightChild();
            if (leftChild != null) {
                queue.offer(leftChild);
            }
            if (rightChild != null) {
                queue.offer(rightChild);
            }
        }
    }
    System.out.println(result);
}

Horizontal traversal should be handled with the help of the characteristics of the queue, put each layer into the queue tail, and take it out from the beginning (each time a layer of data is added, the data in the queue needs to be taken out)

4-3. Overall code

package com.iworkh.da.lesson03;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * custom binary tree
 *
 * @author: iworkh-Muyu Yunlou
 * @date: 2020-07-02
 */
public class MyListBinaryTree implements ITree {

    private TreeNode root;

    public MyListBinaryTree(TreeNode root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public int size() {
        return size(this.root);
    }

    private int size(TreeNode node) {
        // Returns 0 if null, plus one if not null
        if (node == null) {
            return 0;
        }
        int leftSize = size(node.getLeftChild());
        int rightSize = size(node.getRightChild());
        // The left and right child nodes will drop once, so as long as the node is null, just add one by yourself
        return leftSize + rightSize + 1;
    }

    @Override
    public int getHeight() {
        // Find the depth, that is, who is the longest child node from the root
        return getHeight(root);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // left child node
        int leftNum = getHeight(node.getLeftChild());

        // right child node
        int rightNum = getHeight(node.getLeftChild());

        // return big +1
        return leftNum > rightNum ? leftNum + 1 : rightNum + 1;
    }

    @Override
    public TreeNode findKey(Object value) {
        return this.findKey(value, root);
    }

    private TreeNode findKey(Object value, TreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getData().equals(value)) {
            return node;
        }

        TreeNode leftNode = findKey(value, node.getLeftChild());

        TreeNode rightNode = findKey(value, node.getRightChild());

        if (leftNode != null) {
            return leftNode;
        }

        if (rightNode != null) {
            return rightNode;
        }

        return null;
    }

    @Override
    public void preOrderTraverse() {
        this.preOrderTraverse(root);
    }

    private void preOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // d output
        System.out.print(node.getData() + " ");
        // l Handling
        preOrderTraverse(node.getLeftChild());
        // r processing
        preOrderTraverse(node.getRightChild());
    }

    @Override
    public void inOrderTraverse() {
        this.inOrderTraverse(root);
    }

    private void inOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // l Handling
        inOrderTraverse(node.getLeftChild());
        // d output
        System.out.print(node.getData() + " ");
        // r processing
        inOrderTraverse(node.getRightChild());
    }

    @Override
    public void postOrderTraverse() {
        this.postOrderTraverse(root);
    }

    private void postOrderTraverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // l Handling
        postOrderTraverse(node.getLeftChild());
        // r processing
        postOrderTraverse(node.getRightChild());
        // d output
        System.out.print(node.getData() + " ");
    }

    @Override
    public void preOrderByStack() {
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return;
        }

        // Mind method: move with the current node, and how to access the stack according to the order of DLR, LDR, LRD
        // Point to the current mobile node of the tree
        TreeNode current = root;
        List<Object> result = new ArrayList<>();
        while (current != null || !stack.isEmpty()) {
            // Put all the left child nodes of the current node on the stack, and loop consistently until the left child node is null
            while (current != null) {
                // output
                result.add(current.getData());
                stack.push(current);
                // To move the position of the current node to the current node (ie the left node)
                current = current.getLeftChild();
            }

            // If the stack is not empty, pop the top element from the stack
            // Give the right node of the current node to the current node for the next loop to find all its left node s
            if (!stack.isEmpty()) {
                current = stack.pop();
                current = current.getRightChild();
            }
        }
        System.out.println(result);
    }

    @Override
    public void inOrderByStack() {
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return;
        }

        // Mind method: move with the current node, and how to access the stack according to the order of DLR, LDR, LRD
        // Point to the current mobile node of the tree
        TreeNode current = root;
        List<Object> result = new ArrayList<>();
        while (current != null || !stack.isEmpty()) {
            // Put all the left child nodes of the current node on the stack, and loop consistently until the left child node is null
            while (current != null) {
                stack.push(current);
                // To move the position of the current node to the current node (ie the left node)
                current = current.getLeftChild();
            }

            // If the stack is not empty, pop the top element from the stack and output
            // Give the right node of the current node to the current node for the next loop to find all its left node s
            if (!stack.isEmpty()) {
                current = stack.pop();
                result.add(current.getData());
                current = current.getRightChild();
            }
        }
        System.out.println(result);
    }

    @Override
    public void postOrderByStack() {

        // method one:
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return;
        }
        List<Object> result = new ArrayList<>();
        // Point to the current mobile node of the tree
        TreeNode current = null;
        // Points to one of the children of the currently moved node (ie, the previous top of the stack)
        TreeNode tmpChildNode = null;

        stack.push(root);
        while (!stack.isEmpty()) {
            current = stack.peek();
            if ((current.getLeftChild() == null && current.getRightChild() == null) || current.getLeftChild() == tmpChildNode || current
                    .getRightChild() == tmpChildNode) {
                result.add(current.getData());
                stack.pop();
                tmpChildNode = current;
            } else {
                // Add the right child node first, because the stack is LIFO
                if (current.getRightChild() != null) {
                    stack.push(current.getRightChild());
                }
                // Add the left child node, because the stack is LIFO
                if (current.getLeftChild() != null) {
                    stack.push(current.getLeftChild());
                }
            }
        }
        System.out.println(result);


        // Method 2
        // Deque<TreeNode> stack = new LinkedList<>();
        // if (root == null) {
        //     return;
        // }
        //
        // // Mental method: move with the current node, how to access to the stack according to the order of DLR, LDR, LRD
        // // Point to the current moving node of the tree
        // TreeNode current = root;
        // List<Object> result = new ArrayList<>();
        // while (current != null || !stack.isEmpty()) {
        //     // Put all the right child nodes of the current node on the stack, and loop consistently until the right child node is null
        //     while (current != null) {
        //         stack.push(current);
        //         // To move the position of the current node to the current node (ie right node)
        //         result.add(current.getData());
        //         current = current.getRightChild();
        //     }
        //
        //     // If the stack is not empty, pop the top element from the stack, output
        //     // Give the left node of the current node to the current node for the next loop to find all its right node s
        //     if (!stack.isEmpty()) {
        //         current = stack.pop();
        //         current = current.getLeftChild();
        //     }
        // }
        // // invert the result
        // Collections.reverse(result);
        // System.out.println(result);
    }

    @Override
    public void levelOrderByQueue() {
        Deque<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return;
        }
        List<Object> result = new ArrayList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            // Traverse to pop elements in the stack
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                result.add(node.getData());
                TreeNode leftChild = node.getLeftChild();
                TreeNode rightChild = node.getRightChild();
                if (leftChild != null) {
                    queue.offer(leftChild);
                }
                if (rightChild != null) {
                    queue.offer(rightChild);
                }
            }
        }
        System.out.println(result);
    }
}

4-4. Test code

The created tree is the tree we have been analyzing in the previous article

public class MyListBinaryTreeTest {
    public static void main(String[] args) {
        TreeNode root = genBTree();

        MyListBinaryTree myListBinaryTree = new MyListBinaryTree(root);

        System.out.println("Is it empty:" + myListBinaryTree.isEmpty());
        System.out.println("Height of tree:" + myListBinaryTree.getHeight());
        System.out.println("Number of tree nodes:" + myListBinaryTree.size());

        System.out.println("Find 3: " + myListBinaryTree.findKey(3));
        System.out.println("Find 20:" + myListBinaryTree.findKey(20));

        System.out.println("Preorder recursive traversal:");
        myListBinaryTree.preOrderTraverse();
        System.out.println("");
        System.out.println("Inorder recursive traversal:");
        myListBinaryTree.inOrderTraverse();
        System.out.println("");
        System.out.println("Post-order recursive traversal:");
        myListBinaryTree.postOrderTraverse();
        System.out.println("");

        System.out.println("Preorder stack traversal:");
        myListBinaryTree.preOrderByStack();
        System.out.println("");
        System.out.println("Inorder stack traversal:");
        myListBinaryTree.inOrderByStack();
        System.out.println("");
        System.out.println("Postorder stack traversal:");
        myListBinaryTree.postOrderByStack();
        System.out.println("");
        System.out.println("Horizontal queue traversal:");
        myListBinaryTree.levelOrderByQueue();
    }

    private static TreeNode genBTree() {
        TreeNode treeNode6 = new TreeNode(6, null, null);
        TreeNode treeNode7 = new TreeNode(7, null, null);
        TreeNode treeNode4 = new TreeNode(4, treeNode6, treeNode7);

        TreeNode treeNode9 = new TreeNode(9, null, null);
        TreeNode treeNode8 = new TreeNode(8, null, treeNode9);
        TreeNode treeNode5 = new TreeNode(5, treeNode8, null);

        TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);

        TreeNode treeNode10 = new TreeNode(10, null, null);
        TreeNode treeNode12 = new TreeNode(12, null, null);
        TreeNode treeNode11 = new TreeNode(11, null, treeNode12);

        TreeNode treeNode3 = new TreeNode(3, treeNode10, treeNode11);

        return new TreeNode(1, treeNode2, treeNode3);
    }
}

result

Is it empty: false
 tree height: 4
 Number of tree nodes: 12
 Find 3: TreeNode{data=3, leftChild=10, rightChild=11}
Find 20: null
 Preorder recursive traversal:
1 2 4 6 7 5 8 9 3 10 11 12 
Inorder recursive traversal:
6 4 7 2 8 9 5 1 10 3 11 12 
Post-order recursive traversal:
6 7 4 9 8 5 2 10 12 11 3 1 
Preorder stack traversal:
[1, 2, 4, 6, 7, 5, 8, 9, 3, 10, 11, 12]

Inorder stack traversal:
[6, 4, 7, 2, 8, 9, 5, 1, 10, 3, 11, 12]

Postorder stack traversal:
[6, 7, 4, 9, 8, 5, 2, 10, 12, 11, 3, 1]

Horizontal queue traversal:
[1, 2, 3, 4, 5, 10, 11, 6, 7, 8, 12, 9]

5. Links

6. Recommended

To be able to read the article to the end, first of all, thank you for your affirmation of this article. Your affirmation is the greatest encouragement to bloggers.

If you find this article helpful, then click ๐Ÿ‘
If you have any questions, leave yours ๐Ÿ’ฌ
Afraid of losing me, then throw me โญ
The computer is not convenient to read, then I will send it to you ๐Ÿ“ฒ

Tags: Algorithm data structure

Posted by KDesigns on Mon, 30 May 2022 02:54:01 +0530