Как вставить узлы в дерево в C справа налево?

Question

Теперь я понимаю, что код ниже работает только для root и его дочерних элементов, но я не знаю, как его расширить. У каждого узла должны быть дети, прежде чем передавать «внукам». Спасибо.

void insert_node(IndexTree **root, Node *node) { 
    IndexTree *temp = (IndexTree*)malloc(sizeof(IndexTree)); 
    memcpy(&temp->value.cs, node, sizeof(Node)); 
    temp->left = NULL; 
    temp->right = NULL; 
    temp->tip=1; 

if ((*root) == NULL) { 
    *root = temp; 
    (*root)->left = NULL; 
    (*root)->right = NULL; 
} 
else { 
    while (1) { 
     if ((*root)->right == NULL) { 
      (*root)->right = temp; 
      break; 
     } 
     else if ((*root)->left == NULL) { 
      (*root)->left = temp; 
      break; 
     } 
    } 
} 

Answer 1

Использование рекурсивных функций.

Деревья - это рекурсивные типы данных (https://en.wikipedia.org/wiki/Recursive_data_type). В них каждый узел является корнем собственного дерева. Попытка работать с ними с помощью вложенных if s и while s просто ограничивает вас глубиной дерева.

Рассматривайте следующие функции: void print_tree(IndexTree* root). Реализация, которая идет по всем значениям дерев делает следующее:

void print_tree(IndexTree* root) 
{ 
     if (root == NULL) return; // do NOT try to display a non-existent tree 

     print_tree(root->right); 
     printf("%d\n", root->tip); 
     print_tree(root->left); 
} 

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

Что касается вставки, само решение аналогично печати дерева:

void insert_value(IndexTree* root, int v) 
{ 
    if (v > root->tip) { 
     if (root->right != NULL) { 
      insert_value(root->right, v); 
     } else { 
      // create node at root->right 
     } 
    } else { 
     // same as above except with root->left 
    } 
} 

Answer 2

Это может быть интересно программирование вопрос, чтобы создать полное бинарное дерево, используя связанное представление. Здесь Linked означает представление без массива, где левый и правый указатели (или ссылки) используются для обозначения левого и правого детей соответственно. Как написать функцию вставки, которая всегда добавляет новый узел на последнем уровне и в крайнем левом доступном положении? Чтобы создать связанное полное двоичное дерево, нам нужно отслеживать узлы в порядке порядка уровня, чтобы следующий узел был вставлен в крайнее левое положение. Структуру данных очереди можно использовать для отслеживания вставленных узлов.
Ниже приведены шаги по вставке нового узла в полное двоичное дерево. (Правый sckewed)
1. If the tree is empty, initialize the root with new node.

2. Else, get the front node of the queue.

……. if the right child of this front node doesn’t exist, set the right child as the new node. //as per your case
…….else If the left child of this front node doesn’t exist, set the left child as the new node.

3. If the front node has both the left child and right child, Dequeue() it.

4. Enqueue() the new node.