ツリー内のリーフノードを数えよう

Question

すべてのノードに送信ノードの事前決定セットがあるツリーがあるとします。レベル値が与えられたリーフノードの数を数えるための高速化/最適化を考え出すことは可能でしょうか？もし誰かが同じことをするためのアイデアやリンクやリソースを提案できれば素晴らしいだろう。

Answer 1

いいえ、あなたはまだツリー全体を走査する必要があります。ツリーの各ノードの子ノードの数だけから、正確な構造を予測する方法やそれを近似する方法はありません。

それ以外は、カウンタを保持して、挿入するたびに更新してください。より簡単で、葉の数をカウントすることを除いて、時間演算の複雑さは変わらないでしょう。これはO(1)に縮小されます。

Answer 2

これは実際にはかなり厳しいものになる可能性があります。プログラミング言語の種類が異なるので、入力データ構造はツリーのバイナリまたは一般ツリー（任意の数の子）、ツリーのサイズです。

最も一般的な考え方は、ルートから始めてDFSまたはBFSを実行してすべてのノードレベルを取得し、各セットに単一レベルのノードが含まれるセットのリストを作成することです。セットは任意の構造にすることができます、標準的なリストは上手です。

パフォーマンスが必要な場合（Cより優れていても）、C++で作業しているとしましょう。

あなたが言及したように、一般的なツリーを持ち、入力構造が隣接リストであるとします。

//nodes are numbered from zero to N-1 
vector<vector<int>> adjList; 

次に、BFSまたはDFSのいずれかを実行します。いずれかの方法でツリーを作成し、各ノードのレベルを維持します。次のノードのレベルは、その親のレベルに1を加えたレベルです。

レベルを検出すると、ノードをこのように配置します。

vector<vector<int>> nodesPartitionedByLevels(nodeCount); 
//run bfs here 
//inside it you call 
nodesPartitionedByLevels[level].push_back(node) 

これはそれです。

レベルがある場合は、そのレベルのすべてのノードを反復し、任意のノードを競合する場合は隣接リストをチェックします。

adjList[node].empty()を基本的に呼び出します。それよりも真の場合はリーフノードです。