C ++ - Проблемы с пониманием рекурсивной функции двоичного дерева (вставка) - PullRequest
Новая
       74

C ++ - Проблемы с пониманием рекурсивной функции двоичного дерева (вставка)

0 голосов
/ 24 февраля 2020

У меня есть двоичное дерево, которое выглядит следующим образом 

struct Node 
{
  int key;
  double data;
  Node* right;
  Node* left;
};

, и у меня есть эта функция "вставки" для вставки новых узлов и построения дерева 

void insert(Node*& p, int key, double to_be_inserted) 
{
  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }
  else 
  {
    if (p->key == key) 
    {
      p->data = to_be_inserted;
    }
    else 
    {
      Node*& newChild = (p->key > key) ? p->left : p->right;
      insert(newChild, key, to_be_inserted);
    }
  }
}

и основная функция это выглядит так 

int main(int argc, char ** argv) 
{
  Node* root = nullptr;
  insert(root, 11, 11);
  insert(root, 6, 6);
  insert(root, 4, 4);
  insert(root, 5, 5);
  insert(root, 8, 8);
  insert(root, 10, 10);
  insert(root, 19, 19);
  insert(root, 17, 17);
  insert(root, 43, 43);
  insert(root, 31, 31);
  insert(root, 49, 49);

  printTree(root, 0);
  return 0;
}

Окончательное «распечатанное» дерево выглядит так:

enter image description here

(This) print- out "предназначен для чтения слева направо, а не сверху вниз)

Чего я не понимаю, так это ... когда функция insert решает вернуться назад (go создает резервную копию дерево) и построить правильное поддерево?

Например, если мы посмотрим на insert(root, 5, 5) и insert(root, 8, 8) в main, почему 8 оказывается дочерним узлом node 6 вместо node 5. Согласно логике c функции insert, она должна просто идти вниз по дереву и делать 8 дочерним узлом node 5 ... верно?

Мне нужна помощь должным образом понимание функции вставки. Я уверен, что я что-то неправильно понимаю в его логике c.

Спасибо (и простите за длинный пост)!

1 Ответ

1 голос
/ 24 февраля 2020

К тому времени, когда вы вставляете 8, три выглядят так (X означает NULL): 

insert(root, 11, 11);
insert(root, 6, 6);
insert(root, 4, 4);
insert(root, 5, 5);

        11
    6         X
 4    X    X     X
   5

Теперь, когда вы пытаетесь вставить 8 (в этой строке Node*& newChild = (p->key > key) ? p->left : p->right; вы сначала проверяете если 11 > 8, что верно, и, следовательно, эта строка говорит вам, что вы сейчас пытаетесь вставить 8 в левого дочернего элемента 11, который, как оказалось, имеет корни в 6.

В этот момент функция вставки повторяется, но на этот раз root из трех не является 11, а 6. 8 больше, чем 6, и, таким образом, идет с правой стороны. из 6.

Таким образом, это ситуация до и после вставки 8. 


        11                             11                
    6         X                    6         X           
 4    X    X     X   =====>     4    8    X     X        
   5                             5

Кстати, в этой функции есть возврат. Это простая рекурсивная функция.

...