Binary tree structure definition and traversal method of Python data structure and algorithm
- 2020-06-15 09:45:05
- OfStack
An example of Python data structure and algorithm is presented in this paper. To share for your reference, specific as follows:
First order traversal, in order traversal, after order traversal, the difference lies in the position of the three core statements
Hierarchical traversal adopts the traversal operation of the queue to access the root for the first time. The left child of the root is accessed, and then the child of the root is accessed, and then the node of the same layer is accessed from the left to the right in the next layer
# The first sequence traversal
# Visit node, traverse left subtree, if left subtree is empty, traverse right subtree,
# If the right subtree is empty, go up to 1 Three nodes that can go to the right, and continue the process
preorder(t):
if t:
print t.value
preorder t.L
preorder t.R
# In the sequence traversal
# Starting at the root, 1 Go straight to the bottom left, until no node can walk, stop, access the node
# Then it goes to the lower right to the node, and then to the lower left: if the node has no right children, it goes up to the parent
inorder(t):
inorder(t.L)
print t.value
inorder(t.R)
# After the sequence traversal
inorder(t):
inorder(t.L)
inorder(t.R)
print t.value
# 2 Cross tree node type
class BTNode:
def __init__(self,value,lft=None,rgt=None):
self.value = value
self.lft = lft # Node left branch BTNode
self.rgt = rgt # Node right branch BTNode
For convenience, define 1 some printing operations
class BinTree():
def __init__(self):
self.root = None # create 1 empty 2 tree
def isEmpty(self): # judge 2 Whether the tree is empty
if self.root is None: return True
else: return False
def makeBT(self,bt,L=None,R=None): # Created from the current node 2 tree
bt.lft = L
bt.rgt = R
def returnBTdict(self): # return 2 The dictionary pattern of the cross tree
if self.isEmpty():
return None
def rec(bt=None,R=True):
if R==True:
bt = self.root
return {'root':{'value':bt.value,"L":rec(bt.lft,False),
"R":rec(bt.rgt,False)} }
else:
if bt==None:
return None
else:
return {"value":bt.value,
"L":rec(bt.lft,False) if bt.lft != None else None,
"R":rec(bt.rgt,False) if bt.rgt != None else None}
return None
return rec()
def __repr__(self): # will 2 The cross-tree structure is printed as a dictionary structure
return str(self.returnBTdict())
Below are the various traversal methods added to the class of the tree
def printT_VLR(self,bt=None,rec_count = 0): # The output 2 Cross tree structure (sequential traversal first)
# rec_count Used to calculate the depth of recursion To output the last line break
"""
# The first sequence traversal
# Visit node, traverse left subtree, if left subtree is empty, traverse right subtree,
# If the right subtree is empty, go up to 1 Three nodes that can go to the right, and continue the process
preorder(t):
if t:
print t.value
preorder t.L
preorder t.R
"""
if bt==None:
bt = self.root
print bt.value,
btL, btR = bt.lft, bt.rgt
if btL != None:
print btL.value,; rec_count += 1; self.printT_VLR(btL,rec_count); rec_count -= 1
if btR != None:
print btR.value,; rec_count += 1; self.printT_VLR(btR,rec_count); rec_count -= 1
if rec_count == 0:
print "\n"
def printT_LVR(self,bt=None):
"""
# In the sequence traversal
# Starting at the root, 1 Go straight to the bottom left, until no node can walk, stop, access the node
# Then it goes to the lower right to the node, and then to the lower left: if the node has no right children, it goes up to the parent
inorder(t):
inorder(t.L)
print t.value
inorder(t.R)
"""
if bt==None:
bt = self.root
btL, btR = bt.lft, bt.rgt
if btL != None:
self.printT_LVR(btL)
print bt.value,
if btR != None:
self.printT_LVR(btR)
def printT_LRV(self,bt=None):
"""
# After the sequence traversal
inorder(t):
inorder(t.L)
inorder(t.R)
print t.value
"""
if bt==None:
bt = self.root
btL, btR = bt.lft, bt.rgt
if btL != None:
self.printT_LRV(btL)
if btR != None:
self.printT_LRV(btR)
print bt.value,
def printT_levelorder(self):
"""
Sequence traversal Queue traversal operation is adopted
The first 1 The second visit to the root, the left child in the visit to the root, the next visit to the root has the child, and then the next 1 layer
From left to right 11 Access nodes of the same layer
"""
btdict = self.returnBTdict()
q = []
q.append(btdict['root'])
while q:
tn = q.pop(0) # Pop out of the queue 1 A node ( Is also 1 A dictionary )
print tn["value"],
if tn["L"]!=None:
q.append(tn["L"])
if tn["R"]!=None:
q.append(tn["R"])
Test printing effect
def test():
bt = BinTree()
# btns = [BTNode(v) for v in "+*E*D/CAB"] # The sequence of input
# bt.root = btns[0]
# bt.makeBT(btns[0], L=btns[1], R=btns[2])
# bt.makeBT(btns[1], L=btns[3], R=btns[4])
# bt.makeBT(btns[3], L=btns[5], R=btns[6])
# bt.makeBT(btns[5], L=btns[7], R=btns[8])
btns = [BTNode(v) for v in [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]
bt.root = btns[0]
bt.makeBT(btns[0], L=btns[1], R=btns[2])
bt.makeBT(btns[1], L=btns[3], R=btns[4])
bt.makeBT(btns[2], L=btns[5], R=btns[6])
bt.makeBT(btns[3], L=btns[7], R=btns[8])
bt.makeBT(btns[4], L=btns[9], R=btns[10])
bt.makeBT(btns[5], L=btns[11], R=btns[12])
bt.makeBT(btns[6], L=btns[13], R=btns[14])
Output:
{'root': {'R': {'R': {'R': {'R': None, 'L': None, 'value': 15}, 'L': {'R': None, 'L': None, 'value': 14}, 'value': 7}, 'L': {'R': {'R': None, 'L': None, 'value': 13}, 'L': {'R': None, 'L': None, 'value': 12}, 'value': 6}, 'value': 3}, 'L': {'R': {'R': {'R': None, 'L': None, 'value': 11}, 'L': {'R': None, 'L': None, 'value': 10}, 'value': 5}, 'L': {'R': {'R': None, 'L': None, 'value': 9}, 'L': {'R': None, 'L': None, 'value': 8}, 'value': 4}, 'value': 2}, 'value': 1}}For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Encryption and Decryption Algorithm and Skills Summary, Python Coding skills Summary, Python Function Use Skills Summary, Python String Manipulation Skills Summary and Python Introduction and Advanced Classic Tutorial.
I hope this article has been helpful in Python programming.