1

1) 不均衡二分木という用語は何を意味し、それをテストするアルゴリズムをどのように書くことができますか?

2) 二分木の深さをテストする関数を書くように求める問題があります。これでうまくいくと思いますが、よくわかりません....:

function getDepth(Node n){
    if(node == null){
        return 0;
    }
    return 1 + Math.max(getDepth(node.left), getDepth(node.right));
}
getDepth(root);

誰でも私にポインタを与えることができます...

4

2 に答える 2

0

歪んだ二分木は、1 種類の部分木しか持たない木です。ツリーがサブ ツリーのみを残した場合、それは歪んだツリーのままになり、その逆も同様です。

于 2015-06-13T16:43:39.507 に答える
0

1) スキュー バイナリ ツリーは、100% 広く普及している一般的な用語ではありません (Google でさえ混乱します)。講義ノートや本を検索して、その意味を確認してください。

  1. ツリーにノードと同じ数のレベルがあるかどうかをテストするには、レベルをカウントする既に持っている関数と、ノードの数をカウントする別の関数を使用できます。

    ただし、ノードの数がレベルの数と同じではないことがわかった場合は、より効率的な別のアルゴリズムを作成する必要があります。

  2. 深さ関数は正しいです。結局のところ、これは木の深さの定義から直接取られているのではないでしょうか?

    （唯一の可能なニックピックは深さ（null）= 1です。代わりに深さ（null）= 0が必要ないことを確認してください）

于 2011-04-27T17:24:05.363 に答える