Python binary tree definition and traversal method example analysis
- 2020-09-28 08:58:06
- OfStack
An example of Python2 tree definition and traversal method is given. To share for your reference, the details are as follows:
2. Basic Overview of The tree:
A two-tree is a number of finite elements. If it is null, it is null. If it is null, it is null; or if it has a node called a root node, it is divided into left and right child nodes of the two-tree on both sides of the root node.
1. There is no node with a degree greater than 2 in each node of the tree
The i layer of 2. 2 tree has at most 2^{i-1} nodes
3. A 2-tree with a depth of k has at most 2^ k-1 nodes
4. In a cross-tree, the number of nodes with degree 0 N0 is 1 larger than the number of nodes with degree 2 N2, that is, N2 + 1 = N0
Python code:
#coding:utf-8
'BiTree'
class Node(object):
'Node Defination'
def __init__(self,item):
self.item = item
self.left = None
self.right = None
class Tree(object):
'Bitree Defination'
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
if self.root is None:
self.root = node
else:
q = [self.root]
while True:
pop_node = q.pop(0)
if pop_node.left is None:
pop_node.left = node
return
elif pop_node.right is None:
pop_node.right = node
return
else:
q.append(pop_node.left)
q.append(pop_node.right)
def traverse(self):# Level traversal
if self.root is None:
return None
q = [self.root]
res = [self.root.item]
while q != []:
pop_node = q.pop(0)
if pop_node.left is not None:
q.append(pop_node.left)
res.append(pop_node.left.item)
if pop_node.right is not None:
q.append(pop_node.right)
res.append(pop_node.right.item)
return res
def preorder(self,root): # The first sequence traversal
if root is None:
return []
result = [root.item]
left_item = self.preorder(root.left)
right_item = self.preorder(root.right)
return result + left_item + right_item
def inorder(self,root): # In the sequence traversal
if root is None:
return []
result = [root.item]
left_item = self.inorder(root.left)
right_item = self.inorder(root.right)
return left_item + result + right_item
def postorder(self,root): # After the sequence traversal
if root is None:
return []
result = [root.item]
left_item = self.postorder(root.left)
right_item = self.postorder(root.right)
return left_item + right_item + result
if __name__=='__main__':
t = Tree()
for i in range(10):
t.add(i)
print " Sequence traversal :",t.traverse()
print " The first sequence traversal :",t.preorder(t.root)
print " In the sequence traversal :",t.inorder(t.root)
print " After the sequence traversal :",t.postorder(t.root)
Output results:
[
Sequence traversal: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
First order traversal: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
Middle order traversal: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
Sequential traversal: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]
Here for
if __name__=='__main__':
" Make a script both importable and executable "
This means that the script module you write can be imported into another module and can be executed by the module itself.
Here is an example to explain:
#test.py
def func():
print "we are in %s"%__name__
if __name__ == '__main__':
func()
Output results:
[we are in __main__
]
Indicates that the contents of the if statement have been executed and called
func()
The func function is now called in another module
#testtest
from test import func
func()
Output results:
[we are in moudle
]That is, the contents of the if condition are not executed.
Conclusion:
If you directly execute a *.py file, the file
if __name__ == '__main__'
Is True, which is equivalent to the code of this module; If it is imported by import from another module (ES70en.py), ___, 73EN__ will be the name of the module (test) rather than ___, and will be added to the mode code
if __name__ == '__main__'
If you want to check the problem of this module code, you can directly carry out debugging execution
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 is helpful for Python programming.