时间戳

首页 > 解决方案 > Traversal pointer in tree while insertion

c++ - Traversal pointer in tree while insertion

问题描述

#include<iostream>

using namespace std;

struct node
{
    int data;
    node *right;
    node *left;
} ;

node *root = NULL;
node *right = NULL;
node *left = NULL;

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = NULL;
    ptr->right = NULL;

    if(root==NULL)
    {
        root = ptr;
        cout<<"Inserted "<<root->data<<" at root\n";
    }
    else
    {
        node *pos = root;
        while(pos)
        {
            cout<<pos->data<<" pos->data\n";
            if(pos->data > data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->left;
            }
            else if(pos->data < data)
            {
                cout<<pos->data<<": data\n";
                pos = pos->right;
            }
            if(!pos)
                cout<<"NULL\n";
        }
        pos = ptr;
        cout<<"Inserted\n";
    }
    return *root;
}

void preorder(node *root)
{
    if(root)
    {
        cout<<root->data;
        preorder(root->left);
        preorder(root->right);
    }
}

int main()
{
    insert(2);
    insert(1);
    insert(3);
    insert(4);
    insert(5);
    preorder(root);
    return 0;
}

Here, while inserting the new element, I am pointing root to new variable pos so that root is unaltered so that it becomes parameter to the function preorder() properly as it is the actual root

But, pos isn't inserting all the elements and also not displaying the required results. In short I have to use root instead of pos to insert, but using root directly is altering the 'actual' root (which in this case is 2).

标签： c++data-structurestreebinary-tree

解决方案

但是， pos 没有插入所有元素，也没有显示所需的结果。

我认为主要有两个错误。

  • root在当前insert函数中永远不会更新，因为ptr仅pos在 while 循环完成后才分配给时间变量。

  • 我们应该考虑传递参数的值data已经保存在二叉树中的情况。

此外，一再preorder显示令人困惑。root下面是一个修复insertand的示例preorder。 演示在这里。

node insert(int data)
{
    node *ptr = new node;
    ptr->data = data;
    ptr->left = nullptr;
    ptr->right = nullptr;

    if(!root)
    {
        root = ptr;
    }
    else
    {
        node *pos = root;

        while(true)
        {
            if(pos->data > data)
            {
                if(!pos->left){
                    pos->left = ptr;
                    break;
                }

                pos = pos->left;
            }
            else if(pos->data < data)
            {
                if(!pos->right){
                    pos->right = ptr;
                    break;
                }

                pos = pos->right;                
            }
            else{
                break;
            }
        }
    }
    return *root;
}

void preorder(node *next)
{
    if(next)
    {
        cout << next->data << std::endl;
        preorder(next->left);
        preorder(next->right);
    }
}

推荐阅读