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

This article introduces the relevant knowledge of "C language and the introduction of non-recursive traversal of binary trees in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Preface

The recursive traversal of the binary tree is very simple, the difference between the three recursive traversal methods, but the location of the printf is different, so I won't talk about it here. Post the preorder code here:

/ / Node struct Node {int val; struct Node* left, * right;}; / / preorder traversal of void pre (Node* root) {if (root = = null) return; printf ("% d", root- > val); pre (root- > left); pre (root- > right);}

Among the three non-recursive traversal ways of preorder, middle order and post-order, the middle order is the simplest, the second is the pre-order, and the second is the post-order, which is just a personal feeling. Maybe everyone feels different.

1. Non-recursive mid-order traversal

Traversal order in the middle order: left subtree-> header node-> right subtree.

As shown in the figure-from the "lie data structure"

So the first thing we need to consider is to push the nodes on the left-hand side (left subtree) into the stack, and when we reach the bottom (NULL), we output the elements at the top of the stack.

Then add the node on the right-hand side (right subtree) of the current node to the stack instead.

# define MAXSIZE 20 / / the maximum number of nodes in the whole tree, which is used to open up an array when the stack uses typedef struct Node Node;void in (Node* root) {Node* stack [MAXSIZE] = {0}; int size = 0 / / used to point to the arr array, and also to indicate that there are several elements in the array while (size! = 0 | | root! = NULL) {if (root! = NULL) {stack [size++] = root; root = root- > left / / continue to go to the left subtree} else {/ / at this time root is NULL, indicating that you have come to the bottom of the left subtree and output the top elements of the stack. Root can go to the right subtree to printf ("% c", stack [--size]-> val); root = stack [size]-> right;}} 2. Non-recursive preorder traversal

Preorder traversal order: head node-> left subtree-> right subtree

I remember when I was learning the algorithm at Station B, I listened to what teacher Zuo Chengyun said that some recursive behaviors can be realized on their own stacks.

Indeed, the three non-recursive traversal methods actually need to implement the functions of the stack themselves. In the next preorder traversal, the idea of width-first traversal is used, as shown in the figure:

The picture is from "lie data structure".

First add all the data of the first layer, and then judge all the data of the second layer while using the first layer of data in the stack, and the same is true of the third layer.

# define MAXSIZE 20 / / the maximum number of nodes in the whole tree, used to open up an array when the stack uses typedef struct Node Node;void pre (Node* root) {if (root = = NULL) return; Node* stack [MAXSIZE] = {0}; / / Simulation stack int size = 0; / / represents how many elements there are in the stack arr [size++] = root; while (size! = 0) {Node* node = stack [--size] Printf ("% c", node- > val); / / press the right child first, then the left child. In this way, the left child pops up first and then the right child / / head left and right if (node- > right! = NULL) stack [size++] = node- > right; if (node- > left! = NULL) stack [size++] = node- > left;}} 3. Non-recursive post-order traversal

After explaining the non-recursive preorder traversal, in fact, we can complete the post-order traversal by changing it on the basis of preorder traversal. When we iterate through the preorder, in the while loop, when we add the left and right child nodes, the right child is added first, and then the left child is added to the stack. Only in this way, the order in which we pop up is first left and then right.

Now we just need to change the order of adding left and right children, we first press the stack is the left child, and then press the right child. This pops up in the order of right and then left. Then add the knot at this time, that is, the knot-> the right child-> the left child. At this time, we read from the back to the front, which is the left child-> the right child-> the head node. This becomes a post-order traversal.

The picture is from "lie data structure".

# define MAXSIZE 20 / / the maximum number of nodes in the whole tree, used to open up an array when the stack uses typedef struct Node Node;void postorder (Node* root) {if (root = = NULL) return; Node* stack1 [MAXSIZE] = {0}; / / main stack Node* stack2 [MAXSIZE] = {0}; / / auxiliary stack int size1 = 0; / main stack: number of elements representing the array int size2 = 0 / / Auxiliary stack: the number of elements representing the array stack1 [size1++] = root; while (size1! = 0) {Node* node = stack1 [--size1]; stack2 [size2++] = node; / / temporarily stored in the auxiliary stack / / press the left child first, and then press the right child if (node- > left! = NULL) stack1 [size1++] = node- > left If (node- > right! = NULL) stack1 [size1++] = node- > right;} / / output the data of the auxiliary stack upside down while (size2--! = 0) printf ("% c", stack2 [size2]-> val);} "C language and Java in the non-recursive traversal of binary trees" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.