python 3 이 진 트 리 의 스 트 리밍 과 재 귀 알고리즘 분석(소결)실현

1.이 진 트 리 의 세 가지 옮 겨 다 니 는 방식
이 진 트 리 는 세 가지 옮 겨 다 니 는 방식 이 있 습 니 다.먼저 옮 겨 다 니 고 중간 에 옮 겨 다 니 며 다음 에 옮 겨 다 니 는 것 입 니 다.먼저 가운데 에 있 는 것 은 뿌리 노드 를 방문 하 는 순서 입 니 다.
전체적인 사 고 를 옮 겨 다 니 며:나 무 를 가장 작은 하위 트 리 로 나 눈 다음 순서대로 출력 합 니 다.

1.1 선착순 옮 겨 다 니 기
a.루트 노드 에 먼저 접근 하기
왼쪽 노드 방문
c 오른쪽 노드 에 접근
　　　　a（b ( d ( h ) )( e ( i ) )）( c ( f )( g )) -- abdheicfg
1.2 중 순 옮 겨 다 니 기
왼쪽 노드 에 먼저 접근
b 접근 루트 노드
c 오른쪽 노드 에 접근
　　　　( ( ( h ) d ) b ( ( i ) e ) ) a ( ( f ) c ( g ) ) -- hdbieafcg
1.3 후 순 옮 겨 다 니 기
왼쪽 노드 에 먼저 접근
b 오른쪽 노드 에 접근
c 접근 루트 노드
　　　　((hd)(ie)b)(fgc)a -- hdiebfgca
2.python 3 트 리 구조 구현

#       ，                        
class Node():

  def __init__(self,data=None):
    self._data = data
    self._left = None
    self._right = None

  def set_data(self,data):
    self._data = data

  def get_data(self):
    return self._data

  def set_left(self,node):
    self._left = node

  def get_left(self):
    return self._left

  def set_right(self,node):
    self._right = node

  def get_right(self):
    return self._right

if __name__ == '__main__':
  #      
  root_node = Node('a')
  # root_node.set_data('a')
  #       
  left_node = Node('b')
  #       
  right_node = Node('c')
  
  #          ，        
  root_node.set_left(left_node)
  #          ，        
  root_node.set_right(right_node)

  print(root_node.get_data(),root_node.get_left().get_data(),root_node.get_right().get_data())

3.트 리 의 재 귀적 옮 겨 다 니 기 실현(앞 뒤 옮 겨 다 니 기)
다음 예 는 나무의 스 트 리밍 알고리즘 입 니 다.그 중에서 나무의 종 류 를 최적화 시 켰 습 니 다.

#       ，                        
class Node():

  def __init__(self,data =None,left=None,right = None):
    self._data = data
    self._left = left
    self._right = right


#             
def pro_order(tree):
  if tree == None:
    return False
  print(tree._data)
  pro_order(tree._left)
  pro_order(tree._right)

#    
def pos_order(tree):
  if tree == None:
    return False
  # print(tree.get_data())
  pos_order(tree._left)
  pos_order(tree._right)
  print(tree._data)

#    
def mid_order(tree):
  if tree == None:
    return False
  # print(tree.get_data())
  mid_order(tree._left)
  print(tree._data)
  mid_order(tree._right)


#    
def row_order(tree):
  # print(tree._data)
  queue = []
  queue.append(tree)
  while True:
    if queue==[]:
      break
    print(queue[0]._data)
    first_tree = queue[0]
    if first_tree._left != None:
      queue.append(first_tree._left)
    if first_tree._right != None:
      queue.append(first_tree._right)
    queue.remove(first_tree)

if __name__ == '__main__':

  tree = Node('A',Node('B',Node('D'),Node('E')),Node('C',Node('F'),Node('G')))
  pro_order(tree)
  mid_order(tree)
  pos_order(tree)

4.재 귀 알고리즘


위의 두 장의 그림 은 지인 에서 붙 여 온 것 이다.그림 1 에서 돌아 온 후에 바로 이전 단계 로 돌아 갈 것 입 니 다.이런 생각 은 전면적 이지 않 습 니 다.비교적 합 리 적 인 반환 은 그림 2 와 같이 하위 함수 가 돌아 올 때 하위 함 수 를 호출 하 는 노드 로 돌아 가 야 합 니 다.그러면 나머지 코드 를 실행 하고 다시 이전 단계 로 돌아 가 야 합 니 다.
그림 1 로 돌아 오 면 이 진 트 리 의 옮 겨 다 니 는 것 은 전례 에 따라 이 루어 지지 않 는 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.