Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonでプレオーダーおよびインオーダートラバーサルからバイナリツリーを構築する


二分木のインオーダーおよびプレオーダートラバーサルシーケンスがあるとします。これらのシーケンスからツリーを生成する必要があります。したがって、プレオーダーシーケンスとインオーダーシーケンスが[3,9,20,15,7]と[9,3,15,20,7]の場合、ツリーは-

になります。

Pythonでプレオーダーおよびインオーダートラバーサルからバイナリツリーを構築する

手順を見てみましょう-

  • メソッドがビルドツリーと呼ばれ、プレオーダーリストとインオーダーリストがあるとします
  • root:=プレオーダーから最初のノードを削除し、プレオーダーから最初のノードを削除します
  • root_index:=インオーダーリストからのroot.valのインデックス
  • leftまたはroot:=buildTree(preorder、0からroot_indexまでの順序のサブセット)
  • rightまたはroot:=buildTree(preorder、root_index + 1からendまでの順序のサブセット)

理解を深めるために、次の実装を見てみましょう-

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   #print using inorder traversal
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ',')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, preorder, inorder):
      if inorder:
         root = TreeNode(preorder.pop(0))
         root_index = inorder.index(root.data)
         root.left = self.buildTree(preorder,inorder[:root_index])
         root.right = self.buildTree(preorder,inorder[root_index+1:])
         return root
ob1 = Solution()
print_tree(ob1.buildTree([3,9,20,15,7], [9,3,15,20,7]))

入力

[3,9,20,15,7]
[9,3,15,20,7]

出力

9, 3, 15, 20, 7,

  1. Pythonでの二分木順序トラバーサル

    二分木があるとします。再帰を使用せずに、順序どおりのトラバーサルスキームを使用してこのツリーをトラバースする必要があります。したがって、ツリーが次のような場合 その場合、トラバーサルは[2,5,7,10,15,20]になります。 これを解決するには、次の手順に従います- 2つの配列resとスタックを作成し、curr:=rootを設定します 1つの無限ループを実行します 現在がnullではない場合 currをスタックにプッシュし、curr:=currの左側に設定します スタックの長さが0の場合、resを返します node:=スタックからポップされた要素 ノードの値をresに

  2. Pythonで二分木を反転する

    二分木があるとします。私たちの仕事は、逆二分木を作成することです。したがって、ツリーが以下のようになっている場合- 反転したツリーは次のようになります これを解決するために、再帰的アプローチを使用します ルートがnullの場合は、戻ります 左右のポインタを入れ替える 左のサブツリーと右のサブツリーを再帰的に解決します 例(Python) 理解を深めるために、次の実装を見てみましょう- class TreeNode:    def __init__(self, data, left = None, right = None):