次のように、各数値がそのすぐ下の 2 つ (またはそれ以上) の隣接する数値に接続されるように整数を格納するデータ構造が必要です。
1
/ \
3 2
/ \ / \
5 6 4
/ \ / \ / \
7 9 8 10
次に、ルートから一番下のベース行までの降順パスの最大合計を見つける必要があります。たとえば、上記のデータでは、1-3-6-9 が最大合計 19 のパスになります。
1 つのノードが 3 つ以上の子ノードに接続できる可能性があります。
私は C# ツリー クラスを実装しようとしましたが、子を正しく追加する方法がよくわかりません。そのため、ツリー structore が必要であり、最大合計を効率的に見つけるアルゴリズムを作成する必要があるかどうか疑問に思っています。そのコードは次のとおりです: http://ideone.com/GeH36c
言語的には、C#もC++もどちらでもOKです。
ツリーベースの構造に実際に格納するのではなく、ツリーが常にバランスが取れている場合（例のように）、ジャグ配列を使用する方がよい場合があります。
int[][] pyramid = new int[]
{
new[]{1}
new[]{2, 3}
new[]{5, 6, 4}
new[]{7, 9, 8, 10}
}
のアイテムの子pyramid[i][j]はpyramid[i+1][j]とpyramid[i+1][j+1]
実際に最大パスを見つける場合は、バックトラッカーを使用できます。パスを削除する方法はいくつかありますが、バックトラッカーを使用する場合は、実行時の複雑さが指数関数的になることを知っておく必要があります（つまり、拡張性が高くありません）。他よりも優れたバックトラッカーを作成することはできますが、一般的なケースでO（2 ^ n）よりも優れたアルゴリズムを見つけることができるかどうかはわかりません。
(学びたい場合は、コードのコメントを読んでください;))
C++ で連結リストを使用することもできます。次のような構造体を作成できます。
struct MyNumber{
//The number itself
int me;
//Each number has 2 derived numbers
MyNumber *childA,*childB;
//A default constructor of a number that doesn't have 'sons'
MyNumber(int me):me(me),childA(NULL),childB(NULL)
{}
};
次に、ピラミッドの最上部となる「MyNumber」と、ピラミッドの最下部を表す「MyNumber」のリストを作成します。
#include <iostream>
#include <vector>
using namespace std;
//The top of the pyramid only has 1 number. It's null because it hasn't been initiated.
MyNumber *top=NULL;
//The bottom is composed of a list of numbers
vector<MyNumber*> bottom;
その後、ピラミッドに新しいレベルを追加する関数を作成します。
void add_level(int count,int * list_of_numbers){
//if the top of the pyramid doesn't exist (is null) then initiate one
if(top==NULL)
{
//You can only add 1 number to the top. If not, there must be an error.
if(count!=1){
cout<<"Error: can't add more than one number at the top of the pyramid"<<endl;
return;
}
//You made it correctly! We will create the top with the first number of the list.
top=new Number(list_of_numbers[0]);
}
//The top is already created. We will connect numbers.
else{
//The new level to be added:
vector<MyNumber*> new_level;
//The count of the new numbers list must be 1 more than the bottom size,
//unless that the bottom size is 0: the count will be 2
if(bottom.size()==0)
if(count!=2){
cout<<"Error: the second level can only have 2 numbers"<<endl;
return;
}
else if( bottom.size()!=(count-1) ){
cout<<"Error: the new level can only have "<<bottom.size()+1<<" numbers"<<endl;
return;
}
//adding the numbers to the new level list
bool bfirst_time=true;
for(int i=0,e=0;i<count;i++)
{
MyNumber * new_number=new MyNumber(list_of_numbers[i]);
new_level.push_back(new_number);
if(bfirst_time)
{
//Setting the childA from the old bottom as the first number from the list
//Do this only 1 time
bottom[0]->childA=new_number;
bfirst_time=false;
}
else{
//The 'e' bottom number will be new number parent as well as the 'e+1'
//bottom number (every number has 2 parents except the first and last
//number from the new list)
bottom[e]->childB=new_number;
e++;
if(e<bottom.size())
bottom[e]->childA=new_number;
}
}
//connecting those numbers with their parent/s(the old bottom of the pyramid)
}
}
次に、関数を使用してピラミッドに数値を追加します。
int * list_of_numbers=new int[1];
list_of_numbers[0]=1;
//adding the top
add_level(1,list_of_numbers);
list_of_numbers=new int[2];
list_of_numbers[0]=2;
list_of_numbers[0]=3;
//adding the second level
add_level(2,list_of_numbers);
...
最後に、次の方法で最大合計を取得できます。
#include <iostream>
#include <algorithm>
using namespace std;
//the int containing the sum
int max_sum=top->me;
//a clone of the top
MyNumber * clone=top;
//same as "while you don't reach the bottom of the pyramid, continue"
while(clone->childA!=NULL && clone->childB!=NULL)
{
//add the biggest value to the max_sum variable
max_sum+=max(clone->childA->me,clone->childB->me);
//setting the clone as the biggest child
clone=(clone->childA->me > clone->childB->me)? clone->childA:clone->childB;
}
このコードを大幅に改善できます。おそらく C# で作成する方が簡単ですが、私は使用しません :(
コードにいくつかのエラーがあるかもしれません、私はそれをテストしませんでした:P
データ構造について頭に浮かぶクラス（C＃）：
class Node
{
int value;
Node parent; // You might do without this element
// Or use List<Node> parents for multiple parents;
List<Node> childs;
}
アルゴリズムに関しては、私が考えることができるのは、上から始めて、再帰関数を使用して下に進み（最初に深さ）、すべての合計を比較し、Node最大合計の値を保持することです。
バイナリ ツリーまたは AVL ツリーについて話している場合は、次のようになります。
typedef struct Node{ int value; Node *right; Node *left; BOOL hit; }TypeNode;
ところで、最高額を探しているので、次のようにできます。
typedef struct node{ int value; node* right; node* left; BOOL hit; }TypeNode; BOOL haveBrother(TypeNode *node){ if(node->right!=NULL || node->left!=NULL){ return true; } return false; } int getSum(TypeNode *root, char* str){ int sum=0; strcpy(str,""); TypeNode *aux=root; while(aux!=NULL){ if(aux->left!=NULL){ if(!aux->left->hit){ if(haveBrother(aux->left)){ aux=aux->left; sum+=aux->value; strcat(str,itoa(aux->value)); strcat(str,"-"); }else{ sum+=aux->left->value; aux->left->hit=true; strcat(str,itoa(aux->value)); strcat(str,"-"); break; } }else{ aux->left->hit=false; if(aux->right!=NULL){ if(!aux->right->hit){ if(haveBrother(aux->right)){ aux=aux->right; sum+=aux->value; strcat(str,itoa(aux->value)); strcat(str,"-"); }else{ sum+=aux->right->value; aux->right->hit=true; strcat(str,itoa(aux->value)); strcat(str,"-"); break; } }else{ aux->right->hit=false; aux->hit=true; sum+=aux->value; strcat(str,itoa(aux->value)); strcat(str,"-"); break; } }else{ aux->hit=true; sum+=aux->value; strcat(str,itoa(aux->value)); strcat(str,"-"); break; } } }else{ aux->hit=true; sum+=aux->value; strcat(str,itoa(aux->value)); strcat(str,"-"); break; } } return sum; } int main{ TypeNode *root=new TypeNode; int sum=0; int highestsum=0; char sumpath[100]; do{ sum=getSum(root,sumpath); if(sum>highestsum){ highestsum=sum; } }while(sum!=0); printf("path: %s, with total sum: %d",sumpath,highestsum); }
作成したばかりで、動作するかどうかわからない。そこでテストし、動作していない場合は報告する
現在、コンパイラにアクセスできないため、以下のコードにはエラーが含まれている可能性があります。ただし、（再帰を使用して）一般的な原則を示していると思います。できたらすぐに実行して、エラーを修正します。
#include <vector>
using namespace std;
class Node {
public:
Node() {}
Node(int val) {
this->value = val;
this->maxSumAtThisNode = 0;
this->children.push_back(NULL);
}
void addChild(Node* child) { this->children.push_back(child); }
int numChildren() { return this->children.size(); }
int getMaxSum() { return this->maxSumAtThisNode; }
void setMaxSum(int new_sum) { this->maxSumAtThisNode = new_sum; }
int getValue() { return this->value; }
Node* getChildAtIndex(int i) {return this->children[i]; }
private:
int value;
int maxSumAtThisNode;
vector<Node*> children;
};
class Tree {
public:
Tree(Node* rootNode) { this->root = rootNode; };
int findMaxSum(Node* currentNode) {
bool isLeafNode = true;
Node* child = new Node;
for (int i=0;i<(currentNode->numChildren());i++) {
child = currentNode->getChildAtIndex(i);
if (child) {
isLeafNode = false;
int theSum = currentNode->getMaxSum() + child->getValue();
if (child->getMaxSum() < theSum) {
child->setMaxSum(theSum);
}
this->findMaxSum(child);
}
}
if (isLeafNode) {this->leafNodes.push_back(currentNode); }
int maxSum = 0;
for (int j=0;j<leafNodes.size();j++) {
if (leafNodes[j]->getMaxSum() > maxSum) { maxSum = leafNodes[j]->getMaxSum(); }
}
return maxSum;
}
private:
vector<Node*> leafNodes;
Node* root;
};