问金字塔/树数据结构c++/c#

EN

与其实际将其存储在基于树的结构中，如果树总是平衡的(例如在您的示例中)，那么使用锯齿数组可能会更好：

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]

当涉及到实际查找最大路径时，您可以使用backtracker。可能有一些方法可以修剪路径，但如果你使用backtracker，你应该知道它具有指数级的运行时复杂性(这意味着它不能很好地伸缩)。虽然你可以做一些比其他的更好的回溯算法，但我不确定你是否能够找到一个在一般情况下比O(2^n)更好的算法。

如果你在谈论二叉树或AVL树，它是这样的：

类型定义结构节点{整数值；节点*右；节点*左；BOOL命中；}TypeNode；

顺便说一句，既然你正在寻找最高的和，你可以这样做：

类型定义f结构节点{ int value；node* right；node* left；BOOL命中；} 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(TypeNode，"")；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(字符串，itoa(aux->值))；strcat(字符串，"-")；}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->值；strcat(str，itoa(aux->value))；strcat(str，"-")；}else{ sum+=aux->right->value；aux->right->hit=true；strcat(str，itoa(aux->value))；strcat(str，"-")；中断；}}否则{ 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，"-")；中断；}否则{ aux->hit=true；sum+=aux->value；strcat(字符串，itoa(aux->value))；strcat(str，"-")；break；}} return sum；} int main{ TypeNode *root=new TypeNode；int sum=0；int highestsum=0；char sumpath100；do{ sum=getSum(根，总路径)；if(sum>highestsum){ highestsum=sum；}}while(sum=getSum！=0)；printf(“路径：%s，总和：%d"，总路径，最高和)；}

刚做好，不确定它是否正常工作，在那里测试，如果它不工作，报告

我脑海中浮现的数据结构类(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值。