Python - 数据结构之二叉树

  • 简述

    树表示由边连接的节点。它是一种非线性数据结构。它具有以下特性 -
    • 一个节点被标记为根节点。
    • 除根以外的每个节点都与一个父节点相关联。
    • 每个节点可以有任意数量的 chid 节点。
    我们使用前面讨论的概念 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
    
  • 插入树中

    要插入到树中,我们使用上面创建的相同节点类并向其添加插入类。插入类将节点的值与父节点进行比较,并决定将其添加为左节点还是右节点。最后,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]