Python 이 이 진 트 리 를 재건 하 는 세 가지 방법 에 대한 상세 한 설명

이 글 은 파 이 썬 이 이 진 트 리 를 재건 하 는 세 가지 방법 을 실례 로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
학습 알고리즘 에서 이 진 트 리 를 재 구축 하 는 방법 을 찾 습 니 다.

input 순서 로 문자 재 구축 을 입력 합 니 다

순서 문자열 재 귀적 해석 재 구축

순서 문자열 스 택 분석 재 구축

뒤의 내용 을 보기 귀 찮 으 면 이 사 이 트 를 직접 클릭 하여 다운로드 할 수 있 습 니 다전체 인 스 턴 스 코드
사고의 방향
학습 알고리즘 에서 python 알고리즘 에 대한 자료 가 상대 적 으로 적 고 이 진 트 리 의 해석 과 재건 이 적어 돌 을 만 지 며 강 을 건 널 수 밖 에 없습니다.
서로 다른 방식 으로 이 진 트 리 를 옮 겨 다 니 면 서로 다른 노드 의 정렬 을 얻 을 수 있다.그러면 이미 알 고 있 는 노드 정렬 전제 에서 특정한 옮 겨 다 니 는 방식 으로 정렬 을 분석 하여 이 진 트 리 를 구축 할 수 있다.
응용 에 사용 하면 여러 가지 식 을 분석 할 수 있 고 웹 페이지,xml 등 을 분석 할 수 있 습 니 다.
본 고 는 앞 순 서 를 옮 겨 다 니 는 방식 으로 배열 하여 이미 알 고 있 는 문자열 을 분석 하고 이 진 트 리 를 생 성 한다.초보 자 는 문 제 를 푸 는 것 을 목적 으로 아직 최적화 되 지 않 아 파 이 썬 의 간결 하고 아름 다운 모습 을 나타 내지 못 했다.큰 소 에 게 아 낌 없 는 지적 을 바 랍 니 다.
우선 input 입력 을 사용 합 니 다.
노드 클래스

class treeNode:
 def __init__(self, rootObj = None, leftChild = None, rightChild = None):
  self.key = rootObj
  self.leftChild = None
  self.rightChild = None

input 방법 이 진 트 리 재 구축

 def createTreeByInput(self, root):
  tmpKey = raw_input("please input a key, input '#' for Null")
  if tmpKey == '#':
   root = None
  else:
   root = treeNode(rootObj=tmpKey)
   root.leftChild = self.createTreeByInput(root.leftChild)
   root.rightChild = self.createTreeByInput(root.rightChild)
  return root

다음 두 가지 방법 은 미리 편 성 된 문자열 을 사용 하여 list 방법 을 통 해 list 로 변환 하여 해석 합 니 다.
my Tree 는 빈 나 무 를 예화 합 니 다.
재 귀 방법 을 호출 하여 이 진 트 리 를 재건 하 다.

 treeElementList = '124#8##5##369###7##'
 myTree = myTree.createTreeByListWithRecursion(list(treeElementList))
 printBTree(myTree, 0)

재 귀 방법 으로 이 진 트 리 를 재건 하 다.

 def createTreeByListWithRecursion(self, preOrderList):
  """
             
  :param preOrder:       
  :return:    
  """
  preOrder = preOrderList
  if preOrder is None or len(preOrder) <= 0:
   return None
  currentItem = preOrder.pop(0) #   C      
  if currentItem is '#':
   root = None
  else:
   root = treeNode(currentItem)
   root.leftChild = self.createTreeByListWithRecursion(preOrder)
   root.rightChild = self.createTreeByListWithRecursion(preOrder)
  return root

스 택 방법 으로 이 진 트 리 를 재 구축 합 니 다.

 treeElementList = '124#8##5##369###7##'
 myTree = myTree.createTreeByListWithStack(list(treeElementList))
 printBTree(myTree, 0)

스 택 으로 이 진 트 리 재 구축

def createTreeByListWithStack(self, preOrderList):
 """
            
 :param preOrder:       
 :return:    
 """
 preOrder = preOrderList
 pStack = SStack()
 # check
 if preOrder is None or len(preOrder) <= 0 or preOrder[0] is '#':
  return None
 # get the root
 tmpItem = preOrder.pop(0)
 root = treeNode(tmpItem)
 # push root
 pStack.push(root)
 currentRoot = root
 while preOrder:
  # get another item
  tmpItem = preOrder.pop(0)
  # has child
  if tmpItem is not '#':
   # does not has left child, insert one
   if currentRoot.leftChild is None:
    currentRoot = self.insertLeft(currentRoot, tmpItem)
    pStack.push(currentRoot.leftChild)
    currentRoot = currentRoot.leftChild
   # otherwise insert right child
   elif currentRoot.rightChild is None:
    currentRoot = self.insertRight(currentRoot, tmpItem)
    pStack.push(currentRoot.rightChild)
    currentRoot = currentRoot.rightChild
  # one child is null
  else:
   # if has no left child
   if currentRoot.leftChild is None:
    currentRoot.leftChild = None
    # get another item fill right child
    tmpItem = preOrder.pop(0)
    # has right child
    if tmpItem is not '#':
     currentRoot = self.insertRight(currentRoot, tmpItem)
     pStack.push(currentRoot.rightChild)
     currentRoot = currentRoot.rightChild
    # right child is null
    else:
     currentRoot.rightChild = None
     # pop itself
     parent = pStack.pop()
     # pos parent
     if not pStack.is_empty():
      parent = pStack.pop()
     # parent become current root
     currentRoot = parent
     # return from right child, so the parent has right child, go to parent's parent
     if currentRoot.rightChild is not None:
      if not pStack.is_empty():
       parent = pStack.pop()
       currentRoot = parent
   # there is a leftchild ,fill right child with null and return to parent
   else:
    currentRoot.rightChild = None
    # pop itself
    parent = pStack.pop()
    if not pStack.is_empty():
     parent = pStack.pop()
    currentRoot = parent
 return root

두 갈래 트 리 보이 기

def printBTree(bt, depth):
 '''''
          ，#       NULL
 '''
 ch = bt.key if bt else '#'
 if depth > 0:
  print '%s%s%s' % ((depth - 1) * ' ', '--', ch)
 else:
  print ch
 if not bt:
  return
 printBTree(bt.leftChild, depth + 1)
 printBTree(bt.rightChild, depth + 1)

이 진 트 리 의 코드 를 인쇄 하고 어떤 인형 코드 를 사용 해 주 셔 서 감사합니다.
input 입력 및 이 진 트 리 결과 표시
 
문자열 의 결 과 를 분석 합 니 다.
 
전체 코드 참조:https://github.com/flyhawksz/study-algorithms/blob/master/Class_BinaryTree2.py
Python 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.