Двоичный поиск Дерево Вставка C без рекурсии

Question

Я новичок на странице, и я действительно зациклился на домашнем задании моего университета, чтобы воссоздать функцию, которая вставляет узлы в дерево без рекурсии. Мне был дан рекурсивный метод, и мне нужно преобразовать его в Iterative. Это дано Рекурсивный Код:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else if (newnode->entry < root->entry) 
    { 
     root->left = InsertTree(root->left, newnode); 
    } 
    else 
    { 
     root->right = InsertTree(root->right, newnode); 
    } 
    return root; 
} 

, и я сделал это один:

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode) 
{ 
    if (!root) 
    { 
     root = newnode; 
     root->left = root->right=NULL; 
    } 
    else 
    { 
     TreeNode * temp = root, *prev = NULL; 

     while(temp) 
     { 
     if (temp->entry < newnode->entry) 
      temp = temp->right; 
     else 
      temp = temp->left; 
     } 
     newnode; 
     temp->left = temp->right = NULL; 
    } 
    return root; 
} 

он работает в течение первых элементов, но не сохраняет элементы отдыха. Любые идеи? Заранее спасибо

Answer 1

The (ип) использование prev указывает на осознание того, что рекурсивные результаты должны быть заделаны. Как уже принято решение другими, здесь «идеальное» решение, используя псевдонимы указателей.

TreeNode **current = &root; 
    while (*current) 
    { 
     if (newnode->entry < (*current)->entry) 
     { 
      current = &(*current)->left; 
     } 
     else 
     { 
      current = &(*current)->right; 
     } 
    } 
    *current = newnode; 
    newnode->left = newnode->right = NULL; 
    return root; 

Ток будет в конце точки к корню или слева/справа от узла; являющийся нулевым.

Обратите внимание, что это использование псевдонимов не существует на некоторых других языках, таких как java. Одно из немногих преимуществ C.

Префикс-оператор & принимает адрес переменной.

Answer 2

Это код для вставки элемента итеративно. Поскольку новый элемент для вставки уже создан/выделен, нет смысла не инициализировать левое/правое поле структуры, как только элемент будет создан.

TreeNode *InsertTree(TreeNode *root, TreeNode *newnode){ 

     //assuming newnode->left/right already == NULL 
     if(root==NULL){ 
      root = newnode; 
     } 
     else { 
      TreeNode * prev = NULL; 
      TreeNode * curr = root; 
      while(curr != NULL){ 
       prev = curr; 
       if(curr -> entry < newnode -> entry) curr = curr -> right; 
       else curr = curr -> left; 
      } 
      if (prev -> entry < newnode -> entry) prev -> right = newnode; 
      else prev -> left = newnode; 

     } 
     return root; 
    }