Блог

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

Моя функция для создания двоичного дерева:

 typedef struct myTree _node;

   

void INSERT(_node *(*tree), _node *item) { 
                    
     if (!(*tree)) {
          *tree = item;
          return;
     }
            
     if (item->val < (*tree)->val) {
          INSERT(amp;(*tree)->left, item);
     }
            
     else if (item->val > (*tree)->val) {
          INSERT(amp;(*tree)->right);
     }
 }
  

Моя основная функция:

 int main(void) {

int i;
int *balanced;

_node *current, *root;
            
    root = NULL;
    
    for (i = 0; i < size; i  ) {
        
        current = (_node *)malloc(sizeof(_node));
        current->left = current->right = NULL;
        current->val = balanced[i];
        INSERT(amp;root, current);
    }
    
return 0;
}
  

Я опустил части своей основной функции для простоты.

Идея в том, что я хочу распечатать содержимое дерева в порядке pre, in и post, а также просмотреть связанный список и распечатать значение узла в дереве, на которое указывает каждый узел связанного списка.

Я изучаю C всего несколько месяцев, поэтому я не очень продвинут.

Подобно тому, как ваша функция insert рекурсивна по дереву, перемещение по дереву также рекурсивно. Есть два способа сделать это: конкретный способ и общий способ. Давайте посмотрим оба.

Конкретный способ просто выводит значения по мере их обнаружения. Это решает эту конкретную проблему: печать значений. Если вам нужно выполнить обход дерева, чтобы сделать более одной вещи, вам придется копировать код, что, как правило, плохо.
С другой стороны, код намного проще и понятнее. Давайте рассмотрим случай по порядку (вы можете сделать два других самостоятельно; они очень похожи):

 void print_in_order (const struct myTree * tree) {
  // if we're in a null node, do nothing
  if (!tree) return;
  // otherwise, do the left subtree, then the current node, then the right subtree
  // non-existent subtrees will be handled by the above check, so don't check twice
  print_in_order(tree -> left);
  printf("%dn", tree -> val);
  print_in_order(tree -> right);
}
  

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

 void print_node (const struct myTree * node) {
  printf("%dn", node -> val);
}
  

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

 void apply_in_order (const struct myTree * tree,
                     void (* callback)(const struct myTree *)) {
  // this is the same as before...
  if (!tree) return;
  apply_in_order(tree -> left, callback);
  // ...except that, instead of doing a specific thing, we call the callback on each node
  callback(tree);
  apply_in_order(tree -> right, callback);
}
  

Теперь вы просто вызываете эту функцию as apply_in_order(tree, print_node); и получаете то же поведение, что и выше. Но в следующий раз, когда вам нужно будет написать функцию, которая обходит дерево, вам понадобится только для каждого узла; остальное уже сделано.