12

たとえば、次の関数でかなり大きなツリーをトラバーサルしている場合、スタック オーバーフローが発生する可能性があります。

void inorder(node* n)
{
  if(n == null) return;
  inorder(n->l);
  n->print();
  inorder(n->r); 
}

このようなオーバーフローの発生を防ぐために、関数に条件または何かを追加する方法は?

4

7 に答える 7

6

それが本当に懸念される場合は、再帰よりも反復を検討してください。

http://en.wikipedia.org/wiki/Tree_traversal

反復のための擬似コードを参照してください iterativeInorder iterativePreorder iterativePostorder

基本的に、独自のリストを while ループ内のスタック データ構造として使用します。関数の再帰を効果的に置き換えることができます。

于 2013-07-01T05:12:39.380 に答える
1

非常に大きなツリーがあり、再帰トラバーサルを使用してスタックをオーバーランさせるという問題が発生している場合、問題はバランスの取れたツリーを持っていない可能性があります。最初の提案は、赤黒ツリーや AVL ツリーなどのバランスの取れたバイナリ ツリー、または B+ ツリーなどのノードごとに 2 つ以上の子を持つツリーを試すことです。C++ ライブラリが提供するstd::map<>およびstd::set<>これらは通常、バランス ツリーを使用して実装されます。

ただし、再帰的な順序通りのトラバーサルを回避する簡単な方法の 1 つは、ツリーをスレッド化するように変更することです。つまり、リーフ ノードの右ポインタを使用して、次のノードを示します。このようなツリーの走査は、次のようになります。

n = find_first(n);
while (! is_null(n)) {
    n->print();
    if (n->is_leaf()) n = n->r;
    else n = find_first(n->r);
}
于 2013-07-01T06:15:58.533 に答える
1

再帰に関する問題は、メモリの (最小) サイズと入力の (最大) サイズの両方に何らかの境界を設定できない限り、スタックがオーバーフローしないことを保証できないことです。ただし、できることは、無限ループがある場合にスタックがオーバーフローすることを保証することです...

「if() return;」が表示されます 終了条件であるため、ツリーのすべてのブランチが null で終了する限り、無限ループを避ける必要があります。したがって、1 つの可能性は、ツリーの一部のブランチが null に到達しない不正な入力です。(これは、たとえば、ツリー データ構造にループがある場合に発生します。)

他に考えられる唯一の可能性は、使用可能なスタック メモリの量に対してツリー データ構造が大きすぎるということです。(NB これは仮想メモリであり、スワップ領域を使用できるため、必ずしも RAM が不足しているという問題ではありません。) その場合は、再帰的ではない他のアルゴリズム的アプローチを考え出す必要があるかもしれません。関数のメモリ使用量は小さいため、関数が行う追加の処理を省略しない限り、これが問題になるには、ツリーが本当に深くなければなりません。(注: ここで問題になるのは最大深度であり、ノードの総数ではありません。)

于 2013-07-01T04:59:24.730 に答える
1

OS のスタック サイズを増やすことができます。これは通常ulimit、Unix ライクな環境を使用している場合に構成されます。

たとえば、Linuxではulimit -s unlimitedスタックのサイズを「無制限」に設定できますが、IIRCにはハード制限があり、メモリ全体を1つのプロセス専用にすることはできません（ただし、以下のリンクの回答の1つは無制限に言及しています） .

私の提案はulimit -s、スタックの現在のサイズを取得する実行することです。それでもスタックオーバーフローが発生する場合は、満足するまでその制限を2倍にします。

スタックのサイズとその更新方法に関する詳細な説明については、こちら、こちら、およびこちらをご覧ください。

于 2013-07-01T05:19:10.683 に答える
0

別の int 変数を再帰関数に関連付けることによって行うことができる変更の小さなプロトタイプ。ルートでデフォルトでゼロ値から始まる関数に変数を引数として渡し、ツリーを下るにつれて減少させることができます。 ..

欠点: このソリューションには、すべてのノードに割り当てられる int 変数のオーバーヘッドが伴います。

void inorder(node* n,int counter)
{
 if(counter<limit) //limit specified as per system limit
 {
  if(n == null) return;
  inorder(n->l,counter-1);
  n->print();
  inorder(n->r,counter-1);
 }
 else
  n->print();
}

さらなる調査を検討してください: 再帰のみを考慮する場合、トラバーサルに問題はないかもしれませんが。また、ツリーの作成と更新を改善することで回避できます。まだ考慮されていない場合は、バランス ツリーの概念を確認してください。

于 2013-07-01T06:54:57.047 に答える
0

関数が呼び出された時間を追跡するために、静的変数を追加できます。システムがクラッシュすると思われる状態に近づいている場合は、何らかのルーチンを実行してユーザーにエラーを通知します。

于 2013-07-01T04:40:04.553 に答える