我需要一个数据结构，它以这样一种方式存储整数，即每个数字都连接到紧接在其下方的两个（或更多）相邻的数字，例如
1
/ \
3 2
/ \ / \
5 6 4
/ \ / \ / \
7 9 8 10
然后需要找到从根到底部基行的任何下降路径的最大和，例如，在上面显示的数据中，1-3-6-9 将是最大和为 19 的路径。
一个节点可能连接到两个以上的子节点。
我试图实现一个 C# 树类，但不能完全弄清楚如何正确添加孩子，所以只是想知道是否真的需要有一个树结构并创建一个算法来有效地找到最大和。这是代码：http: //ideone.com/GeH36c
在语言方面，C# 和 C++ 都可以。
(If you want to learn, read the comments from the code ;) )
You could also try using linked lists in C++. You can create a struct like this:
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)
{}
};
Then you create a "MyNumber" that will be the top of the pyramid, and a list of "MyNumber" that will represent the bottom of the pyramid:
#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;
After that you create a function wich adds new levels to the pyramid:
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)
}
}
Next you add the numbers to the pyramid using the function:
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);
...
Finally you can get the maximum sum by this way:
#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;
}
You can improve this code a lot. Probably it is easier to make it in C# but I don't use it :(
There may be some errors in the code, I didn't test it :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最大总和的值。
我现在无法访问编译器，所以下面的代码可能有一些错误。我认为它说明了一般原则（使用递归）。我会尽快尝试运行它并修复任何错误。
#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;
};
如果树总是平衡的（例如在您的示例中），则与其实际将其存储在基于树的结构中，不如只使用锯齿状数组：
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) 更好的算法。
如果您在谈论二叉树或 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); }
刚刚成功，不确定它是否工作，在那里测试，如果它不工作，请报告