Python implements input binary tree first order and middle order traversal and then output post order traversal operation example

An example of Python is presented in this paper, which implements the first order and middle order traversal of input 2 tree, and then outputs the second order traversal operation. To share for your reference, the details are as follows:

1 function:

Input: first order and middle order traversal of a 2 - tree
Output: Subsequent traversal

Thought:

In the first sequence traversal, the first element is the root
Find the roots in the middle order traversal, the left subtree and the right subtree

Python code:

# -*- coding:utf-8 -*-
def fromFMtoL( mid ):
  global las # Global post-ordered traversal 
  global fir # The first sequence traversal 
  root = fir[0]  # Take out the current root 
  fir = fir[1:]  # After taking out the root   So let's go through the order first and get the roots out   The following 1 The element is the root 
  root_po = mid.find( root ) # The position of the roots in the middle order traversal 
  left = mid[0:root_po]  # The left subtree 
  right = mid[root_po+1:len(mid)] # The right subtree 
  '''
   Post-order traversal:   On the left   right   The root  
   First the left subtree   Then right subtree   The last to 
  '''
  # When you have a left subtree 
  if len(left) > 0:
    fromFMtoL( left )
  # When you have the right subtree 
  if len(right) > 0:
    fromFMtoL( right )
  # The root is written into the result 
  las += root
if __name__ == "__main__" :
  # fir = input(" Please enter first order traversal: ")   # The result of the preceding traversal 
  # mid = input(" Please enter middle order traversal: ")   # The result of an ordered traversal 
  fir = "DBACEGF"
  mid = "ABCDEFG"
  # fir = "ABC"
  # mid = "BAC"
  las = ""
  fromFMtoL( mid )
  print(las)

Operation results:

ACBFGED

For more information about Python, please refer to: Python Data Structure and Algorithm Tutorial, Python Coding Skills Summary, Python Function Skills Summary, Python String Manipulation Skills Summary and Python Introduction and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.