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)
- val->left subtree->right subtree-preorder traversal
- Left subtree->val->right subtree-in-order traversal
- 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(); } }