Двоичное представление N-арного дерева

Question

В настоящее время я пытаюсь создать древовидную структуру с узлами, имеющими неизвестное количество детей, но мне также необходимо отслеживать родительские узлы. Я посмотрел на этот вопрос N-ary trees in C и сделал структуру, аналогичную структуре сообщили в ссылке:

template <class T> 
struct treeNode { 

public: 

T * data; 
treeNode *parent; 
treeNode *kids; //left 
treeNode *siblings; //right 


treeNode(); 
~treeNode(); 
treeNode(T data); 
void treeInsert(T newItem); 



}; 

Он говорит, что, делая дерево таким образом, это делает некоторые алгоритмы проще кода. Тем не менее, мне сложно определить, как я буду создавать методы insert() и search() для этой структуры, видя, что мне нужно отслеживать родительские узлы. Есть ли какие-либо предложения относительно того, как я могу это сделать?

EDIT:

Вот мой метод вставки():

template<class T> 
bool NewTree<T>::insert(T *data, treeNode<T> * parent) 
{ 
if(this->root == NULL) 
{ 
    this->root = new treeNode<T>(); 
    this->root->data = data; 
    this->root->parent = NULL; 
    this->root->children = NULL; 
} 
else 
{ 
    treeNode temp = new treenode<T>(); 
    temp.data = data; 
    temp.parent = parent; 
    parent->children->siblings = temp; // add node to siblings of parent's children 
    parent->children = temp; // add node to children of parent 

} 

} 

ли это выглядеть правильно?

Answer 1

С любой древовидной структурой поиск будет использовать относительно тот же алгоритм (рекурсия глубины, если она несортирована, или простой поиск по дереву, если отсортировано (например, дерево двоичного поиска)). Когда вы вставляете, все, что вам нужно сделать, это назначить родительскому элементу нового узла. Затем назначьте новый узел .parent.child[1] новому узлу (таким образом, связав родителя с дочерним элементом). Затем проверьте других дочерних элементов родительского узла, чтобы назначить братьев и сестер вашего нового узла (если они есть).

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

(узел-источник):

class Node { 
    // generic data store 
    public int data; 
    public Node parent; 
    public Node siblings; 
    public Node children; 
} 

(исходное дерево):

class NewTree { 
    // current node 
    public Node current; 
    // pointer to root node 
    public Node root; 

    // constructor here 
    // create new node 
    public boolean insert(int data) { 
    // search for the node which is immediately BEFORE where the new node should go 
    // remember that with duplicate data values, we can just put the new node in 
    // front of the chain of siblings 
    Node neighbor = this.search(data); 
    // if we've found the node our new node should follow, create it with the 
    // found node as parent, otherwise we are creating the root node 
    // so if we're creating the root node, we simply create it and then set its 
    // children, siblings, and parent to null 
    // i think this is the part you're having trouble with, so look below for a 
    // diagram for visual aid 
    } 

    public Node search(int target) { 
    // basically we just iterate through the chain of siblings and/or children 
    // until this.current.children is null or this.current.siblings is null 
    // we need to make certain that we also search the children of 
    // this.index.sibling that may exist (depth-first recursive search) 
    } 
} 

Когда мы находим место (с помощью поиска()), где о ur новый узел должен идти, нам нужно переназначить родительские, дочерние и братья и сестры «ссылки» внутри нового узла своим новым родителям, детям и братьям и сестрам. Например, мы принимаем это:

A-| 
| 
B-C-| 
| | 
| F-G-| 
| | 
| - 
| 
D-E-| 
| | 
- H-| 
    | 
    - 

И мы вставим новый узел (X), где F. Это просто для иллюстрации того, как мы переназначаем каждую из ссылок нового узла. Эти более мелкие детали могут немного отличаться, но, что важно, вот пример реализации переназначения ссылки:

A-| 
| 
B-C-| 
| | 
| X-F-G-| 
| | | 
| - - 
| 
D-E-| 
| | 
- H-| 
    | 
    - 

Что мы делаем: 1) Создание X. 2) Назначить x.parent -с. 3) Перенесите c.children в x. 4) Назначьте x.siblings f. Это вставляет новый узел (помните, что вставка отличается от сортировки, и ваше дерево может потребоваться, если вы явно требуют определенного заказа).