пирамида/структура данных дерева C++/C#

Question

мне нужна структура данных, которая хранит целые числа таким образом, что каждый номер подключен к двум (или более) смежных непосредственно под себя, как

 1 
    /\ 
    3 2 
/\/\ 
    5 6 4 
/\/\/\ 
7 9 8 10 

И то необходимо найти максимальную сумму любых нисходящих путей от корня до нижней базовой строки, например, в данных, показанных выше, 1-3-6-9 будет путь, который имеет максимальную сумму 19.

Возможно, что один узел может подключаться к более чем двум дочерним узлам.

Я попытался реализовать класс дерева C#, но не могу точно определить, как правильно добавить детей, поэтому просто задайтесь вопросом, действительно ли нужно иметь структуру дерева и создать алгоритм для поиска max эффективно. Вот этот код: http://ideone.com/GeH36c

С точки зрения языка, C# и C++ оба в порядке.

Answer 1

Вместо того, чтобы на самом деле хранить ее в виде дерева на основе структуры, если дерево всегда уравновешивается (например, как в вашем примере), было бы лучше просто использовать зазубренный массив:

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, вы должны знать, что он имеет экспоненциальную сложность выполнения (что означает, что он недостаточно масштабируется). Хотя вы можете сделать некоторые отступники, которые лучше других, я не уверен, что вы сможете найти алгоритм, который лучше, чем O (2^n) в общем случае.

Answer 2

Если говорить о Binary Tree или AVL дерева это его:

typedef struct Node{ 

    int value; 
    Node *right; 
    Node *left; 
    BOOL hit; 

}TypeNode; 

Btw, так как вы ищете самую высокую сумму вы можете сделать это следующим образом:

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); 
} 

только что сделал, не уверен, если его работа, проверьте там, сообщите, если он не работает

Answer 3

Класс, который приходит мне в голову (C#) для структуры данных:

class Node 
{ 
    int value; 
    Node parent;   // You might do without this element 
          // Or use List<Node> parents for multiple parents; 
    List<Node> childs; 
} 

Что касается алгоритма, то, что я могу думать, начинать сверху, и с рекурсивной функцией сделать свой путь к bottom (сначала глубина), сравнивая все суммы, сохраняя значения Node для максимальной суммы.

Answer 4

(Если вы хотите узнать, прочитать комментарии из кода;))

Вы также можете попробовать использовать связанные списки в 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; 

После этого вы создаете функцию Wich добавляет новые уровни к пирамиде:

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

Answer 5

не имеют доступа к компилятор прямо сейчас, поэтому код ниже может иметь некоторые ошибки. Я думаю, что это иллюстрирует общий принцип, хотя (используя рекурсию.) Я попробую запустить его, как только смогу, и исправить любые ошибки.

#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; 
};