二叉树实现C++

Question

二叉树插入:

#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来显示段错误源的来源.

其他一些说明:

1. root在分配新节点后,应将值重新分配给.你没有这样做,因为你错过了c ++的基本原理之一.也就是说,它基于c.关于c的事情是严格地称为"按值"的函数/方法调用范例.因此,函数调用中的所有参数都是按值.传入root的内存地址时,实际上是在复制指针的值.然后,您只是更新本地值.您需要将其分配回root.如果您想从头到尾学习这个概念,我强烈建议您在斯坦福大学观看Jerry Cain的编程范例课程.
2. 在main函数中,您应该尝试将符号名称保留为lower_case而不是CamelCase.这有助于区分变量与类型(类型应保留CamelCase).
3. 在TreeType :: insert方法中,应该调用变量tree_node而不是tree.这样做有助于反映正确的类型并避免混淆.
4. 尽可能尝试使用this->root和this->insert表示法.如果您不小心创建了本地范围的root变量,它不仅会正确解析,而且对于定义数据或方法的读者来说,它也更清晰.伟大的编码是关于沟通.读者可能只需要100-500ms就能理解符号指向的位置; 然而,你可以在避免歧义方面积累的微小成本加起来成为一个更加清晰的软件.你未来的自己(和你的同事)会感谢你.请参阅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

试试这样的事情 -

 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 );
};