Binary tree is the simplest tree structure, which is usually composed of root node, left subtree and right subtree. The common binary tree consists of balanced binary tree, binary search tree and so on. Next, the author will focus on the principle and code implementation of pre order, middle order, post order and hierarchical traversal of ordinary binary tree.

Pre order, middle order and post order traversal of binary tree

The pre order, middle order and post order traversal of a binary tree refers to the order in which the root node is accessed. As the name suggests, preorder traversal means first accessing the root node and traversing the binary tree in the order of root node, left subtree and right subtree. It should be emphasized that when traversing the subtree (whether left subtree or right subtree), the traversal order is also the root node of the subtree, the left subtree of the subtree and the right subtree of the subtree. Therefore, the traversal of binary tree uses the idea of divide and conquer, which is often realized by depth first search algorithm. Next, the author will use C + + to realize the preorder traversal of binary tree by using recursive and iterative methods:

Preorder traversal (recursion):

Using the recursive method, it is important to determine the condition of recursive termination. In the traversal of binary tree, the recursive condition is that the pointer of the binary tree is a null pointer.

class Solution {
public:
    void preorder_traversal(TreeNode *root){
        if(root==null) return;
        cout<<root->val<<endl;        // Specific statements can be used instead of other personal purposes
        preorder_traversal(root->left);
        preorder_traversal(root->right);
    }

};

Preorder traversal (iteration):

The difficulty of iterative method lies in the setting of iterative termination conditions and the realization of traversal order. Generally, the traversal iterative method of binary tree is realized by stack.

class Solution {
public:
    void preorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        if(!root) return;
        stk.push(root);
        while(!stk.empty()){
            root=stk.top();
            cout<<root->val<<endl;
            stk.pop();
            //Due to the first in then out nature of the stack, the left node needs to be put into the stack later so that it can be accessed first
            if(root->right) stk.push(root->right);
            if(root->left) stk.push(root->left);
        }
    }

};

Medium order traversal (recursion)

The middle order traversal order is the left subtree, root node and right subtree. The following is a recursive implementation:

class Solution {
public:
    void Inorder_traversal(TreeNode *root){
        if(root==null) return;
        Inorder_traversal(root->left);
        cout<<root->val<<endl;        // It can be replaced by other statements, depending on your personal purpose
        Inorder_traversal(root->right);
    }

};

Medium order traversal (iteration)

The middle order traversal first traverses the left subtree, so it needs to iterate to the highest child node of the left subtree of the binary tree, and then go back to traverse the binary tree. The following is the iterative implementation:

class Solution {
public:
    void Inorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        if(!root) return;  //If it is empty, the tree will be returned directly
        while(true){
            if(root){
                stk.push(root); //Root node stack
                root=root->left; //Iterate to the highest left child node of the binary tree
            }
            else if(!stk.empty()){
                root=stk.top()  //This node is the highest left child node of the binary tree. Access it first
                cout<<root->val<<endl;
                stk.pop();
                root=root->right; //After accessing the highest left sub node, you need to access the right sub tree of the node (if any)
            }
            else break;
        }
     
    }

};

Postorder traversal (recursion)

The order of post order traversal is left subtree, right subtree and root node. The recursive implementation is:

class Solution {
public:
    void Postorder_traversal(TreeNode *root){
        if(root==null) return;
        Postorder_traversal(root->left);
        Postorder_traversal(root->right);
        cout<<root->val<<endl;        // It can be replaced by other statements, depending on your personal purpose
    }

};

Postorder traversal (iteration)

The order of post order traversal is the left and right roots. The post order traversal can be obtained by using the results of pre order traversal of the left and right roots. Change the pre order traversal to the right and left traversal of the root, and then reverse the results to get the post order traversal results. The code is as follows:

class Solution {
public:
    void postorder_traversal(TreeNode *root){
        stack<TreeNode*> stk;
        vecor<int> res; //Store the results of right and left traversal of the root
        if(!root) return;  //If it is empty, the tree will be returned directly
        stk.push(root);
        while(!stk.empty()){
            root=stk.top();
            res.push_back(root->val);
            stk.pop();
            if(root->left) stk.push(root->left);
            if(root->right) stk.push(root->right);
        }
        reverse(res.begin(),res.end());//Reverse the results to get the results of post order traversal
        for(int num:res) cout<<num<<endl;
    
     
    }

};

Hierarchical traversal of binary tree

Previously, the traversal methods of pre order, middle order and post order of binary tree are introduced. Next, the hierarchical traversal of binary tree will be introduced. The so-called hierarchical traversal is to traverse the binary tree layer by layer. This kind of traversal uses breadth first search, which usually needs to be realized with the help of queue. The code is as follows:

class Solution {
public:
    void Hierarchical_Traversal(TreeNode *root){
        queue<TreeNode*> que;
        if(!root) return;
        que.push(root);
        while(!que.empty()){
            root=que.front();
            cout<<root->val<<endl;
            que.pop();
            //Print from left to right. Because of the first in, first out nature of the queue, let the left node enter the queue first
            if(root->left) que.push(root->left);
            if(root->right) que.push(root->right);
        }    
    }
};

Finally, thank you for your patience. The author will constantly update the knowledge of algorithms and machine learning. Interested students can pay attention and learn together. In addition, if you have questions, you can comment in the comment area or chat with me in private. I'm glad to help you.