python二叉树常用算法总结

1.1 二叉树的初始化

#initial of BinaryTree
class BinaryTree:
  def __init__(self,rootObj):
      self.val = rootObj
      self.left = None
      self.right = None

  def insertLeft(self,newNode):
      if self.left == None:
          self.left = BinaryTree(newNode)
      else:
          t = BinaryTree(newNode)
          t.left = self.left
          self.left = t

  def insertRight(self,newNode):
      if self.right == None:
          self.right = BinaryTree(newNode)
      else:
          t = BinaryTree(newNode)
          t.right = self.right
          self.right = t

1.2 创建一个二叉树

#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
#  18
# 7  11
#3 4 5 6
#   1 3 2 4

root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)

1.3 前序遍历

#递归版本
def PreOrder(self, node):
  if node:
      print(node.val)
      self.PreOrder(node.left)
      self.PreOrder(node.right)
#循环版本
def PreOrderLoop(self, node):
  if node == None:
      return
  stack =[]
  print(node.val)
  stack.append(node)
  node = node.left
  while stack!=[] or node:
      while node:
          print(node.val)
          stack.append(node)
          node = node.left
      node = stack[-1].right
      stack.pop()

#ouput: 18 7 3 4 11 5 1 3 6 2 4 

1.4 中序遍历

#递归版本
def InOrder(self, node):
  if node:
      self.InOrder(node.left)
      print(node.val)
      self.InOrder(node.right)
#循环版本
def InOrderLoop(self, node):
  if node == None:
      return None
  stack = []
  stack.append(node)
  node = node.left
  while stack!=[] or node:
      while node:
          stack.append(node)
          node = node.left
      print(stack[-1].val)
      node = stack[-1].right
      stack.pop()
#output：3 7 4 18 1 5 3 11 2 6 4

1.5 后序遍历

#递归
def PostOrder(self, node):
  if node:
      self.PostOrder(node.left)
      self.PostOrder(node.right)
      print(node.val)
#非递归
def PostOrderLoop(self, node):
  if node == None:
      return
  stack =[]
  stack.append(node)
  pre = None
  while stack!=[]:
      node = stack[-1]
      if ((node.left==None and node.right==None) or
              (pre and (pre == node.left or pre ==node.right))):
          print(node.val)
          pre = node
          stack.pop()
      else:
          if node.right:
              stack.append(node.right)
          if node.left:
              stack.append(node.left)
#output:3 4 7 1 3 5 2 4 6 11 18

1.6 层序遍历

def LevelOrder(self, node):
  if node == None:
      return
  stack = []
  stack.append(node)
  while stack!=[]:
      node = stack[0]
      if node.left:
          stack.append(node.left)
      if node.right:
          stack.append(node.right)
      print(node.val)
      stack.pop(0)
output: 18 7 11 3 4 5 6 1 3 2 4

1.7 计算节点数

#递归版本
def CountNode(self, root):
  if root == None:
      return 0
  return self.CountNode(root.left) + self.CountNode(root.right) + 1
#非递归版本
def CountNodeNotRev(self, root):
  if root == None:
      return 0
  stack = []
  stack.append(root)
  index = 0
  while index<len(stack):
      if stack[index].left:
          stack.append(stack[index].left)
      if stack[index].right:
          stack.append(stack[index].right)
      index += 1
  print(len(stack))
output: 11

1.8 计算树的深度

def getTreeDepth(self, root):
  if root == None:
      return 0
  left = self.getTreeDepth(root.left) + 1
  right = self.getTreeDepth(root.right) + 1
  return left if left>right else right

1.9 计算树的叶子树

def countLeaves(self, root):
  if root == None:
      return 0
  if root.left==None and root.right==None:
      return 1
  return self.countLeaves(root.left)+self.countLeaves(root.right)

1.10 获取第K层节点数

def getKLevel(self, root, K):
  if root == None: return 0
  if K == 1: return 1
  return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1)

1.11 判断两颗二叉树是否相同

def StrucCmp(self, root1, root2):
  if root1 == None and root2 == None: return True
  elif root1 ==None or root2 == None: return False
  return self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right)

1.12 二叉树的镜像

def Mirror(self, root):
  if root == None: return
  tmp = root.left
  root.left = root.right
  root.right = tmp
  self.Mirror(root.left)
  self.Mirror(root.right)

1.13 找最低公共祖先节点

def findLCA(self, root, node1, node2):
  if root == None: return
  if root == node1 or root == node2: return root
  left = self.findLCA(root.left, node1, node2)
  right = self.findLCA(root.right, node1, node2)
  if left and right:
      return root
  return left if left else right

1.14 获取两个节点的距离

def getDist(self, root, node1, node2):
  lca = self.findLCA(root, node1, node2) #找最低公共祖宗节点
  level1 = self.FindLevel(lca, node1) #祖节点到两个节点的距离
  level2 = self.FindLevel(lca, node2)
  return level1+level2
def FindLevel(self, node, target):
  if node == None: return -1
  if node == target: return 0
  level = self.FindLevel(node.left, target)
  if level == -1: level = self.FindLevel(node.right, target)
  if level != -1: return level + 1
  return -1

1.15 找一个节点的所有祖宗节点

def findAllAncestor(self, root, target):
  if root == None: return False
  if root == target: return True
  if self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target):
      print(root.val)
      return True
  return False

关于python二叉树常用算法总结的文章就介绍至此，更多相关python二叉树常用算法，内容请搜索编程宝库以前的文章，希望大家多多支持编程宝库！

小学生也能看懂的python语法之循环语句精解：🌌 专注Golang，Python语言，云原生，人工智能领域得博主；💜 过去经历的意义在于引导你，而非定义你； while循环# 使用print输出模 ...