与えられた二分木を二重リンクリストに変換するPythonプログラム

特定のバイナリツリーを二重リンクリストに変換する必要がある場合は、「ノード」クラスを作成する必要があります。このクラスには、ノードに存在するデータと、リンクリストの次のノードへのアクセスという2つの属性があります。

初期化関数を持つ別の「linked_list」クラスを作成する必要があり、ノードのヘッドは「None」に初期化されます。

二重リンクリストでは、ノードにポインタがあります。現在のノードには、前のノードだけでなく次のノードへのポインタがあります。リストの最後の値は、次のポインタで「NULL」値になります。両方向に移動できます。

二分木は非線形データ構造であり、1つのルートノードが含まれ、ルートを除くすべてのノードが1つの親ノードを持つことができます。二分木ノードは最大2つの子を持つことができます。

特定のバイナリツリーを二重リンクリストに変換し、ノード値を出力するために、ユーザーは複数のメソッドを定義します。

以下は同じのデモンストレーションです-

例

class Node:
   def __init__(self, my_data):
      self.right = None
      self.data = my_data
      self.left = None
class binary_tree_to_list:
   def __init__(self):
      self.root = None
      self.head = None
      self.tail = None
   def convert_tree_to_list(self, node_val):
      if node_val is None:
         return
      self.convert_tree_to_list(node_val.left)
      if (self.head == None) :
         self.head = self.tail = node_val
      else:
         self.tail.right = node_val
         node_val.left = self.tail
         self.tail = node_val
      self.convert_tree_to_list(node_val.right)
   def print_it(self):
      curr = self.head
      if (self.head == None):
         print("The list is empty")
         return
      print("The nodes are :")
      while curr != None:
         print(curr.data)
         curr = curr.right
my_instance = binary_tree_to_list()
print("Elements are being added to the list")
my_instance.root = Node(10)
my_instance.root.left = Node(14)
my_instance.root.right = Node(17)
my_instance.root.left.left = Node(22)
my_instance.root.left.right = Node(29)
my_instance.root.right.left = Node(45)
my_instance.root.right.right = Node(80)
my_instance.convert_tree_to_list(my_instance.root)
my_instance.print_it()

出力

Elements are being added to the list
The nodes are :
22
14
29
10
45
17
80

説明

• 「Node」クラスが作成されます。
• 必要な属性を持つ別のクラスが作成されます。
• 「convert_tree_to_list」という名前の別のメソッドが定義されています。これは、指定されたバイナリツリーを二重リンクリストに変換するために使用されます。
• 循環リンクリストのノードを表示する「print_it」という名前の別のメソッドが定義されています。
• 「binary_tree_to_list」クラスのオブジェクトが作成され、そのオブジェクトでメソッドが呼び出されて、ツリーが二重リンクリストに変換されます。
• 「init」メソッドが定義されており、二重にリンクされたリストのルート、ヘッド、およびテールノードがNoneになります。
• 「convert_tree_to_list」メソッドが呼び出されます。
• バイナリツリーを反復処理し、二重にリンクされたリストに変換します。
• これは、「print_it」メソッドを使用してコンソールに表示されます。