Дерево с 3 детьми

Question

Это вопрос типа структуры данных. У меня проблема с деревом. Я хочу, чтобы пользователь вводил свое имя. «DAN» теперь я хочу сделать дерево для этого с корневым узлом, имеющим трех детей. У меня есть дерево с тремя детьми.

как я реализую его со связанным списком. потому что в бинарном древовидном списке есть двое детей.

но здесь у меня есть три. просто в том, что у меня есть корневой узел, имеющий троих детей

   root 
       /| \ 
      /| \ 
      ch1 ch2 ch3 

Answer 1

Простой, создать структуру с тремя детьми указателей:

struct TreeNode 
{ 
    int data; 
    TreeNode *children[3]; 
}; 

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

struct TreeNode 
{ 
    int data; 
    TreeNode *firstChild; 
    TreeNode *nextSibling; 
}; 

// To iterate through the children of a node: 
TreeNode *child = root->firstChild; 
while (child != NULL) 
{ 
    // Do stuff with child 
    ... 
    child = child->nextSibling; 
} 

Это простирается более легко с любым количеством детей, но она имеет более высокую производительность ре при доступе к данным. Поэтому, если вы знаете, что у каждого узла будет не более 3 детей, лучше использовать фиксированный массив дочерних указателей, чтобы улучшить время доступа и улучшить локальность кэша.