Python - 二叉樹

上一頁
下一頁

樹表示由邊連線的節點。它是一種非線性資料結構。它具有以下特性：

  • 一個節點被標記為根節點。

  • 除根節點外的每個節點都與一個父節點關聯。

  • 每個節點可以具有任意數量的子節點。

我們使用前面討論的節點概念在 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

插入到樹中

為了插入到樹中，我們使用上面建立的相同的 Node 類，並向其新增一個 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 類為根節點以及左節點和右節點建立佔位符。然後，我們建立一個 insert 函式來向樹中新增資料。最後，透過建立一個空列表並將左節點首先新增到列表中，然後是根節點或父節點，來實現中序遍歷邏輯。

最後，新增左節點以完成中序遍歷。請注意，此過程會對每個子樹重複，直到遍歷所有節點。

示例

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 類為根節點以及左節點和右節點建立佔位符。然後，我們建立一個 insert 函式來向樹中新增資料。最後，透過建立一個空列表並將根節點首先新增到列表中，然後是左節點，來實現前序遍歷邏輯。

最後，新增右節點以完成前序遍歷。請注意，此過程會對每個子樹重複，直到遍歷所有節點。

示例

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 類為根節點以及左節點和右節點建立佔位符。然後，我們建立一個 insert 函式來向樹中新增資料。最後，透過建立一個空列表並將左節點首先新增到列表中，然後是右節點，來實現後序遍歷邏輯。

最後，新增根節點或父節點以完成後序遍歷。請注意，此過程會對每個子樹重複，直到遍歷所有節點。

示例

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]
列印頁面
上一頁
下一頁
廣告
© . All rights reserved.