C ++ распечатать бинарное дерево поиска

Question

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

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

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

void treenode::insert(int i)
{

   if(root == 0)
   {
      cout << "root" << endl;
      root = new node(i,root);
   }
   else
   {
      node* travel = root;
      node* prev;
      while(travel)
      {
         if(travel->value > i)
         {
            cout << "travel left" << endl;
            prev = travel;
            travel = travel->left;
         }
         else
         {
            cout << "travel right" << endl;
            prev = travel;
            travel = travel->right;
         }
      }
      //insert
      if(prev->value > i)
      {
         cout << "left" << endl;
         prev->left = new node(i);
      }
      else
      {
         cout << "right" << endl;
         prev->right = new node(i);
      }
   }

}

void treenode::print()
{

   node* travel = root;
   while(travel)
   {
      cout << travel->value << endl;
      travel = travel->left;
   }

}

Answer 1

Вы можете использовать рекурсию (псевдокод):

prin-tree(node):
   print-tree(left-subnode) if exists
   print(node-value)
   print-tree(right-subnode) if exists
...
print(root-of-tree)

Answer 2

Все зависит от определения дерева.Если узлы не содержат указателей на родителя, вам нужно использовать стек для печати трансверсали по порядку.Самый простой способ - написать рекурсивную функцию для использования стека приложения.Алгоритм уже был показан ранее, но в основном:

in-order(node):
   in-order(node.left) if node.left not null
   process(node)
   in-order(node.right) if node.right not null

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

Answer 3

Традиционный способ CS101 для обхода двоичного дерева для выполнения каких-либо действий (печать, поиск, вставка и т. Д.) Заключается в использовании рекурсии.Пусть (независимо) подпрограмма проверит свой текущий узел, затем, если это не тот, который он ищет, вызовите себя с левым и / или правым поддеревом (если оно есть).

Для хорошегообсуждение, с psedocode, посмотрите статью в Википедии о обходе дерева .Он даже показывает, как это сделать без рекурсии, что будет соответствовать тому, как вы делали вставку.