Pre-middle and post-order traversal (recursive and non-recursive) and level-order traversal of binary trees

Pre-middle and post-order traversal (recursive and non-recursive) and level-order traversal of binary trees

Article directory

  • Pre-middle and post-order traversal (recursive and non-recursive) and level-order traversal of binary trees
  • Preface
  • 1. Recursive implementation
    • 1. Preorder traversal
    • 2. In-order traversal
    • 3. Post-order traversal
  • 2. Non-recursive implementation
    • 1. Preorder traversal
    • 2. In-order traversal
    • 3. Postorder traversal
  • 3. Layer sequential traversal

Foreword

Regarding the structure of a binary tree: Each node of a binary tree generally has three elements, a pointer to the left child, a pointer to the right child, and the data stored in the node.

template <class T>
struct TreeNode
{<!-- -->
TreeNode(const T & x)
:_left(nullptr)
, _right(nullptr)
, _val(x)
{<!-- -->}


TreeNode* _left;
TreeNode* _right;
T_val;
};

The so-called traversal of a binary tree generally starts with the left and then the right, that is, first walks the left subtree and then the right subtree. However, the timing of accessing the data stored in the nodes in the tree is different, resulting in three different traversal methods (herein referred to as access). The data is val)

  1. val->left subtree->right subtree-preorder traversal
  2. Left subtree->val->right subtree-in-order traversal
  3. Left subtree->right subtree->val-post-order traversal

1. Recursive implementation

1. Preorder traversal

 void PreOrder(TreeNode* root)
{<!-- -->
//Return if root is empty
if (root == nullptr)
{<!-- -->
return;
}

//Access _val value
cout << root->_val << " ";

//Recursively walk the left subtree
PreOrder(root->_left);

//Recursively walk the right subtree
PreOrder(root->_right);
}

2. In-order traversal

 void InOrder(TreeNode* root)
{<!-- -->
//Return if root is empty
if (root == nullptr)
{<!-- -->
return;
}

//Recursively walk the left subtree
PreOrder(root->_left);

//Access _val value
cout << root->_val << " ";

//Recursively walk the right subtree
PreOrder(root->_right);
}

3. Post-order traversal

 void PostOrder(TreeNode* root)
{<!-- -->
//Return if root is empty
if (root == nullptr)
{<!-- -->
return;
}

//Recursively walk the left subtree
PreOrder(root->_left);

//Recursively walk the right subtree
PreOrder(root->_right);

//Access _val value
cout << root->_val << " ";
}

2. Non-recursive implementation

Compared with recursive implementation, non-recursive implementation is slightly more complicated. The basic principle is to use the first-in-last-out nature of the stack to save nodes to simulate the recursive process in order to achieve the purpose of traversing the binary tree.

Note: The following code defaults to _val being of int type, and the traversed accessed data is first stored in the vector without being printed directly

1. Preorder traversal

 void PreOrder(TreeNode* root)
{<!-- -->
TreeNode* cur = root;
vector<int> v;
stack<TreeNode*> st;

while (cur || !st.empty())
{<!-- -->
while (cur)
{<!-- -->
//Access the node data
v.push_back(cur->_val);
//Push the node onto the stack and save it
st.push(cur);
//Continue accessing the left subtree
cur = cur->_left;
}
//Going here, the left subtree of the node in the stack has been visited
//If the stack is not empty, take the top element of the stack and access its right subtree
//In fact, the stack here cannot be empty. This should be a redundant judgment. You can think about why.
if (!st.empty())
{<!-- -->
//Get the top element of the stack
cur = st.top();
//Delete the top element of the stack
st.pop();
//Convert into a sub-problem and treat cur->_right as a new tree. Repeat the above operations.
cur = cur->_right;
}
}
//Print the data traversed in preorder in sequence
for (auto e : v)
{<!-- -->
cout << e << " ";
}
cout << endl;
}

