[Data Structure] understanding of three-order non-recursion traversal binary tree

xiaoxiao2021-03-06  165

A few days ago, I listened to a lecture that recursively to non-recursion transformations, and some did not dare to enjoy exclusive. Therefore, I will discuss it with everyone.

All three sequences travers the binary tree to use the stack, and the role of the stack is to save the node of the tree to return to the stack call.

Supreme: According to the order in the order, visit the root to traverse its left sub-tree. If the degree of the left sub-tree is not zero, you must first traverse your left sub-tree to go through the rooted right tree, and under the tree is priority than the tree. From this characteristic, it can be used in the backward first characteristics of the stack, and the root node is incorporated one by one, and the left sub-tree is accessed again to obtain the address of the root, and then traverse the right tree.

This further discussed, recursive transfer non-recursion will experience the variable of the current function and put it in the stack, call the called function, and the control is handed over to the called function, while the variable and return value of the modified function will undergo when returned. That is, the outlet, the control is transferred to the call function, and the return value returns to the call function. It can be seen that when the recursive function is converted into a non-recursive function, the stack is a variable that calls the function, while when the returns are returned, the variable of the called function will be called out of the stack and return the return value in the stack to the main tone. function.

转载请注明原文地址:https://www.9cbs.com/read-128262.html

New Post(0)