algorithm - 木の経路長の再帰的定義

Question

ツリーのパス長を計算する適切な方法は、すべての k について、k とレベル k のノード数の積を合計することです。

ツリーのパスの長さは、ツリーのすべてのノードのレベルの合計です。パスの長さは、次のように単純な再帰定義を持つことができます。

N 個のノードを持つツリーのパスの長さは、そのルートのサブツリーのパスの長さの合計に N-1 を加えたものです。

上記の再帰的定義に従うことができません。簡単な例で親切に説明してください。

Answer 1

再帰を理解する

パスの長さは、次のように単純な再帰的定義を持つことができます。

Nノードのツリーのパス長は、ルートのサブツリーのパス長とN-1の合計です。

まず、パスの長さを理解する必要があります。これは、ノードとルートの間のすべての距離の合計です。

この考えを念頭に置いて、子のないルートノードのパス長が0であることを確認するのは簡単です。ルートノードまでの距離を持つノードはありません。

いくつかの木のパスの長さがすでにわかっていると仮定しましょう。Rすでに持っているすべてのツリーを接続する新しいノードを作成する場合は、ルートノードまでの距離がどのように変化するかを考えてください。

以前は、ツリーのルート（現在はサブツリー）までの距離が測定されていました。ここで、ルートノードに対してもう1つのステップを実行する必要があります。つまり、すべての距離が1つ増加します。

したがって、ルートノードからの子孫があり、それらはすべてルートから1つ離れているN - 1ため、を追加します。N - 11*(N-1) = N-1

---

パスの長さはいくつかの方法で簡単に計算できます。エッジまたはノードのいずれかを数えることができます。

ノードのカウント

             A        Level 0
           /   \      
          B     C     Level 1
         / \   / \
        D   E F   G   Level 2

パスの長さは0から始めます。

• ノードAはルートであり、常にレベル0にあります。パスの長さには影響しません。（それに到達するためにパスをたどる必要はないので、0）
  • 0 + (0) = 0
• レベル1には、次の2つのノードがBありCます。
  • 0 + (1 + 1) = 2
• レベル2には、次の4つのノードがD, E, FありGます。
  • 2 + (2 + 2 + 2 + 2) = 10

エッジを数える

             A        
           /   \      Level 1
          B     C     
         / \   / \    Level 2
        D   E F   G

• 0、最初の合計
• + 1*2レベル1には、2エッジがあります
• + 2*4レベル2には、4エッジがあります

定義を数学に変換する

ツリーのパス長を計算するための便利な方法は、すべてのkについて、kとレベルkのノードの数の積を合計することです。

L _iがレベル上のノードのセットをi示しh、高さ、つまりノードからルートまでの最大距離を示すとします。

Answer 2

             A
           /   \
          B     C
         / \   / \
        D   E F   G

ここで、N = 総数 ツリー内のノード数 = 7

(リーフ ノードのパス長はゼロと見なされます。)

ACC。再帰的な定義へ:

Path length of tree = Path length with Root A
                    = Path length with Root B + Path length with Root C + (7-1)

                    = (Path length with Root D + Path length with Root E + (3-1))
                    + (Path length with Root F + Path length with Root G + (3-1))
                    + (7-1)

                    = ((0 + 0 + 2) + (0 + 0 + 2)) + 6
                    = 10

その実装は次のようになります。

int Recurse(Node root, int totalNodes)
{
    if (totalNodes == 1)
        return 0;
    int noOfNodes1 = CountNodes(root.left);
    int noOfNodes2 = CountNodes(root.right);
    return ( Recurse(root.left, noOfNodes1)
           + Recurse(root.right, noOfNodes2) + totalNodes - 1);
}