Binary Tree реализация C++

Question

вставки

Binary Tree:

#include "stdafx.h" 
#include <iostream> 

using namespace std; 

struct TreeNode { 
    int value; 
    TreeNode* left; 
    TreeNode* right; 
}; 

struct TreeType { 
    TreeNode* root; 

    void insert(TreeNode* tree, int item); 

    void insertItem(int value) { 
    insert(root, value); 
    } 
}; 

void TreeType::insert(TreeNode* tree, int number) { 
    if (tree == NULL) { 
    tree = new TreeNode; 
    tree->left = NULL; 
    tree->right = NULL; 
    tree->value = number; 
    cout << "DONE"; 
    } else if (number < tree->value) { 
    insert(tree->left, number); 
    } else { 
    insert(tree->right, number); 
    } 
} 

int main() { 
    TreeType* MyTree = new TreeType; 
    MyTree->insertItem(8); 

    return 0; 
} 

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

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

Может ли кто-нибудь сказать мне, где я ошибаюсь?

Answer 1

В конструкторе дерева, вам необходимо инициализировать указатель корня на NULL. Он не гарантированно инициализируется как NULL.

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

Некоторые другие примечания:

1. Вы должны присвоить значение обратно root после того как вы выделили новый узел. Вы этого не делаете, потому что вам не хватает одной из основ C++. То есть, это основано на c. И дело в том, что это строго «парадоксальная» функция/метод, вызывающая парадигму. Таким образом, все параметры вызова функции имеют значение. Когда вы передаете адрес памяти для root, вы фактически копируете значение указателя. Затем вы обновляете только локальное значение. Вам нужно назначить его обратно root. Если вы хотите изучить эту концепцию спереди назад, я настоятельно рекомендую посмотреть Jerry Cain's Programming Paradigms course at Stanford.
2. В вашей основной функции вы должны попытаться сохранить имена символов как lower_case вместо CamelCase. Это помогает дифференцировать переменные от типов (типы должны оставаться CamelCase).
3. В вашем методе TreeType :: insert вы должны вызывать переменную tree_node вместо дерева. Это помогает отражать правильный тип и позволяет избежать путаницы.
4. По возможности попробуйте использовать обозначения this->root и this->insert. Мало того, что это будет правильно разрешено, если вы случайно создадите переменную root с локальным областью, но она также понятна читателю, где определены данные или метод. Отличное кодирование касается общения. Для читателя может потребоваться меньше 100-500 мсек, чтобы понять, на что указывает символ; однако крошечные сбережения, которые вы можете аккумулировать во избежание неоднозначностей, складываются в гораздо более четкое программное обеспечение. Ваше будущее я (и ваши коллеги) поблагодарит вас. См. http://msmvps.com/blogs/jon_skeet/archive/2013/09/21/career-and-skills-advice.aspx

Наконец, я могу преувеличивать, насколько важно учиться у источника. Если вы изучаете c или C++ в первый раз, прочитайте http://www.amazon.com/The-Programming-Language-4th-Edition/dp/0321563840 и http://www.amazon.com/Programming-Language-2nd-Brian-Kernighan/dp/0131103628. Это сэкономит вам часы, часы, часы. После того, как вы узнали из источника, программирование также намного более приятное, потому что вы понимаете значительную часть концепций. И, на самом деле, все гораздо веселее, когда у вас есть достойный уровень компетентности в них.

Answer 2

В вашем конструкторе TreeType я думаю, что вы должны явно указать корень в NULL.

TreeType::TreeType() { 
    root = NULL; 
} 

Answer 3

Попробуйте что-то вроде this-

struct Node { 
    int Data; 
    Node* Left; 
    Node* Right; 
}; 

Node* Find(Node* node, int value) 
{ 
    if(node == NULL) 
     return NULL; 
    if(node->Data == value) 
     return node; 
    if(node->Data > value) 
     return Find(node->Left, value); 
    else 
     return Find(node->Right, value); 
}; 

void Insert(Node* node, int value) 
{ 
    if(node == NULL) { 
     node = new Node(value); 
     return; 
    } 
    if(node->Data > value) 
     Insert(node->Left, value); 
    else 
     Insert(node->Right, value); 
};