使用 c++ 在二叉树中非递归添加函数

Question

我正在编写一个 Add 函数以非递归方式向二叉树添加节点。 我遇到了只能生成一层深二叉树的问题。我调试了它，我知道问题出在哪里，但不知道如何修复它。也许新的眼睛会看到一些我看不到的东西...... 问题是我的临时节点在每次新函数调用时都会重置为根值，因此会线性添加节点。 无论如何，这是功能：

   void BinaryTreeNonRec::add(int num){
        treeNode *temp, *parent;

        if (root==NULL) {
            root = new treeNode;
            root->data=num;
            root->left=0;
            root->right=0;
            temp=root;
            printf("value is root \n");
        } else {
            temp=root;
            while (temp!=NULL) {
                if (num <= temp->data){
                    parent = temp;
                    temp=temp->left;
                    //root =temp;
                    printf("value is to the left \n");
                } else {
                    parent =temp;
                    temp=temp->right;
                    //root=temp;
                    printf("value is to the right \n");
                }               
            }   
            parent = new treeNode;
            parent->data=num;
            parent->left=NULL;
            parent->right=NULL;
            temp=parent;
        }   
}

感谢您的任何帮助。

Answer 1

您不是将新节点添加到树中，只是沿着树向下运行并用新节点填充父节点，但从不将其添加到树中，请将以下代码更改

parent = new treeNode;
parent->data=num;
parent->left=NULL;
parent->right=NULL;
temp=parent;

为：

treeNode *newNode = new treeNode;
newNode->data = num;
newNode->left = NULL;
newNode->right = NULL;

//Now insert the new node BELOW parent
if(num <= parent->data)
    parent->left = newNode;
else
    parent->right = newNode;

Answer 2

问题可能是您从未将新节点添加到树中。

  parent = new treeNode;
  parent->data=num;
  parent->left=NULL;
  parent->right=NULL;
  temp=parent;

您将新节点分配给 temp 和parent，它们是临时变量，因此不存在于函数外部。您要做的是将新节点分配给父级>左节点或父级>右节点，具体取决于您的新输入位于哪一侧，以便将其链接到树中。因此，您想要做的是如下所示：

  temp = new treeNode;
  temp->data=num;
  temp->left=NULL;
  temp->right=NULL;
  if(num < parent->data)
     parent->left = temp;
  else
     parent->right = temp;

Answer 3

算法

1. if root == null 创建新节点分配给 Root
2. 根据与 rootNode 的比较不断迭代，直到到达任何叶节点
3. 检查 if num <=parent(leaf) 插入左侧 ELSE 插入右侧

代码

private void insertItrInBST(int num){
    Node temp = root,parent = root;

    if(root == null){
        root = getNewNode(num);
    }else{
        temp = root;

        while(temp != null){
            if(num <= root.data){
                parent = temp;
                temp = temp.left;   
            }else{
                parent = temp;
                temp = temp.right;
            }
        }
        Node newNode = getNewNode(num);
        if(num <= parent.data){
            parent.left = newNode;
        }else{
            parent.right = newNode;
        }
    }
}