Trees/Computer Science/Depth-First Search: How does in-order traversal work?
I don't fully understand the in-order traversal. At least not in the code.
You start at 5 and recurse to 1, always to the left. Then I print 1. After that, the 3 would be printed, meaning you climb back up.
I don't understand how the climb works. After the 1, you'd want to jump to the right, which isn't possible because the 1 has no children. The same thing happens after I've spent the 1, 3, and the 4: How do I jump back up to the 5?
Well, I understand the principle in pseudocode: Always left, root, right. But not in the real code.
I have this code snippet from ChatGPT:
def in_order_traversal(root): if root is not None: # Zuerst den linken Teilbaum durchlaufen in_order_traversal(root.left) # Dann den Wurzelknoten besuchen print(root.value) # Schließlich den rechten Teilbaum durchlaufen in_order_traversal(root.right)
(1 votes)
Loading...
Since your sample tree is small, you can also go through the algorithm well step-by-step.
I’ll show the drain for the left subtree. We start with the root node (n(5)):
The in_order_traversal– Function is recursive. That means she keeps calling herself. Whenever the program flow changes to a new functional context, I have set the indentation stage further to the right in the above course.
Since a subnode is transferred during each call, the tree structure can be folded down. The examination of whether the transferred node exists is the termination condition of the recursion. In this case, the function does not call itself again, but is terminated. Thus, the program flow can jump again to the caller (or here climb up).
I understand, but somehow not quite when you say this is jumped back to the caller, why is it jumped to 5 after the 4 and not to 3? Or does that result with the indentation you made in your pseudcode? I guess that’s been nested with the intention. Looks like multiple grinding in one loop
I have already explained what the indentations stand for in my above text.
In the best case, you will create a sketch/step-by-step schedule yourself. Basically, you only need to consider a rule:
When a function is called, the program flow jumps in its body, its instructions work (until the end of the functional body or one return– instruction has been reached) and then jumps back to the caller (or behind the call location). From there it goes as usual.
When crossing to pre-order logic, it doesn't work great than differently in-order. The only difference is that at each call the pre-order function the node value is output first before it goes further into the subnodes.
Algorithm (Python):
Take this tree as an example:
working steps, starting with the call of pre_order_traversal(n(5)) :
As already mentioned above: An indentation step to the right stands for a context change into the called function. When the function has been completely processed, it goes back to the caller (an indentation to the left). In the end, you're back at the first caller.
With the help of the stack the principle, understood. Just don’t get up with the pre order. At Pre Order, I will first issue my root and then jump recursively into my left or right tree. The recursion calls are nevertheless stored in the stack, i.e. my root itself is not deposited in the steak. Then how do I jump back to the root?
You need to place the previous nodes in a data structure. A stack usually in depth search, a cue in width search. How exactly depends on how exactly you carry.
i.e. at the recursion, the program where it was already?
The progammstack is used for recursion, yes.
During recursion, jump marks are placed on the stack by the recursion call.
In what order this happens you decide by the order of your calls.
For in-order, this would look like:
For mail order according to:
That is to say, the predecessor node will be noticed as soon as I have reached the end, so I am completely down, do you automatically jump back to the predecessor node? How exactly is it then at the post order there I jump so to speak from bottom left to right
Look at how Recursion works, best visualized. Then you should understand how the “high climbing” works.