binary-tree - バイナリ ツリーのプリ オーダーとポスト オーダーのトラバーサルは同じですか?

Question

この場合が真である二分木はありますか?

二分木が 1 つのルート ノードのみで構成されている場合を除き、そうは思いません。

Answer 1

その通りです。ルートノードに少なくとも1つの子があるとします。

プレオーダートラバーサルでは、ルートノードが最初に処理されます。子供はそれの後に来る。これは、擬似コードで簡単に確認できます。

preorder(node)
  if node == null then return
  print node.value
  preorder(node.left) 
  preorder(node.right)

ポストオーダートラバーサルでは、ルートノードが最後に処理され、子が最初に処理されます。コードをもう一度参照してください。

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  print node.value

（ウィキペディアの擬似コード）。

結論として、二分木に複数のノードがある場合、トラバーサルは必然的に異なります。