Python 프로그래밍에서 이진 트리와 7가지 탐색 방법을 구현하는 방법에 대한 자세한 설명

이 글에서는 주로 PythonProgramming구현과 7가지 순회 방법을 소개합니다. Python 이진 트리의 정의와 일반적인 순회 연산 기법을 예제 형식으로 자세히 분석합니다.

이 문서에서는 이진 트리 및 순회 메서드 구현 예제를 통해 Python을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

소개:

Tree는 매우 중요한 유형의 데이터 구조로, 주요 목적은 검색 효율성을 높이는 것이며 반복 검색에 더 좋습니다. . 이진 정렬 트리, FP-트리 등이 있습니다. 또한 허프만 트리와 같이 코딩 효율성을 향상시키는 데에도 사용할 수 있습니다.

Code:

Python을 사용하여 트리 구성과 여러 순회 알고리즘을 구현합니다. 어렵지는 않지만 코드를 요약합니다. 구현 기능:

1 트리 구성
② Recursion 선순 순회, 순순 순회, 후순 순회 구현
3 스택은 선순 순회, 순순 순회, 후순 순회를 구현합니다
IV Queue 계층적 순회 구현

#coding=utf-8
class Node(object):
  """节点类"""
  def init(self, elem=-1, lchild=None, rchild=None):
    self.elem = elem
    self.lchild = lchild
    self.rchild = rchild
class Tree(object):
  """树类"""
  def init(self):
    self.root = Node()
    self.myQueue = []
  def add(self, elem):
    """为树添加节点"""
    node = Node(elem)
    if self.root.elem == -1: # 如果树是空的，则对根节点赋值
      self.root = node
      self.myQueue.append(self.root)
    else:
      treeNode = self.myQueue[0] # 此结点的子树还没有齐。
      if treeNode.lchild == None:
        treeNode.lchild = node
        self.myQueue.append(treeNode.lchild)
      else:
        treeNode.rchild = node
        self.myQueue.append(treeNode.rchild)
        self.myQueue.pop(0) # 如果该结点存在右子树，将此结点丢弃。
  def front_digui(self, root):
    """利用递归实现树的先序遍历"""
    if root == None:
      return
    print root.elem,
    self.front_digui(root.lchild)
    self.front_digui(root.rchild)
  def middle_digui(self, root):
    """利用递归实现树的中序遍历"""
    if root == None:
      return
    self.middle_digui(root.lchild)
    print root.elem,
    self.middle_digui(root.rchild)
  def later_digui(self, root):
    """利用递归实现树的后序遍历"""
    if root == None:
      return
    self.later_digui(root.lchild)
    self.later_digui(root.rchild)
    print root.elem,
  def front_stack(self, root):
    """利用堆栈实现树的先序遍历"""
    if root == None:
      return
    myStack = []
    node = root
    while node or myStack:
      while node:           #从根节点开始，一直找它的左子树
        print node.elem,
        myStack.append(node)
        node = node.lchild
      node = myStack.pop()      #while结束表示当前节点node为空，即前一个节点没有左子树了
      node = node.rchild         #开始查看它的右子树
  def middle_stack(self, root):
    """利用堆栈实现树的中序遍历"""
    if root == None:
      return
    myStack = []
    node = root
    while node or myStack:
      while node:           #从根节点开始，一直找它的左子树
        myStack.append(node)
        node = node.lchild
      node = myStack.pop()      #while结束表示当前节点node为空，即前一个节点没有左子树了
      print node.elem,
      node = node.rchild         #开始查看它的右子树
  def later_stack(self, root):
    """利用堆栈实现树的后序遍历"""
    if root == None:
      return
    myStack1 = []
    myStack2 = []
    node = root
    myStack1.append(node)
    while myStack1:          #这个while循环的功能是找出后序遍历的逆序，存在myStack2里面
      node = myStack1.pop()
      if node.lchild:
        myStack1.append(node.lchild)
      if node.rchild:
        myStack1.append(node.rchild)
      myStack2.append(node)
    while myStack2:             #将myStack2中的元素出栈，即为后序遍历次序
      print myStack2.pop().elem,
  def level_queue(self, root):
    """利用队列实现树的层次遍历"""
    if root == None:
      return
    myQueue = []
    node = root
    myQueue.append(node)
    while myQueue:
      node = myQueue.pop(0)
      print node.elem,
      if node.lchild != None:
        myQueue.append(node.lchild)
      if node.rchild != None:
        myQueue.append(node.rchild)
if name == 'main':
  """主函数"""
  elems = range(10)      #生成十个数据作为树节点
  tree = Tree()     #新建一个树对象
  for elem in elems:
    tree.add(elem)      #逐个添加树的节点
  print '队列实现层次遍历:'
  tree.level_queue(tree.root)
  print '\n\n递归实现先序遍历:'
  tree.front_digui(tree.root)
  print '\n递归实现中序遍历:'
  tree.middle_digui(tree.root)
  print '\n递归实现后序遍历:'
  tree.later_digui(tree.root)
  print '\n\n堆栈实现先序遍历:'
  tree.front_stack(tree.root)
  print '\n堆栈实现中序遍历:'
  tree.middle_stack(tree.root)
  print '\n堆栈实现后序遍历:'
  tree.later_stack(tree.root)

요약:

트리 순회에는 두 가지 주요 유형이 있습니다. 하나는 사전 주문, 중간 주문 및 사후 주문과 같은 깊이 우선 순회입니다. 계층적 순회와 같은 너비 우선 순회. 둘의 차이는 트리 구조에서는 그다지 뚜렷하지 않지만, 트리에서 유방향 그래프, 무방향 그래프로 확장할 때 깊이 우선 탐색과 너비 우선 탐색의 효율성과 역할은 여전히 ​​매우 다릅니다.

깊이 우선은 일반적으로 재귀를 사용하고, 너비 ​​우선은 일반적으로 대기열을 사용합니다. 일반적으로 재귀를 사용하여 구현할 수 있는 대부분의 알고리즘은 스택을 사용하여 구현할 수도 있습니다.

재귀적으로 트리를 구성하는 방법이 있다는 인상을 받았지만 트리를 구성하는 방법을 전혀 알 수 없었습니다. 신중하게 생각해 본 결과 재귀적 아이디어는 깊이 우선 알고리즘과 다소 유사하며 트리 구성은 너비 우선이어야 한다는 것을 깨달았습니다. 재귀를 사용하는 경우 트리 깊이 지정 등 종료 조건이 있어야 합니다. 그렇지 않으면 구성된 트리가 왼쪽 단일 하위 트리 또는 오른쪽 단일 하위 트리 쪽으로 편향됩니다. 따라서 일반적인 트리 구성에는 큐를 사용하는 것이 좋습니다.

위 내용은 Python 프로그래밍에서 이진 트리와 7가지 탐색 방법을 구현하는 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!