Неожиданный результат двоичного дерева

struct BSTreeNode
{
    struct BSTreeNode *leftchild;  
        AnsiString data;  
    struct BSTreeNode *rightchild;  
};

struct BSTreeNode * root;  

String tree = "";

struct BSTreeNode * newNode(AnsiString x)  
{
    struct BSTreeNode * node = new struct BSTreeNode;
    node->data = x; 
    node->leftchild = NULL;  
    node->rightchild = NULL;  
    return node;
}

struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x)  
{   if (node == NULL) return newNode(x);
    if (x < node->data)
        node->leftchild = insertBSTree(node->leftchild, x);
    else
        node->rightchild = insertBSTree(node->rightchild, x);
    return node;
}

void printBSTree(struct BSTreeNode * node) 
{   if (node != NULL)
    {   printBSTree(node->leftchild);
        tree += node->data+"_";
        printBSTree(node->rightchild);
    }
}

//--- insert button ---
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    AnsiString data;
    data = Edit1->Text;
    root = insertBSTree(root, data);
    tree = "";
    printBSTree(root);
    Memo1->Lines->Add(tree);
}

Предположим, что я вставляю A、B、C、D、E、F、G в двоичное дерево (Button1Click — это кнопка для вставки данных в двоичное дерево) двоичное дерево должно быть таким

      A
    /   \
   B     C
  / \   / \    
 H  J   D  E
       / \
      F   G

но оказалось, что это похоже на

 A   
  \    
   B
    \
     C
      \
       D
        \
         E
          \
           F
            \ 
             G

struct BSTreeNode ---> узел дерева

struct BSTreeNode * newNode(AnsiString x) ---> создание нового узла

button1Нажмите ---> вставьте данные из Edit->text; к бинарному дереву.

InsertBSTree ---> если узел имеет значение NULL, создайте новый узел. Вставка данных в leftchild/rightchild

В C++ бесполезно использовать ключевое слово struct при указании типа. BSTreeNode это уже типаж, не пишите struct BSTreeNode везде.

prapin 28.02.2024 17:30

@prapin: можно также предложить использовать ссылки или сделать эти функции функциями-членами.

Chris 28.02.2024 17:33

Пожалуйста, опубликуйте минимальный пример проблемы (похоже, достаточно только A и B) и то, что вы сделали, чтобы попытаться диагностировать проблему (т. е. использовать отладчик, чтобы увидеть, где он сначала не сделал то, что вы ожидали).

Scott Hunter 28.02.2024 17:33

Каковы значения data в вашем примере?

Scott Hunter 28.02.2024 17:34

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

john 28.02.2024 17:42

Я отладил и ошибок нет. «данные» хранят значение двоичного дерева. Например, если я вставлю «A» в двоичное дерево (Button1Click), значение «A» будет сохранено в «данных». Ассистент моего учителя рассказал мне, что мое бинарное дерево оказалось таким, как второе в посте.

Cat Ball 29.02.2024 17:14
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
6
73
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы создали двоичное дерево поиска, используя <, чтобы определить, в какую ветвь вставить:

struct BSTreeNode * insertBSTree(struct BSTreeNode * node , AnsiString x)  
{   if (node == NULL) return newNode(x);
    if (x < node->data)
        node->leftchild = insertBSTree(node->leftchild, x);
    else
        node->rightchild = insertBSTree(node->rightchild, x);
    return node;
}

Ваш второй пример — двоичное дерево поиска, но не сбалансированное.

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

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

       D
      / \
     /   \
    /     \
   B       F    
  / \     / \
 A   C   E   G

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

A
 \
  B
   \
    C

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

   B
  / \
 A   C

Чтобы сбалансировать исходное дерево:

 A   
  \    
   B
    \
     C
      \
       D
        \
         E
          \
           F
            \ 
             G

Вы проверите каждое поддерево, чтобы убедиться, что оно сбалансировано. Первое несбалансированное поддерево — это E, F, G.

 A   
  \    
   B
    \
     C
      \
       D
        \
         F
        / \
       E   G

Тогда мы увидим, что D, E, F, G несбалансированы вправо.

 A   
  \    
   B
    \
     C
      \
       E
      / \
     D   F
          \
           G

И так далее...

 A   
  \    
   B
    \
     D
    / \
   C   E
        \
         F
          \
           G
 A   
  \    
   B
    \
     D
    / \
   C   F
      / \
     E   G
 A   
  \    
   C
  / \
 B   D
      \
       F
      / \
     E   G
 A   
  \    
   C
  / \
 B   E
    / \
   D   F
        \
         G
  A   
   \    
    D
   / \
  C   E
 /     \
B       F
         \
          G
  A   
   \    
    D
   / \
  C   F
 /   / \
B   E   G
    B   
   / \    
  A   C
       \
        D
         \
          F
         / \
        E   G

    B   
   / \    
  A   C
       \
        E
       / \
      D   F
           \
            G
    B   
   / \    
  A   D
     / \
    C   E
         \
          F
           \
            G
    B   
   / \    
  A   D
     / \
    C   F
       / \
      E   G
    C   
   / \    
  B   D
 /     \
A       F
       / \
      E   G
    C   
   / \    
  B   E
 /   / \
A   D   F
         \
          G

Если пойти еще на несколько шагов дальше:

      D   
     / \    
    C   E
   /     \
  B       F
 /         \
A           G
      D   
     / \    
    B   E
   / \   \
  A   C   F
           \
            G
       D
      / \
     /   \
    /     \
   B       F    
  / \     / \
 A   C   E   G

Другие вопросы по теме