Shulou(Shulou.com)06/01 Report--

Editor to share with you how C++ non-recursive implementation of the binary tree before, middle and back order traversal, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article. Let's take a look at it!

Preorder traversal of binary tree

When traversing the binary tree without recursion, we can use a stack simulation recursion mechanism. The preorder traversal order of the binary tree is: root → left subtree → right subtree, we can first put the left node of the binary tree into the stack, and access it at the same time, which is equivalent to completing the access of the root and the left subtree. When the left node has finished entering the stack, the nodes are taken out from the top of the stack in turn, and the right subtree can be accessed in the same way.

The specific steps are as follows:

Put the left node into the stack, and access the left node at the same time.

Remove the top node top of the stack.

Prepare to visit the right subtree of the top node.

Struct TreeNode {int val; TreeNode * left; TreeNode * right; TreeNode (): val (0), left (nullptr), right (nullptr) {} TreeNode (int x): val (x), left (nullptr), right (nullptr) {} TreeNode (int x, TreeNode * left, TreeNode * right): val (x), left (left), right (right) {}} Class Solution {public: / / preorder traversal vector preorderTraversal (TreeNode* root) {stack st; / / auxiliary stack vector ret; / / used to store the results of preorder traversal TreeNode* cur = root While (cur | |! st.empty ()) {/ / 1. Put the left node into the stack and visit the left node while (cur) {st.push (cur) at the same time. Ret.push_back (cur- > val); cur = cur- > left;} / / 2, take out the top node of the stack TreeNode* top = st.top (); st.pop () / / 3. Prepare to visit its right subtree cur = top- > right;} return ret; / / return preorder traversal result}}; Intermediate order traversal of binary tree

The traversal order of the binary tree in the middle order is: the left subtree → root → right subtree, we can first put the left node of the binary tree into the stack, and then take out the node from the top of the stack, and then access it while taking out the node. At this time, it is equivalent to visiting the left subtree and then the root, and then accessing the right subtree in the same way.

The specific steps are as follows:

Put the left node into the stack.

Take out the top node top and access it.

Prepare to visit the right subtree of the top node.

Struct TreeNode {int val; TreeNode * left; TreeNode * right; TreeNode (): val (0), left (nullptr), right (nullptr) {} TreeNode (int x): val (x), left (nullptr), right (nullptr) {} TreeNode (int x, TreeNode * left, TreeNode * right): val (x), left (left), right (right) {}} Class Solution {public: / / Central order traversal vector inorderTraversal (TreeNode* root) {stack st; / / Auxiliary stack vector ret; / / used to store the results of medium order traversal TreeNode* cur = root While (cur | |! st.empty ()) {/ / 1, while (cur) {st.push (cur); cur = cur- > left } / / 2. Remove the top node of the stack and visit TreeNode* top = st.top (); st.pop (); ret.push_back (top- > val) / / 3. Prepare to visit its right subtree cur = top- > right;} return ret; / / return the result of traversal in the middle order}}; the post-order traversal of the binary tree

The traversal order of the binary tree is: the left subtree → right subtree → root. We can first put the left node of the binary tree into the stack. When the left node has finished entering the stack, we will observe the top node of the stack. If the right subtree of the top node of the stack is empty, or the right subtree of the top node of the stack has been visited, then the top node of the stack can be unstacked and accessed. If the right subtree of the top node of the stack has not been accessed The right subtree of the node at the top of the stack is accessed in the same way until the right subtree is accessed, and the access order follows the order required by the post-traversal of the binary tree.

The specific steps are as follows:

Put the left node into the stack.

Observe the top node top of the stack.

If the right subtree of the top node is empty, or if the right subtree of the top node has been visited, visit the top node. After visiting the top node, pop it out of the stack and update the last visited node as top.

If the right subtree of the top node has not been accessed, prepare to visit its right subtree.

Struct TreeNode {int val; TreeNode * left; TreeNode * right; TreeNode (): val (0), left (nullptr), right (nullptr) {} TreeNode (int x): val (x), left (nullptr), right (nullptr) {} TreeNode (int x, TreeNode * left, TreeNode * right): val (x), left (left), right (right) {}} Class Solution {public: / / Post-order traversal vector postorderTraversal (TreeNode* root) {stack st; / / Auxiliary stack vector ret; / / used to store the results of post-order traversal TreeNode* cur = root; TreeNode* prev = nullptr / / record the last visited node while (cur | |! st.empty ()) {/ / 1. Put the left node into the stack while (cur) {st.push (cur) Cur = cur- > left;} / / 2, remove the top node of the stack TreeNode* top = st.top () / / 3. If the right subtree of the removed node is empty, or the right subtree has already been visited Then visit the node if (top- > right = = nullptr | | top- > right = = prev) {/ / access the top node and pop it out of the stack st.pop () Ret.push_back (top- > val); / / update the node of the last visit is top prev = top } else / / 4. If the right subtree of the removed node has not been accessed, prepare to visit its right subtree {cur = top- > right;}} return ret / / return post-order traversal result}}

Note: please combine the given code when looking at the demonstration of the moving picture. The dynamic picture is made in strict accordance with the logic of the code.

These are all the contents of this article entitled "how C++ non-recursively traverses the binary tree in front, middle and back order". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.