python使用findSuccessor方法，写一个非递归的二叉搜索树中序遍历方法，并测试

下面是使用非递归方式实现的二叉搜索树中序遍历方法：

class Node:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            curr = self.root
            while True:
                if val < curr.val:
                    if curr.left is None:
                        curr.left = Node(val)
                        break
                    else:
                        curr = curr.left
                else:
                    if curr.right is None:
                        curr.right = Node(val)
                        break
                    else:
                        curr = curr.right

    def findSuccessor(self, node):
        if node.right:
            curr = node.right
            while curr.left:
                curr = curr.left
            return curr
        else:
            curr = node.parent
            while curr and curr.right == node:
                node = curr
                curr = curr.parent
            return curr

    def inorderTraversal(self):
        stack = []
        curr = self.root
        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            print(curr.val)
            curr = curr.right

下面我们来测试一下：

bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
bst.insert(6)
bst.insert(8)

bst.inorderTraversal()

输出结果为：

2
3
4
5
6
7
8

可以看出，该方法成功地对二叉搜索树进行了中序遍历。