我尝试使用迭代插入 BST 树，但输出不完整。可能哪里有问题？

Question

我正在使用迭代机制在 BST 中进行插入操作。我使用递归进行了有序遍历，以快速显示我的树并知道我做的是对还是错。但是，输出始终为 4 。我不明白可能是什么问题。我的root没有更新吗？

  #include<stdio.h>
  #include<stdlib.h>
  
  typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
  } node;
  
  node *new(int data) {   //create node
    node *pw;
    pw = (node *)malloc(sizeof(node *));
    pw->data = data;
    pw->left = NULL;
    pw->right= NULL;
    
    return pw;
  }
  
  node *insert(node *root, int data) {  //insert using iteration
    node *pr;
    pr = root;
    
    if (root==NULL)
        return new(data);
    
    while (pr!= NULL) {
        if(data< pr->data) {
            if(pr->left==NULL) {
                pr->data = data;
                pr=NULL;
              }
            else {
            pr= pr->left; 
          }
          } else if(data> pr->data) {
            if(pr->right==NULL) {
                    pr->data = data;
                    pr=NULL;
              }
            else {
            pr= pr->right; 
          }
      }
  }
  return pr;
}

 void inorder(node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->data);

    // Traverse right
    inorder(root->right);
  }
}
  
  void main(){
    node* root = NULL;
    root = insert(root,5);
    root = insert(root,6);
    root = insert(root,4);
    inorder(root);   //inorder traversal for displaying tree
  }

Answer 1

似乎您总是在更改父节点的数据，而不是创建一个新节点作为父节点的子节点。 所以代替：

   if(pr->left==NULL){
        pr->data = data;
        pr=NULL;
      }

它需要是：

       if(pr->left==NULL){
        pr->left = new(data);
        break; /*you have inserted the node, a break will stop the loop*/
      }

同样的更改应该应用于正确的 if 语句。

进一步 -

insert

有这个返回语句：

return pr

并且您将其保存到调用者的

root

中。然而，仅当

root

为 NULL 时才能更改

root

。换句话说：返回

pr

是错误的。

因此进行此更改：

return pr; ---> return root;