如何使用中序/前序/后序遍历二叉搜索树而不使用递归的Python方法？

Question

在 Python 3 中，

class BinaryTree:
"""
=== Private Attributes ===
@type _root: object | None
@type _left: BinaryTree | None
@type _right: BinaryTree | None

"""
def __init__(self, root, left, right):

    if root is None:
        # store an empty BinaryTree
        self._root = None
        self._left = None
        self._right = None
    else:
        self._root = root
        self._left = left
        self._right = right

def is_empty(self):
    return self._root is None

我知道如何使用递归遍历这个二叉树，但我想知道如何不使用递归来进行遍历。

- logic penguin

---

http://meta.softwareengineering.stackexchange.com/questions/6166/open-letter-to-students-with-homework-problems - Corvus Crypto

Answer 1

您可以使用堆栈方法在不使用递归的情况下进行树遍历。 我将给出中序遍历的示例。

def inOrder(root):

    # Set current to root of binary tree
    current = root 
    s = [] # initialze stack
    done = 0

    while(not done):

        # Reach the left most Node of the current Node
        if current is not None:

            # Place pointer to a tree node on the stack 
            # before traversing the node's left subtree
            s.append(current)

            current = current.left 


        # BackTrack from the empty subtree and visit the Node
        # at the top of the stack; however, if the stack is 
        # empty you are done
        else:
            if(len(s) >0 ):
                current = s.pop()
                print current.data,

                # We have visited the node and its left 
                # subtree. Now, it's right subtree's turn
                current = current.right 

            else:
                done = 1

如需更多解释，您可以参考https://www.youtube.com/watch?v=xLQKdq0Ffjg&t=755s教程。

- js_248

---

不错！那么前序遍历和后序遍历是否遵循相似的模式呢？ - logic penguin

他们也会使用栈，但是模式不同。您可以观看给定的YouTube视频以了解更多关于先序遍历和后序遍历的内容。 - js_248