Andres CR Ответов: 2

Может ли кто-нибудь показать мне, как написать двоичное дерево поиска с 31 различными словами? С++

I have tried but it does not print out in order, I was wondering if there was anyone who was willing to help.


Что я уже пробовал:

#include<iostream>
#include<string.h>
#include<cstdlib>
using namespace std;

struct bst 
{
string data;
struct bst  *left, *right;
};

struct bst  *newNode(string key)
{
    struct bst  *temp = new struct bst ();
        temp -> data = key;
        temp -> left = temp -> right = NULL;
    return temp;
}


struct bst * insertNode(struct bst * stem, string key)
{

    if (stem == NULL)
    return newNode(key);

        if (key < stem -> data)
            stem -> left = insertNode(stem -> left, key);
    else
            stem->right = insertNode(stem -> right, key);

return stem;
}
  
void printBT(string prefix, bst * stem, int isLeft)
{
    if(stem != NULL )
{
    cout << stem -> data << endl;
    printBT(prefix + (isLeft ? "| " : " "), stem -> left, 1);
    printBT(prefix + (isLeft ? "| " : " "), stem -> right, 0);
 }
}


void insert(bst *& stem, string values[], int start, int end)
{
       if(start<=end){
       int mid = (end+start)/2;
  
       stem = insertNode(stem,values[mid]);
       insert(stem,values,start,mid-1);
       insert(stem,values,mid+1,end);
 }
}


int main()
{
string list[] = {"after","also", "any", "back", "because", "come", "day", "even", "first", "give", "how", "its", "look", "most", "new", "now", "only", "other", "our", "over",                  "than", "then", "these", "think", "two", "us", "use", "want", "way", "well", "work"};

struct bst *stem = NULL;
int length = sizeof(list)/sizeof(list[0]);
insert(stem,list,0,length-1);
printBT("", stem, 0);
}

Rick York

Я рекомендую вам прочитать об использовании ключевого слова const. Большая часть ваших данных постоянна и должна быть помечена как const.

2 Ответов

Рейтинг:
2

OriginalGriff

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

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

Начните с рассмотрения того, что он делает, и как это отличается от того, что вы хотели. Это важно, потому что это дает вам информацию о том, почему он это делает. Например, если программа предназначена для того, чтобы позволить пользователю ввести число, а он удваивает его и печатает ответ, то если ввод / вывод был таким:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Тогда совершенно очевидно, что проблема заключается в бите, который удваивает его - он не прибавляет себя к себе или умножает его на 2, он умножает его на себя и возвращает квадрат входного сигнала.
Таким образом, вы можете посмотреть на код, и очевидно, что он находится где-то здесь:
int Double(int value)
   {
   return value * value;
   }

Как только у вас появится идея, что может пойти не так, начните использовать отладчик, чтобы выяснить, почему. Поместите точку останова в первую строку метода и запустите приложение. Когда он достигнет точки останова, отладчик остановится и передаст управление вам. Теперь вы можете запускать свой код построчно (так называемый "одноступенчатый") и просматривать (или даже изменять) содержимое переменных по мере необходимости (черт возьми, вы даже можете изменить код и повторить попытку, если вам это нужно).
Подумайте о том, что должна делать каждая строка кода перед ее выполнением, и сравните это с тем, что она действительно делала, когда вы использовали кнопку "Step over" для выполнения каждой строки по очереди. Он сделал то, что вы ожидали? Если да, то переходите к следующей строке.
Если нет, то почему? Чем это отличается?
Надеюсь, это поможет вам определить, в какой части этого кода есть проблема и в чем она заключается.
Это навык, и его стоит развивать, поскольку он помогает вам как в реальном мире, так и в развитии. И, как и все навыки, он только улучшается при использовании!

Рейтинг:
0

markkuk

Ваш printBT() функция обрабатывает дерево с помощью предзаказ trversal.[^]. Если вы хотите распечатать узлы в порядке отправки ключей, используйте в обход в обратном порядке[^].

CPallini

5.