python 은 재 귀적 인 방식 으로 이 진 트 리 를 만 듭 니 다.

트 리 와 그림 의 데이터 구조 가 재 미 있 습 니 다.

# coding = utf-8

 

 

class BinaryTree:

  def __init__(self, root_obj):

    self.key = root_obj

    self.left_child = None

    self.right_child = None

 

  def insert_left(self, new_node):

    node = BinaryTree(new_node)

    if self.left_child is None:

      self.left_child = node

    else:

      node.left_child = self.left_child

      self.left_child = node

 

  def insert_right(self, new_node):

    node = BinaryTree(new_node)

    if self.right_child is None:

      self.right_child = node

    else:

      node.right_child = self.right_child

      self.right_child = node

 

  def get_right_child(self):

    return self.right_child

 

  def get_left_child(self):

    return self.left_child

 

  def set_root_val(self, obj):

    self.key = obj

 

  def get_root_val(self):

    return self.key

 

 

root = BinaryTree('a')

print(root.get_root_val())

print(root.get_left_child())

root.insert_left('b')

print(root.get_left_child())

print(root.get_left_child().get_root_val())

root.insert_right('c')

print(root.get_right_child())

print(root.get_right_child().get_root_val())

root.get_right_child().set_root_val('hello')

print(root.get_right_child().get_root_val())

C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py

a

None

<__main__.BinaryTree object at 0x00000000024139B0>

b

<__main__.BinaryTree object at 0x00000000024139E8>

c

hello

 

Process finished with exit code 0

Python 은 이 진 트 리 가 옮 겨 다 니 는 재 귀 와 비 재 귀 알고리즘 을 실현 합 니 다.
앞 순 서 를 편력 하 다.

 # -----------     ------------
  #     
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  #      
  def pre_order_non_recursive(self, T):
    """         
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

중간 순서 로 옮 겨 다 닌 다.

# -----------     ------------
  #     
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  #      
  def mid_order_non_recursive(self, T):
    """         
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

뒤 순 서 를 옮 겨 다 닌 다.

# -----------     ------------
  #     
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  #      
  def post_order_non_recursive(self, T):
    """           
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

층 차 를 편력 하 다

# -----------     ------------
  def level_order(self, T):
    """    （       ）      
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) #       
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)

전체 코드

class NodeTree:
  def __init__(self, root=None, lchild=None, rchild=None):
    """     
    Argument:
      lchild: BinTree
           
      rchild: BinTree
           

    Return:
      Tree
    """
    self.root = root
    self.lchild = lchild
    self.rchild = rchild


class BinTree:

  # -----------     ------------
  #     
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  #      
  def pre_order_non_recursive(self, T):
    """         
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

  # -----------     ------------
  #     
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  #      
  def mid_order_non_recursive(self, T):
    """         
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

  # -----------     ------------
  #     
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  #      
  def post_order_non_recursive(self, T):
    """           
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

  # -----------     ------------
  def level_order(self, T):
    """    （       ）      
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) #       
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)

  # -----------       、       ―>       ------------
  def tree_by_pre_mid(self, pre, mid):
    if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
      return
    T = NodeTree(pre[0])
    index = mid.index(pre[0])
    T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
    T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
    return T

  # -----------       、       ―>       ------------
  def tree_by_post_mid(self, post, mid):
    if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
      return
    T = NodeTree(post[-1])
    index = mid.index(post[-1])
    T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
    T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
    return T


if __name__ == '__main__':
  # -----------   ：  、  、  、     -----------
  #      
  nodeTree = NodeTree(1,
            lchild=NodeTree(2,
                    lchild=NodeTree(4,
                            rchild=NodeTree(7))),
            rchild=NodeTree(3,
                    lchild=NodeTree(5),
                    rchild=NodeTree(6)))
  T = BinTree()
  print('      \t')
  T.pre_order_recursive(nodeTree) #     -  
  print('
')
  print('       \t')
  T.pre_order_non_recursive(nodeTree) #     -   
  print('
')
  print('      \t')
  T.mid_order_recursive(nodeTree) #     -  
  print('
')
  print('       \t')
  T.mid_order_non_recursive(nodeTree) #     -   
  print('
')
  print('      \t')
  T.post_order_recursive(nodeTree) #     -  
  print('
')
  print('       \t')
  T.post_order_non_recursive(nodeTree) #     -   
  print('
')
  print('    \t')
  T.level_order(nodeTree) #     
  print('
')

  print('==========================================================================')

  # -----------   ：           -----------
  T = BinTree()
  pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
  mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
  post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']

  newT_pre_mid = T.tree_by_pre_mid(pre, mid) #      、         
  T.post_order_recursive(newT_pre_mid) #       
  print('
')

  newT_post_mid = T.tree_by_post_mid(post, mid) #      、         
  T.pre_order_recursive(newT_post_mid) #       

실행 결과
앞 순 서 를 옮 겨 다 니 며 되돌아오다. 
1 2 4 7 3 5 6
이전 순 서 는 반복 되 지 않 습 니 다. 
1 2 4 7 3 5 6
중간 순서 반복 
4 7 2 1 5 3 6
중간 순서 가 반복 되 지 않 습 니 다. 
4 7 2 1 5 3 6
뒤 순 서 를 옮 겨 다 니 며 되돌아오다. 
7 4 2 5 6 3 1
뒤 순 서 는 반복 되 지 않 는 다. 
7 4 2 5 6 3 1
층 차 를 편력 하 다 
1 2 3 4 5 6 7
==========================================================================
C B E H G I F D A
A B C D E F G H I
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.