An traversal instance of a binary tree of python data structures
- 2020-04-02 13:39:24
- OfStack
Traversal scheme
According to the recursive definition of binary tree, a non-empty binary tree is composed of three basic parts: root node, left and right subtree. Therefore, at any given node, three operations can be performed in a certain order:
1). Access node itself (N)
2). Traverse the left subtree (L) of the node
3). Traversing the right subtree (R) of the node
Have the order:
NLR, LNR, LRN
Traversal naming
Name it according to the operation location of access node:
NLR: PreorderTraversal (PreorderTraversal)
-- the operation to access a node occurs before traversing its left and right subtrees.
LNR: middle order traversal (InorderTraversal)
The operation to access a node takes place in traversing its left and right subtrees.
LRN: PostorderTraversal (PostorderTraversal)
-- the operation to access a node occurs after traversing its left and right subtrees.
Note: since the Node to be accessed must be the root of a subtree, N(Node), L(Left subtlee), and R(Right subtree) can be interpreted as the root, the Left subtree of the root, and the Right subtree of the root. NLR, LNR and LRN are also known as first root traversal, middle root traversal and later root traversal, respectively.
Through the calendar calculation method
1). Definition of recursive algorithm of first order traversal:
If the binary tree is not empty, perform the following operations in turn:
A. Access the root node
B. Traverse the left subtree
C. Traverse the right subtree
2). Definition of recursive algorithm for middle order traversal:
If the binary tree is not empty, perform the following operations in turn:
A. Traverse the left subtree
B. Access the root node
C. Traverse the right subtree
3). Recursive algorithm definition of post-order traversal:
If the binary tree is not empty, perform the following operations in turn:
A. Traverse the left subtree
B. Traverse the right subtree
C. Access the root node
I. recursive traversal of binary trees:
# -*- coding: utf - 8 - *-
class TreeNode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class BTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def preorder(self, treenode):
' Before the order, pre-order . NLR ) traversal '
if treenode is 0:
return
print treenode.data
self.preorder(treenode.left)
self.preorder(treenode.right)
def inorder(self, treenode):
' In order ( in-order . LNR'
if treenode is 0:
return
self.inorder(treenode.left)
print treenode.data
self.inorder(treenode.right)
def postorder(self, treenode):
' After order, post-order . LRN ) traversal '
if treenode is 0:
return
self.postorder(treenode.left)
self.postorder(treenode.right)
print treenode.data
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')
bt = BTree(root)
print u'''
# Generated binary tree
# ------------------------
# root
# 7 8
# 6
# 2 5
# 1 3 4
#
# -------------------------
'''
print ' Before the order, pre-order . NLR ) traversal : n'
bt.preorder(bt.root)
print ' In order ( in-order . LNR) traverse : n'
bt.inorder(bt.root)
print ' After order, post-order . LRN ) traversal : n'
bt.postorder(bt.root)
Ii. Non-recursive traversal of binary trees
Now let's do it in a non-recursive way. Stack and queue are mainly used to maintain some data nodes:
# -*- coding: utf - 8 - *-
class TreeNode(object):
def __init__(self, left=0, right=0, data=0):
self.left = left
self.right = right
self.data = data
class BTree(object):
def __init__(self, root=0):
self.root = root
def is_empty(self):
if self.root is 0:
return True
else:
return False
def preorder(self, treenode):
' Before the order, pre-order . NLR ) traversal '
stack = []
while treenode or stack:
if treenode is not 0:
print treenode.data
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
treenode = treenode.right
def inorder(self, treenode):
' In order ( in-order . LNR) traverse '
stack = []
while treenode or stack:
if treenode:
stack.append(treenode)
treenode = treenode.left
else:
treenode = stack.pop()
print treenode.data
treenode = treenode.right
# def postorder(self, treenode):
# stack = []
# pre = 0
# while treenode or stack:
# if treenode:
# stack.append(treenode)
# treenode = treenode.left
# elif stack[-1].right != pre:
# treenode = stack[-1].right
# pre = 0
# else:
# pre = stack.pop()
# print pre.data
def postorder(self, treenode):
' After order, post-order . LRN ) traversal '
stack = []
queue = []
queue.append(treenode)
while queue:
treenode = queue.pop()
if treenode.left:
queue.append(treenode.left)
if treenode.right:
queue.append(treenode.right)
stack.append(treenode)
while stack:
print stack.pop().data
def levelorder(self, treenode):
from collections import deque
if not treenode:
return
q = deque([treenode])
while q:
treenode = q.popleft()
print treenode.data
if treenode.left:
q.append(treenode.left)
if treenode.right:
q.append(treenode.right)
node1 = TreeNode(data=1)
node2 = TreeNode(node1, 0, 2)
node3 = TreeNode(data=3)
node4 = TreeNode(data=4)
node5 = TreeNode(node3, node4, 5)
node6 = TreeNode(node2, node5, 6)
node7 = TreeNode(node6, 0, 7)
node8 = TreeNode(data=8)
root = TreeNode(node7, node8, 'root')
bt = BTree(root)
print u'''
# Generated binary tree
# ------------------------
# root
# 7 8
# 6
# 2 5
# 1 3 4
#
# -------------------------
'''
print ' Before the order, pre-order . NLR ) traversal : n'
bt.preorder(bt.root)
print ' In order ( in-order . LNR) traverse : n'
bt.inorder(bt.root)
print ' After order, post-order . LRN ) traversal : n'
bt.postorder(bt.root)
print ' Sequence ( level-order . LRN ) traversal : n'
bt.levelorder(bt.root)