algorithm - 二分木の最短枝の長さを返すアルゴリズム

Question

二分木は、ノード n に対して、l(n) が n の左の子を与え、r(n) が n の右の子を与えるように、2 つの関数 l および r を使用してエンコードできます。

木の枝は根から葉への経路であり、特定の葉への枝の長さは、根からその葉への経路上の円弧の数です。

MinBranch(l,r,x) を、関数 l および r によってエンコードされたバイナリ ツリーと、バイナリ ツリーのルート ノード x を取得する単純な再帰アルゴリズムとし、バイナリ ツリーの最短ブランチを返します。

このアルゴリズムの疑似コードを提供してください。

Answer 1

最短の枝の長さを取得する方法についての回答を受け取ったようですが、実際の宿題は、おそらくノードのリストとして、枝自体を返すことです。Noneしたがって、 null を意味するために使用して、実際にブランチを返すための実行可能な擬似コード (つまり、Python) は次のとおりです。

def MinBranch(l, r, x):
  if x is None: return []
  left_one = MinBranch(l, r, l(x))
  right_one = MinBranch(l, r, r(x))
  if len(left_one) < len(right_one):
    tail = left_one
  else:
    tail = right_one
  return [x] + tail

Answer 2

両方の枝を見てください。それぞれの最短経路の長さを見つけます。小さい方に 1 を追加し、それを最短の枝と見なします。

Answer 3

^{R が結果である O(2 R} )でも見つけることができます。ツリーが非常に不均衡または無限である場合に役立ちます。<= O(N) です。

これは、反復深化 DFS を使用して行うことができます。

Answer 4

function recurseMin(n)
{
if r(n) is null and l(n) is null, return 1
if r(n) is not null, rightSum = recurseMin( r(n-1) )
if l(n) is not null, leftSum = recurseMin ( l(n-1) )
return 1 + min( leftSum, rightSum )
}