Печать бинарного дерева поиска

Question

Я работаю над программой Binary Tree для школы, и у меня все работает отлично. Все, над чем я сейчас работаю, это правильный вывод. Мой учитель хочет, чтобы на выходе были все числа в отсортированном порядке с запятыми после них.

Мой код, который у меня есть, прекрасно сортирует числа и печатает их, я просто не уверен, как убрать запятую после последнего номера.

Токовый выход: 1, 2, 3, 4,

Должно быть: 1, 2, 3, 4

Вот мой код:

void BinaryTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) 
            inorder(p->left);

        cout << p->data << ", ";

        if(p->right)
            inorder(p->right);
    }
    else
        return;
}

Я попробовал несколько вещей, чтобы сделать это правильно, но я просто не могу понять это.

Любая помощь будет отличной.

Спасибо.

Answer 1

Одним из простых способов является печать символа-разделителя перед данными, например

cout << ", " << p->data;

Таким образом, мы изменили вашу проблему и пропустили печать first . Это намного проще. Подсказка: для того, чтобы отслеживать, пропустить ли запятую, вам может потребоваться ввести другой аргумент функции, так как это рекурсивная функция.

Как указывает xmoex, существует более элегантный способ печати этого дерева, в результате чего получается очень читаемый и логичный код. Попробуйте найти этот способ для дополнительной задачи.

Несоответствующий намек: вы можете отбросить оператор return, поскольку он избыточен - функция все равно вернется! Как это:

void BinaryTree::inorder(tree_node* p)
{
  if (p != NULL)
  {
    // stuff goes inside here!
  }
  // no return here - the function will return anyway
}

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

Answer 2

может быть, вам нужен другой взгляд на проблему. думать об узле как
<left subtree> p->data <right subtree>

В данный момент ваши узлы печатаются как
<left subtree> p->data ", " <right subtree> что приводит к трейлингу ", " каждый раз

Но вы не хотите печатать ", " на каждом элементе.
-> Вы просто хотите напечатать ", " (в нужном месте), когда ( и только когда! ) вы спускаетесь в поддерево, так как в противном случае нет необходимости в разделителе ...

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

Обновление: так как я думаю, что ваша домашняя работа к настоящему времени закончена, я хочу показать свое решение:

void BinaryTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) 
        {
            inorder(p->left);
            cout << ", "; // print ", " everytime after you descended to the left
        }

        cout << p->data;

        if(p->right)
        {
            cout << ", "; // print ", " everytime before you descend to the right
            inorder(p->right);
        }
   }
}

должно выглядеть
<left subtree ", "> p->data <", " rightsubtree>

Answer 3

Вы можете ввести метод max(), который возвращает указатель на самый правый узел, а затем просто сравнить, если указатель на ваш текущий узел равен указателю на максимальный узел.

tree_node* BinaryTree::max(tree_node *p) {
    if(p != NULL && p->right != NULL) return max(p->right);
    return p;
 }

Вам потребуется метод-обертка, который вызывает inorder() и передает максимум, так как вы не хотите вычислять max в каждом рекурсивном вызове.

void BinaryTree::print() {
    inorder(root, max(root));
}

void BinaryTree::inorder(tree_node *p, tree_node *max) {
    if(p == NULL) return;        

    if(p->left) inorder(p->left, max);

    cout << p->data;
    if(p != max) cout << ", ";

    if(p->right) inorder(p->right, max);
}

Answer 4

Я бы сказал, что вы устанавливаете логический флаг, который вы передаете по ссылке на вашу подпрограмму печати (и процедура печати пропускает флаг по мере его повторения).

Первоначально флаг установлен в значение false.Когда вы собираетесь что-то напечатать, проверьте флаг.Если false, установите флаг в true и напечатайте свой элемент.Если это уже так, выведите запятую, пробел и ваш элемент.

Answer 5

Изменение

cout << p->data << ", ";
if(p->right)
{
    inorder(p->right);
}

в

cout << p->data;
if(p->right)
{
    cout << ", ";
    inorder(p->right);
}

т. Е. Запятую печатайте только в том случае, если вы уверены, что в вашем правильном ребенке что-то есть.