preface

We’ve already seenThe construction and basic method of binary sorting treeThe implementation of the. But sort traversal is also an important part. So I’m going toAfter the order before. And sequence traversal comb through.
All you need to know about tree traversal is a reserveQueue, recursion, and stack. Here the author has carried on the detailed introduction, can pay attention to the authorData structures and algorithms. Keep sharing,Learn together.

Sequence traversal

There are left and right nodes
The left and right should be considered equally
Queue to implement

For queues, it’s now in, first out. Push from the root node to the queue, then the first out of the queue is the left and right of the second layer (assuming any).The second floorAdd each execution timeAdded to the queue, then all the added nodes are inBehind the second floor.
Similarly, let’s say we startPop traverses the NTH levelOf the nodes, each node willPush the left and right nodes in. But the queue is first in, first out. It goes to the end of the line (The next layer). All the way to the NTH levelThe last pop comes out, layer n+1 is still in the queue. So this is going to be oneThe sequenceThe effect.

The implementation code is also easy to understand:

public void cengxu(node t) {// Sequence traversal
	Queue<node> q1 = new ArrayDeque<node>();
	if (t == null)
		return;
	if(t ! =null) {
		q1.add(t);
	}
	while(! q1.isEmpty()) { node t1 = q1.poll();if(t1.left ! =null)
			q1.add(t1.left);
		if(t1.right ! =null)
			q1.add(t1.right);
		System.out.print(t1.value + "");
	}
	System.out.println();
}
Copy the code

Sequential traversal (recursion)

This is actually an idea similar to DFS. I’m going to do it recursively. Recursion algorithms are described in great detail earlier. The three-order traversal we use is the same recursion. And everybody knows that recursion is a process that goes back and forth. Three-order traversal only uses the recursion in the process of different fragments to intercept the output, and to reach the results of the previous (middle and post order traversal).

First order recursive

The rule of preorder is root -> left -> right. We operate on the node before calling the recursion. For preorder, you access (output) the node first. Recursively left, recursively right, will take precedence over recursively left. Until there is no left node. Before it stops. The order of access is roughly:

