HTML CSS JAVASCRIPT PYTHON PYTHON2 JAVA C C++ C# SQL Excel Linux AI BOOTSTRAP PHP 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ
❮ 上一节 下一节 ❯

Python - 二叉树

树表示由边连接的节点。 它是一种非线性数据结构。 它具有以下属性 −

  • 一个节点被标记为根节点。

  • 除根节点之外的每个节点都与一个父节点相关联。

  • 每个节点都可以有一个任意数量的子节点。

我们使用前面讨论的概念 os 节点在 python 中创建树数据结构。 我们指定一个节点作为根节点，然后添加更多节点作为子节点。 下面是创建根节点的程序。

创建根

我们创建一个 Node 类并为节点添加赋值。 这成为只有一个根节点的树。

示例

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
   def PrintTree(self):
      print(self.data)

root = Node(10)
root.PrintTree()

输出

当上面的代码执行时，会产生如下结果 −

10

插入树

要插入到树中，我们使用上面创建的相同节点类并向其添加 insert 插入类。 insert 插入类将节点的值与父节点进行比较，并决定将其添加为左节点或右节点。 最后，PrintTree 类用于打印树。

示例

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

   def insert(self, data):
# Compare the new value with the parent node
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
               if self.right is None:
                  self.right = Node(data)
               else:
                  self.right.insert(data)
      else:
         self.data = data

# Print the tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

输出

当上面的代码执行时，会产生如下结果 −

3 6 12 14

遍历树

可以通过决定访问每个节点的顺序来遍历树。 可以清楚地看到，我们可以从一个节点开始，然后首先访问左子树，然后访问右子树。 或者我们也可以先访问右子树，再访问左子树。 因此，这些树遍历方法有不同的名称。

树遍历算法

遍历是访问树的所有节点并打印它们的值的过程。 因为，所有节点都通过边（链接）连接，我们总是从根（头）节点开始。 也就是说，我们不能随机访问树中的一个节点。 我们使用三种方式来遍历一棵树。

  • 有序遍历

  • 前序遍历

  • 后序遍历

有序遍历

在这种遍历方法中，先访问左子树，然后访问根，再访问右子树。 我们应该永远记住，每个节点都可能代表一个子树本身。

在下面的 python 程序中，我们使用 Node 类为根节点以及左右节点创建占位符。 然后，我们创建一个插入函数来向树中添加数据。 最后，通过创建一个空列表并先添加左节点，然后添加根节点或父节点来实现中序遍历逻辑。

最后添加左节点，完成有序遍历。 请注意，对每个子树重复此过程，直到遍历所有节点。

示例

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         else data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()
# Inorder traversal
# Left -> Root -> Right
   def inorderTraversal(self, root):
      res = []
      if root:
         res = self.inorderTraversal(root.left)
         res.append(root.data)
         res = res + self.inorderTraversal(root.right)
      return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

输出

当上面的代码执行时，会产生如下结果 −

[10, 14, 19, 27, 31, 35, 42]

前序遍历

在这种遍历方式中，先访问根节点，再访问左子树，最后访问右子树。

在下面的 python 程序中，我们使用 Node 类为根节点以及左右节点创建占位符。 然后，我们创建一个插入函数来向树中添加数据。 最后，通过创建一个空列表并先添加根节点再添加左节点来实现前序遍历逻辑。

最后添加右节点，完成前序遍历。 请注意，对每个子树重复此过程，直到遍历所有节点。

示例

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         elif data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:
               self.right.insert(data)
         else:
            self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
      print( self.data),
      if self.right:
         self.right.PrintTree()
# Preorder traversal
# Root -> Left ->Right
   def PreorderTraversal(self, root):
      res = []
      if root:
         res.append(root.data)
         res = res + self.PreorderTraversal(root.left)
         res = res + self.PreorderTraversal(root.right)
      return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

输出

当上面的代码执行时，会产生如下结果 −

[27, 14, 10, 19, 35, 31, 42]

后序遍历

在这种遍历方法中，最后访问根节点，因此得名。 首先遍历左子树，然后遍历右子树，最后遍历根节点。

在下面的 python 程序中，我们使用 Node 类为根节点以及左右节点创建占位符。 然后，我们创建一个插入函数来向树中添加数据。 最后，通过创建一个空列表并先添加左节点再添加右节点来实现后序遍历逻辑。

最后添加根节点或父节点，完成后序遍历。 请注意，对每个子树重复此过程，直到遍历所有节点。

示例

class Node:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data
# Insert Node
   def insert(self, data):
      if self.data:
         if data < self.data:
            if self.left is None:
               self.left = Node(data)
            else:
               self.left.insert(data)
         else if data > self.data:
            if self.right is None:
               self.right = Node(data)
            else:

               self.right.insert(data)
      else:
         self.data = data
# Print the Tree
   def PrintTree(self):
      if self.left:
         self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = self.PostorderTraversal(root.left)
res = res + self.PostorderTraversal(root.right)
res.append(root.data)
return res
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

输出

当上面的代码执行时，会产生如下结果 −

[10, 19, 14, 31, 42, 35, 27]
❮ 上一节 下一节 ❯