数据结构—二叉树迭代法遍历
迭代法来遍历二叉搜索树，用递归大家都可以实现对二叉搜索树的遍历，其实递归等同于栈，接下来介绍如何用迭代方式来实现对二叉搜索树的遍历。
第一种迭代方式遍历
将根节点压入栈后出栈，将根节点值添加到数组，因为栈是先进后出，搜索在前序(中左右）是先将右侧子节点压入栈再将左侧子结点压入栈，这样出栈顺序就是左结点和右结点。
def _preorder_iterator(self,cur_node,res): stack = [] stack.append(cur_node) while len(stack) >0: cur_node = stack.pop() res.append(cur_node.val) if cur_node.right != None: stack.append(cur_node.right) if cur_node.left != None: stack.append(cur_node.left) 复制代码
第二种迭代方式遍历
这种方式先是从根节点一路将其左结点压入栈，并且将这些值添加到返回数组，随后出栈时并将其右子节点
def _preorder_iterator(self,cur_node,res): stack = [] stack.append(cur_node) while len(stack) >0: cur_node = stack.pop() res.append(cur_node.val) if cur_node.right != None: stack.append(cur_node.right) if cur_node.left != None: stack.append(cur_node.left) 复制代码
class Node: def __init__(self,val): self.val = val self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def insert(self,val): if self.root == None: self.root = Node(val) else: self._insert(val,self.root) def _insert(self,val,cur_node): if val > cur_node.val: if cur_node.right == None: cur_node.right = Node(val) else: self._insert(val,cur_node.right) elif val < cur_node.val: if cur_node.left == None: cur_node.left = Node(val) else: self._insert(val,cur_node.left) def traversal(self): res = [] self._preorder_iterator(self.root,res) return res def _preorder_iterator(self,cur_node,res): stack = [] stack.append(cur_node) while len(stack) >0: cur_node = stack.pop() res.append(cur_node.val) if cur_node.right != None: stack.append(cur_node.right) if cur_node.left != None: stack.append(cur_node.left) def _preorder(self,cur_node,res): if cur_node == None: return res.append(cur_node.val) self._preorder(cur_node.left,res) self._preorder(cur_node.right,res) if __name__ == "__main__": bst = BinarySearchTree() bst.insert(5) bst.insert(3) bst.insert(4) bst.insert(1) bst.insert(2) print(bst.traversal())
作者：ti138729
链接：https://juejin.cn/post/7020365706185310238