用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. 如果root == null创建新节点分配给root
2. 根据与rootNode的比较继续迭代，直到到达任何叶子节点
3. 检查是否num <= parent(leaf)插入到左侧否则插入到右侧

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