public void qianxu(node t)// Preorder recursion preorder traversal: root --> left subtree --> right subtree
{
	if(t ! =null) {
		System.out.print(t.value + "");// The current nodeqianxu(t.left); qianxu(t.right); }}Copy the code

Sequence of recursion

With our preorder experience, we are well placed to take advantage of order traversal in a recursive implementation. The rule of order traversal is: left subtree -> root -> right subtree. So the order in which we visit the nodes needs to change.

We get to the recursion of 0Back and forthThe process ofFor exactly two child nodes(child node has no node). Only need toAccess the left node once, access the root, access the right node. Can.
And if you have nodes on both sides.Each node must meet the rules of order traversal in. We access the left node from the root first. theLeft node hereThe left node becomesA subtree.Also must satisfy in order traversal requirements. So you first access the left node of the left node (if any). So if you think about it this way, the rules are clear. But it’s too complicated.So let’s use recursion. Because its subproblem is the same as the root problem,It's just a smaller range. So we use the idea of recursion.
So the logic of recursion is: consider the special case (special direct access) do not recursion otherwise recursive access to the left subtree (let the left subtree perform the same function, special stop recursion output, not special continue to find until the most left node). — > Output the node — > recursively access the right subtree.

The code is:

public void zhongxu(node t)// In order traversal in order traversal: left subtree --> root node --> right subtree
{
	if(t ! =null) {
		zhongxu(t.left);
		System.out.print(t.value + "");// Access the current node after the left node is accessedzhongxu(t.right); }}Copy the code

After the sequence of recursion

Similarly, with the previous analysis, the following is left subtree -> right subtree -> root

public void houxu(node t)// Back order traversal back order traversal: left subtree --> right subtree --> root node
{
	if(t ! =null) {
		houxu(t.left);
		houxu(t.right);
		System.out.print(t.value + ""); // Access play left and right to access the current node}}Copy the code

Nonrecursive preorder

Method 1 (Technique)

Nonrecursive preorder. We use the properties of the stack instead of recursion becauseRecursion is sometimes efficientIs not satisfactory. With the stack, we get to the stack in cash-first out order. thenOrder how to add? Recursion is left recursion, right recursion. But the stack is the other way around, because ifLeft stack, right stackThe following consequences can occur:

So, we’re going to use the idea of recursion,You need to push the right node first, then the left nodeAnd then next time I take the node and I take the left node and I take this nodeThen the right node pushes the stack, the left node pushes the stack. And then all the way to the end of the loop it takes precedence over the left node. To achieve the same effect as the recursive order.

After each pop, add the right and left nodes directly output (access) to complete the pre-order non-recursive traversal.

public void qianxu3(node t)// Non-recursive preorder stack first left and then right t is usually root
{
	Stack<node> q1 = new Stack<node>();
	if (t == null)
		return;
	if(t ! =null) {
		q1.push(t);
	}
	while(! q1.empty()) { node t1 = q1.pop();if(t1.right ! =null) {
			q1.push(t1.right);
		}
		if(t1.left ! =null) {
			q1.push(t1.left);
		}
		System.out.print(t1.value + ""); }}Copy the code

Method 2 (Traditional)

Method 2 is similar to the non-recursive order traversal method, except that you need to change the output time and input the access node at the time of the stack. Specific reference in the sequence traversal analysis.

public void qianxu2(node t) {
		Stack<node> q1 = new Stack();	
		while(! q1.isEmpty()||t! =null)
		{
			if(t! =null) {
				System.out.print(t.value+"");
				q1.push(t);				
				t=t.left;
			}
			else{ t=q1.pop(); t=t.right; }}}Copy the code

Non recursive order

There is a difference between order and preorder in non-recursion. Our order of order until middle order is: left node, root node, right node. So we can’t release the node before we go through the root node, because we need it later. So we need to store it on the stack first. Its rules are roughly:

The stackStore all points of the left node in turnUntil the leftmost part is at the top of the stack.
startThrow the top of the stack and access. (for example, the first throws a 2).If there is a right node. It will beThe right node is added to the stack.Then the right node is traversed all the way to the bottom left. (Here 5 and 7 do not have left nodes, so do not add)butIf an15. The right node is added.23Add the left node of 23 to the top of the stack. And so onUntil the stack is empty.

Feasibility analysis: the order is left – middle – right order. Visit left. When the current point is thrown to indicate that the left side has been accessed (or is itself left), the right side of the current point needs to be accessed first. Then the right node will repeat the same operation as the root node (because the right node has to satisfy the order of first left and then right). This is actually simulating a recursive process, you need to think about it.

Implementation code 1:

public void zhongxu2(node t) {
	Stack<node> q1 = new Stack();	
	while(! q1.isEmpty()||t! =null)
	{
		if(t! =null) {
			q1.push(t);
			t=t.left;
		}
		else {
			t=q1.pop();
			System.out.print(t.value+""); t=t.right; }}}Copy the code

Implementation code 2 :(first written by the individual)

public void zhongxu3(node t)// Store all left nodes, throw a point, access the right node of that point, and store all child left nodes for the right node
{
	Stack<node> q1 = new Stack();
	if (t == null)
		return;
	if(t ! =null) {
		q1.push(t);
	}
	node t1 = q1.peek();// Can't throw, save the leftmost first
	while(t1.left ! =null) {
		t1 = t1.left;
		q1.push(t1);
	}
	while(! q1.isEmpty()) { node t2 = q1.pop(); System.out.print(t2.value +"");
		if(t2.right ! =null) {
			t2 = t2.right;
			q1.push(t2);
			while(t2.left ! =null) { t2 = t2.left; q1.push(t2); }}}}Copy the code

Non-recursive order ※

There are two ways to do non-recursive post-order traversal. One way is to use the same method as the previous in-order, pre-order and second methods to get in and out of the stack, but with the extra number of tags, a node accesses the output the second time. The first time this access is pushed, and the second time is when the subtree is ready to exit the stack (not exiting the stack first).

Method 1(Traditional method)

When the preceding sequence and the middle sequence are pushed to the left of the stack first, the two kinds of order are in turn

Before the order:In the stack— >The left into the stack— > Stack out — > Stack out — >Right into the stack— > Right child in — > right out of the stackYou can preorder when you push the stack
Middle order: middle push — > left push — >Left out of the stack— >In the stack— > Right push — > Right child in and out — >Right out of the stack In accordance with the stack order can be completed in order

And in a sequential traversal: It has this rule:

Push, first access
Coming out of the stack. On the second visit,
If you have a right child, you don’t get out of the stack and you push the right child onto the stack for the first time, if you don’t have a right child. Access is popped off the stack.
The loop repeats until the stack is empty

public void houxu2(node t) {
	Stack<node> q1 = new Stack();	
	Map<Integer,Integer >map=new HashMap<>();
	while(! q1.isEmpty()||t! =null)
	{
		if(t! =null) {
			q1.push(t);
			map.put(t.value, 1); //t.value indicates the number of occurrences of this value node
			t=t.left;
		}
		else {
			t=q1.peek();
			if(map.get(t.value)==2) {// Second access, throw
				q1.pop();
				System.out.print(t.value+"");
				t=null;// Need to go up
			}
			else {
				map.put(t.value, 2); t=t.right; }}}}Copy the code

Method 2(dual stack) :

Another approach is to use dual-stack processing. We used to push right and left with a stack in preorder method one. Continue to allow a preorder traversal effect. But this approach is hard to follow.

The same analysis, if weFirst the left, then the right, then the order we get will be the exact opposite of the previous order (The order:Middle, right, left.The reverse is just left, right, and center of the follow-up) symmetry looks like the antecedent. Use another stack to sequenceReverse order!

If we do this process, and we store it on another stack, and we store its first push on one stack,It acts as a reversal.

The implementation code is:

public void houxu3(node t)// If q1 is installed on the right side of the stack, put the right side in front and the left side on top.
{
	Stack<node> q1 = new Stack();
	Stack<node> q2 = new Stack();
	if (t == null)
		return;
	if(t ! =null) {
		q1.push(t);
	}
	while(! q1.isEmpty()) { node t1 = q1.pop(); q2.push(t1);if(t1.left ! =null) {
			q1.push(t1.left);
		}
		if(t1.right ! =null) { q1.push(t1.right); }}while(! q2.isEmpty()) { node t1 = q2.pop(); System.out.print(t1.value +""); }}Copy the code

conclusion

Test results:

In addition, the complete code also please pay attention to the public number (bigsai). The author carefully updatedData structures and algorithms. If you are interested, you can follow a wave of learning together. replyThe data structureorThe crawlerThere are carefully prepared study materials presented.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structures and algorithms – binary tree sequence, pre-order traversal, in-order traversal, post-order traversal (recursive, non-recursive)

preface

Sequence traversal

Sequential traversal (recursion)

First order recursive

Sequence of recursion

After the sequence of recursion

Nonrecursive preorder

Method 1 (Technique)

Method 2 (Traditional)

Non recursive order

Non-recursive order ※

Method 1(Traditional method)

Method 2(dual stack) :

conclusion

Data structures and algorithms – binary tree sequence, pre-order traversal, in-order traversal, post-order traversal (recursive, non-recursive)

preface

Sequence traversal

Sequential traversal (recursion)

First order recursive

Sequence of recursion

After the sequence of recursion

Nonrecursive preorder

Method 1 (Technique)

Method 2 (Traditional)

Non recursive order

Non-recursive order ※

Method 1(Traditional method)

Method 2(dual stack) :

conclusion

Related Posts

19. Learn about Go Modules and how to use them

Five principles of Object-oriented programming SOLID- Single responsibility, open closed principle

WordPress Database Series: Common errors and best practices for using databases in WordPress