Python 이 진 트 리 의 정의 및 자주 사용 되 는 알고리즘 분석

이 글 의 사례 는 Python 이 진 트 리 의 정의 와 자주 사용 되 는 알고리즘 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
이 진 트 리 의 역 사 를 말하자면 대학 에서 말 하 는 것 은 재 귀 알고리즘 이 고 대부분 사람들 이 먼저 생각 하 는 것 도 재 귀 알고리즘 이다.이상 적 이 고 추구 하 는 프로그래머 로 서비 재 귀 알고리즘 을 배 워 이 진 트 리 를 옮 겨 다 니 는 것 도 배 워 야 한다.이 진 트 리 의 비 재 귀 알고리즘 은 보조 스 택 을 사용 해 야 합 니 다.알고리즘 은 정말 교묘 하여 뇌 구멍 을 크게 열 수 있 습 니 다.
다음 주제 로 바로 들 어가 기:
이 진 트 리 를 정의 합 니 다.관리 가 스스로 그 모양 을 상상 하 세 요.

class BinNode( ):
  def __init__( self, val ):
    self.lchild = None
    self.rchild = None
    self.value = val
binNode1 = BinNode( 1 )
binNode2 = BinNode( 2 )
binNode3 = BinNode( 3 )
binNode4 = BinNode( 4 )
binNode5 = BinNode( 5 )
binNode6 = BinNode( 6 )
binNode1.lchild = binNode2
binNode1.rchild = binNode3
binNode2.lchild = binNode4
binNode2.rchild = binNode5
binNode3.lchild = binNode6

우선 순 서 를 옮 겨 다 니 기:

'''
       
'''
def bin_tree_pre_order_traverse( root, visit_func ):
  s = Stack()
  s.push( root )
  while not s.is_empty():
    node = s.pop()
    visit_func( node )
    if node.rchild:
      s.push( node.rchild )
    if node.lchild:
      s.push( node.lchild )

중간 순서 옮 겨 다 니 기:

'''
       
'''
def bin_tree_in_order_traverse( root, visit_func ):
  s = Stack()
  node = root
  while node or not s.is_empty():
    if node:
      s.push( node )
      node = node.lchild
    else:
      node = s.pop()
      visit_func( node )
      node = node.rchild

다음 순서 옮 겨 다 니 기:
뒷 순 서 를 옮 겨 다 니 면서 왼쪽 아이 와 오른쪽 아이 가 모두 방문 되 어야 뿌리 결산 점 을 방문 할 수 있 고 왼쪽 아 이 는 오른쪽 아이 앞에서 방문 해 야 한다.이것 은 절차 의 통제 에 어 려 운 문 제 를 가 져 왔 다.다음은 두 가지 사고방식 을 소개 한다.
사고 1,더 블 스 택 법,이런 방식 은 이해 하기 쉬 우 며 단점 은 두 개의 스 택 이 필요 하 다 는 것 이다.

'''
       
'''
def bin_tree_post_order_traverse( root, visit_func ):
  s1 = Stack()
  s2 = Stack()
  s1.push( root )
  while not s1.is_empty():
    node = s1.pop()
    s2.push( node )
    if node.lchild:
      s1.push( node.lchild )
    if node.rchild:
      s1.push( node.rchild )
  while not s2.is_empty():
    visit_func( s2.pop() )

둘째,뿌리 결산 점 이 왼쪽 아이 와 오른쪽 아이 가 방문 한 후에 야 방문 할 수 있 기 때문에 모든 결산 점 P 에 대해 먼저 창고 에 넣 어야 한다.P 가 왼쪽 아이 와 오른쪽 아이 가 존재 하지 않 는 다 면 직접 방문 할 수 있 습 니 다.또는 P 는 왼쪽 아이 나 오른쪽 아이 가 존재 하지만 왼쪽 아이 와 오른쪽 아이 가 모두 방문 되 었 으 면 이 노드 를 직접 방문 할 수 있 습 니 다.상기 두 가지 상황 이 아니라면 P 의 오른쪽 아이 와 왼쪽 아 이 를 순서대로 창고 에 넣 으 면 창고 꼭대기 요 소 를 찾 을 때마다 왼쪽 아이 가 오른쪽 아이 앞에서 방문 되 고 왼쪽 아이 와 오른쪽 아 이 는 모두 뿌리 노드 앞에서 방문 된다.

def bin_tree_post_order_traverse2( root, visit_func ):
  curr = root
  prev = None
  s = Stack()
  s.push( curr )
  while not s.is_empty():
    curr = s.peek()
    if ( not curr.lchild and not curr.rchild ) or ( prev and ( prev == curr.lchild or prev == curr.rchild ) ):
      visit_func( curr )
      s.pop()
　　　　　　　prev = curr
    else:
      if curr.rchild:
        s.push( curr.rchild )
      if curr.lchild:
        s.push( curr.lchild )

반복:

def bin_tree_level_traverse( root, visit_func ):
  queue = Queue()
  queue.enqueue( root )
  while not queue.is_empty():
    node = queue.dequeue().value
    visit_func( node )
    if node.lchild:
      queue.enqueue( node.lchild )
    if node.rchild:
      queue.enqueue( node.rchild )

더 많은 파 이 썬 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.