如何通过NLR方式插入树的数据

Question

我有一个关于插入树数据并通过 NLR 方法打印出来的 C++ 代码。但是插入数据后，我无法使用菜单中的命令 2 打印树。

我知道问题出在“insertTree”中的某个地方，但不知道如何修复它

struct node {
    int data;
    node* left;
    node* right;
};
void insertTree(node* t, int x) {
    //if the node to add is root
    if (t->data == NULL) {
        node* p = new node();
        p->data = x;
        p->left = NULL;
        p->right = NULL;
        t = p;
    }
    else {
        //if the added element is less than t
        if (t->data > x) {
            insertTree(t->left, x);//add the element to the left of t
        }
        else if(t->data < x) {
            insertTree(t->right, x);//add the element to the left of t
        }
    }
}
void duyet_NLR(node* t) {
    if (t->data != NULL) {
        cout << t->data << " ";
        duyet_NLR(t->left);
        duyet_NLR(t->right);
        system("pause");
    }
}

Answer 1

程序中至少存在两个（或三个）大问题：

• 您勾选

  if (t->data == NULL)

  或

  if (t->data != NULL)

  的所有检查都是错误的。您需要检查

  t

  是否为空指针。

  t->data

  是

  int

  ，不应与

  NULL

  进行比较。另外，不要在 C++ 中使用

  NULL

  。使用

  nullptr

  。在这种情况下，它会对您有所帮助，因为如果您使用

  nullptr

  而不是

  NULL

  ，程序将无法编译。

• node*

  中的

  t

  insertTree

  对于函数来说是局部的。您对其所做的任何更改都不会对该函数的调用者可见（即在

  menu

  中）。这可以通过引用指针来更改：

  void insertTree(node*& t, int x)  // note a reference to the pointer
  

• menu

  中也存在与上述相同的问题。当

  menu

  返回到

  main

  时，

  main

  中的指针仍然是空指针 - 所以之后你无法删除所有节点。在那里进行相同的更改：

  void menu(node*& t)
  

使用递归插入节点可能不是问题，但您可以通过在

insertTree

内循环来查找插入点来避免它。示例：

void insertTree(node*& t, int x) {
    node** next = &t;

    while(*next) { // loop until a leaf node is found
        if((*next)->data > x) next = &(*next)->left;
        else if((*next)->data < x) next = &(*next)->right;
        // this value already exists in the tree
        else return;
    }

    // *next is here a null pointer so that's where we'll insert the new node
    *next = new node{x, nullptr, nullptr};
}

演示

您还需要添加一个函数来释放所有分配的内存。

Answer 2

void duyet_NLR(node* t) {

    if (t->data == NULL) {
        return;
    }

    cout<<t->data;
    duyet_NLR(t -> left);
    duyet_NLR(t -> right);
}