Блог

Я пытаюсь написать двоичное дерево на c , связанный список в качестве поддеревьев и уникальные указатели в качестве соединений между этими списками.Все дерево разделено на две части: правую и левую. Есть два указателя, которые ссылаются из заголовка на левый и на правый листы. Тогда каждый лист в поддереве представляет собой структуру, в которой хранится следующая информация :

 class Leaf{
private:
    int * leaf_value; 
    int occupancy;
    std::unique_ptr<Leaf> NextLeaf;

public:
    explicit Leaf(int);
    void AppendLeaf(int,std::unique_ptr<Leaf>);

};

Leaf::Leaf(int size) {
    leaf_value = new int (size);
    NextLeaf = nullptr;
    occupancy = 0;
}
  

Где leaf_value — это указатель на память, в которой будут храниться все числа на этом уровне.(поскольку это двоичное дерево, мы можем знать точный размер ( 2 ^ current_level ), который должен быть выделен для объектов). Итак, мы будем заполнять это свободное пространство числами до тех пор, пока заполняемость не станет меньше 2 ^ current_level .И после этого мы добавим новый, более глубокий уровень для следующей строки элементов.
Структура будет выглядеть следующим образом:

                1
            /        
         [2]         [ 3 ]
        /              
   [4 , 5 ,6 ,7]  [8 , 9 , 10 , 11 ]
  

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

 
int main(){
     Node head;
     head.next = nullptr;
     int value;
     cin << value;
     AddNode(value , head); 
     return 0;
}

/*TreeHead - is another leaf structure that stores pointers to left and right branches 
struct SmartTree{
    int level;
    std::unique_ptr<Leaf> LeftChild = std::make_unique<Leaf>(1);
    std::unique_ptr<Leaf> RightChild = std::make_unique<Leaf>(1);

}
*/
void AddNode(int val , std::unique_ptr<SmartTree> TreeHead){
/*problem with implemantation of this part */
     Node * currentLeaf  = TreeHead;
     Node * previousLeaf = TreeHead;
     while(current != nullptr){
        previousLeaf = currentLeaf;
        currentLeaf = currentLeaf -> next ;
     }
     currentLeaf = new Leaf;
     previous -> next = currentLeaf;
     currentLeaf -> value = val; 
}
  

Но проблема в том, что я не могу найти правильный способ пройти через все наименьшие значения до нижнего, из-за уникальности уникальных указателей.Я не уверен, что смогу сделать это с помощью move(pointer) функции, потому что, как я понял, функции работают так, что предоставляют право собственности от TreeHead до CurrentLeafe , значение, сохраненное в, может быть потеряно.
Итак, вопрос в том :
Есть ли способ пройти через уникальные указатели или я должен использовать другой вид указателей для выполнения этой задачи?
Большое вам спасибо!

Я немного изменил свои методы, изменив leafs массива [ 1 2 3 ] на normal . Это означает, что теперь каждый лист является объектом, который содержит один элемент, поэтому дерево выглядит теперь не так :

                 1
            /        
         [2]         [ 3 ]
        /              
   [4 , 5 ,6 ,7]  [8 , 9 , 10 , 11 ]
  

но как :

                1
           /       
          2           3
        /          /   
       5      6    7     8 
  

Новая древовидная структура :

 struct SmartTree {
    int value;
    int childrens;
    bool is_root = false;
    std::unique_ptr<SmartTree> LeftChild;
    std::unique_ptr<SmartTree> RightChild;
};

  

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

 std::unique_ptr <SmartTree> InsertLeftChild(std::unique_ptr<SmartTree> tree, std::unique_ptr<SmartTree> left_subtree){
    // left_subtree - node to insert
    tree -> childrens  = 1;
    if (tree -> is_root and  tree -> LeftChild == nullptr) tree -> LeftChild = std::move(left_subtree);
    else if (tree -> is_root) tree -> LeftChild = InsertLeftChild(std::move(tree -> LeftChild) , move(left_subtree));
    else if (tree -> LeftChild == nullptr)tree -> LeftChild = std::move(left_subtree);
    else if (tree -> RightChild == nullptr) tree -> RightChild = std::move(left_subtree);
    else if (tree -> LeftChild -> childrens <= tree -> RightChild -> childrens) tree->LeftChild = InsertLeftChild(std::move(tree -> LeftChild) , std::move(left_subtree));
    else if (tree -> LeftChild -> childrens > tree -> RightChild -> childrens)  tree->RightChild = InsertLeftChild(std::move(tree -> RightChild) , std::move(left_subtree));
    return move(tree);
};
  

Этот записывается только для вставки левых дочерних элементов . Итак, первая и вторая if проверки, является ли это root и инициализируется ли этот root . Если у него есть дочерние элементы, тогда вызовите функцию InsertLeftChilld . Передача аргументов для функции с move уничтожит предыдущий указатель, поэтому с левой стороны я возвращаю права собственности на leftChild :

 tree -> LeftChild = std::move(left_subtree);

  

else if (tree -> LeftChild == nullptr) проверяет, является ли это концом, и если это так — вставляет новый лист

else if (tree -> LeftChild -> childrens <= tree -> RightChild -> childrens) проверяет, куда вы должны направить свой лист дальше, на случай, если это не уровень, на котором вы можете его вставить. Надеюсь, этот метод может помочь кому-нибудь в будущем.Спасибо всем за ответы!