1

我正在编写一个 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;
        }   
}

感谢您提供任何帮助。

4

3 回答 3

2

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

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;
于 2011-07-09T22:26:23.023 回答
1

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

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

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

  temp = new treeNode;
  temp->data=num;
  temp->left=NULL;
  temp->right=NULL;
  if(num < parent->data)
     parent->left = temp;
  else
     parent->right = temp;
于 2011-07-09T22:28:37.453 回答
0

算法

  1. if root == null 创建分配给 Root 的新节点
  2. 根据与 rootNode 的比较继续迭代,直到到达任何叶节点
  3. 检查是否 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;
        }
    }
}
于 2017-07-08T07:53:35.427 回答