3

これは私の研究コードの問題であり、これを行うための効率的な方法は何だろうと思っています。不必要な詳細は省略し、問題の核心を理解できるように提示しています。

各ノードに数字を持つ二分木があるとしましょう。ルートからリーフまで、ツリー内のすべてのブランチの最小合計を見つけたいと考えています。以下は非常に大まかな擬似コードです。

int minimum(tree){
   // Some base cases
   left_min = minimum(tree->left);
   right_min= minimum(tree->right);
   if (left_min < right_min){
      return current_value + left_min;
   }
   else{
      return current_value + right_min;
   }
}

これから、最小値を計算できます。ただし、最小値を与えるノードを計算したい場合は、どうすればよいでしょうか? つまり、答えが 14 の場合、ツリーの各レベルのどのノードを合計すると 14 になるかを調べたいのです。既存の関数に最小限の変更を加えてこれを行う効率的な方法は何でしょうか? 最小限の変更とは、ブランチを追跡するために変数を追加することはできますが、関数を完全に書き直すことはできないということです。

ありがとう

4

2 に答える 2

3

ベクトルの代わりにリスト、スタック、またはキューを使用できます。

typedef vector<yourIdType> idvec;

int minimum(tree, idvec &path){
   // Some base cases
   idvec leftPath, rightPath;
   left_min = minimum(tree->left, leftPath);
   right_min= minimum(tree->right, rightPath);
   if (left_min < right_min){
      swap(path, leftPath);
      path.push_back(thisNodeId);
      return current_value + left_min;
   } else {
      swap(path, rightPath);
      path.push_back(thisNodeId);
      return current_value + right_min;
   }
}
于 2012-07-19T03:37:37.240 に答える
2

リスト/キューを追加の引数として使用して、選択したノードを追跡できます。

int minimum(tree, list){
   List templeft, tempright;
   // Some base cases
   left_min = minimum(tree->left, templeft);
   right_min= minimum(tree->right, tempright);
   if (left_min < right_min){
      list.push_back(templeft);
      list.push_back(current);
      return current_value + left_min;
   }
   else{
      list.push_back(tempright);
      list.push_back(current);
      return current_value + right_min;
   }
}
于 2012-07-19T03:25:00.233 に答える