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.


Related articles: