Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
Iterative method to traverse binary search tree, with recursion we can achieve the traversal of binary search tree, in fact, recursion is equivalent to the stack, next introduced how to use iterative way to achieve the traversal of binary search tree.
The first iteration is traversal
Add the value of the root node to the array because the stack is first in and then out. Search in the preceding order (left and right) is to push the right child node first and then push the left child node, so that the order of exit is left and right node.
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)
ifcur_node.right ! =None:
stack.append(cur_node.right)
ifcur_node.left ! =None:
stack.append(cur_node.left)
Copy the code
The second iteration is traversal
This is done by pushing the left node all the way from the root node, adding the values to the return array, and then removing the right child node from the stack
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)
ifcur_node.right ! =None:
stack.append(cur_node.right)
ifcur_node.left ! =None:
stack.append(cur_node.left)
Copy the code
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)
ifcur_node.right ! =None:
stack.append(cur_node.right)
ifcur_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())
Copy the code