2. In-order traversal

 void InOrder(TreeNode* root)
{<!-- -->
TreeNode* cur = root;
vector<int> v;
stack<TreeNode*> st;

while (cur || !st.empty())
{<!-- -->
while (cur)
{<!-- -->
//Push the node onto the stack and save it
st.push(cur);
//Continue accessing the left subtree
cur = cur->_left;
}
//Going here, the left subtree of the node in the stack has been visited
//If the stack is not empty, take the top element of the stack, access the node data, and access its right subtree
//In fact, the stack here cannot be empty. This should be a redundant judgment. You can think about why.
if (!st.empty())
{<!-- -->
//Get the top element of the stack
cur = st.top();
//Delete the top element of the stack
st.pop();
//Access the node data
v.push_back(cur->_val);
//Convert into a sub-problem and treat cur->_right as a new tree. Repeat the above operations.
cur = cur->_right;
}
}
//Print the data traversed in order in sequence
for (auto e : v)
{<!-- -->
cout << e << " ";
}
cout << endl;
}

3. Postorder traversal

Post-order traversal is slightly more complicated than pre-order and in-order. Because of the different access orders, it is necessary to additionally determine whether the current node is a node returned from the right subtree.
In layman’s terms, only after the left subtree and right subtree of the node have been completed, the _val stored in the node can be accessed, that is, it needs to be judged whether to return to the node for the second time. , because the node will visit the node once when it returns from the left subtree. This is the first time. According to the post-order traversal rules, it is necessary to first go through the right subtree before accessing the node’s _val, so only when returning to the node for the second time Node can only be accessed

void PostOrder(TreeNode* root)
{<!-- -->
TreeNode* cur = root;
TreeNode* front = nullptr;
vector<int> v;
stack<TreeNode*> st;

while (cur || !st.empty())
{<!-- -->
while (cur)
{<!-- -->
//Push the node onto the stack and save it
st.push(cur);
//Continue accessing the left subtree
cur = cur->_left;
}
//Going here, the left subtree of the node in the stack has been visited
//Get the top element of the stack, access the node data, and access its right subtree

//Get the top element of the stack
cur = st.top();

//There are only two situations where the node data can be accessed and the node can be deleted from the stack.
//1. If the right side of the node is empty, access the data directly
//2. The last visited node is the right subtree of the node, which means that we have returned to the node twice and came back through the right subtree.
if (cur->_right == nullptr || front == cur->_right)
{<!-- -->
//Delete the top element of the stack
st.pop();
//Access the node data
v.push_back(cur->_val);
//Save this node as front
front = cur;
//Empty cur, and the outer loop determines whether the stack is empty. If it is not empty, the loop operation
cur = nullptr;
}
//When the right side of the node is not empty and is only visited once
else
{<!-- -->
//Convert into a sub-problem and treat cur->_right as a new tree. Repeat the above operations.
cur = cur->_right;
}
}

//Print the data traversed in sequence in sequence
for (auto e : v)
{<!-- -->
cout << e << " ";
}
cout << endl;
}

3. Layer-order traversal

As the name suggests, layer-order traversal is to access a binary tree layer by layer. The specific idea is also very simple. It accesses nodes layer by layer and uses a queue to store the nodes of the next layer while accessing data.
Note: The default _val of the following code is of int type, and the traversed accessed data is first stored in a two-dimensional array without being printed directly. Each layer of the two-dimensional array represents the corresponding value in the tree. One layer of stored data

 void levelOrder(TreeNode* root)
{<!-- -->
queue<TreeNode*> q;

//Define a two-dimensional array to store the data of the entire tree
vector<vector<int>> vv;

//Define an array to store single-level data to facilitate the insertion of two-digit arrays
vector<int> v;

//Record the number of data in each layer
size_t levelnum;

if(root)
{<!-- -->
q.push(root);
levelnum = 1;
}
//Continue if the queue is not empty
while (!q.empty())
{<!-- -->
//Use levelnum to complete layer by layer
while (levelnum--)
{<!-- -->
TreeNode* top = q.front();
q.pop();
v.push_back(top->_val);

if (top->_left)
{<!-- -->
q.push(top->_left);
}

if (top->_right)
{<!-- -->
q.push(top->_right);
}
}
//Insert this layer of data into a two-dimensional array
//Clear the data in v
//Update levelnum, the new levelnum value is the number of nodes in the queue
vv.push_back(v);
v.clear();
levelnum = q.size();
}
}