2

我在 StackOverflow 上遇到了一些线程，但没有一个能完全消除我的疑虑。

所以问题很简单。我需要迭代地将元素插入二叉树。这是我的代码。

BST newNode(int x)
{
    BSTNodePtr node = (BSTNodePtr) malloc(sizeof(struct TreeNode));
    node->Element = x;
    node->Left = NULL;
    node->Right = NULL;

    return node;

}

BST Insert(int x, BST T)
{
    BST temp_node = T;
    while( T != NULL)   {
        if (x < T->Element)
            T = T->Left;
        else if (x >= T->Element)
            T = T->Right;
    }

    T = newNode(x);

    return temp_node;

}

但是，当我找到这棵树的高度时，我总是得到 0。高度代码是

int Height(BST T)
{
    if (T == NULL)
        return 0;

    return 1+(max(Height(T->Left), Height(T->Right)));
}

当我递归地插入时，这工作得很好（使用具有完全相同签名的函数）

我错过了什么？

4

6 回答 6

1

这里：

BST Insert(int x, BST T)
{
    BST temp_node = T;
    while( T != NULL)   {
        if (x < T->Element)
            T = T->Left;
        else if (x >= T->Element)
            T = T->Right;
    }

    T = newNode(x);

    return temp_node;

}

您导航树，直到您点击T == NULL。然后创建一个节点并将指向它的指针分配给T. 然后返回原始值T。你根本不修改你的树。其中没有节点指向新创建的节点。T只是一个局部变量。

于 2012-09-23T06:03:15.153 回答
1

不能这样解决问题。但是，此代码似乎有效。

BST Insert(int x, BST T)
    {
       BST temp=T;
       BST node=(BST)malloc(sizeof(struct TreeNode));
       node->Element=x;
       node->Left=NULL;
       node->Right=NULL;
       if (T==NULL)
       {
           T=node;
           return(T);
           //printf("%d\n",T->Element);
       }
       else
       {
           while(1)
           {
               if (temp->Element>=node->Element && temp->Left==NULL)
               {
                   temp->Left=node;
                   break;
               }
               else if (temp->Element>=node->Element && temp->Left!=NULL)
               {

                   temp=temp->Left;
               }
               else if (temp->Element<node->Element && temp->Right==NULL)
               {
                   temp->Right=node;
                   break;
               }
               else
               {
                   temp=temp->Right;
               }
           }   
                 return(T);
       }            
    }
于 2012-09-23T09:12:11.050 回答
1

这是我对上述问题的实现：

bst* newNode(int x)
{
    bst* T = new bst;
    T->value = x;
    T->left_child = T->right_child = NULL;
    return T;
}

bst* bst_insert_iter(bst* T,int val)
{
    if (T == NULL)
        T = newNode(val);

    else
    {

    bst *temp_node = T;

    bool flag = true;

    while(flag)   
    {
        if (val <= temp_node->value)
        {
            if (temp_node->left_child == NULL)
            {
                temp_node->left_child=newNode(val);
                flag = false;
            }
            else
                temp_node = temp_node->left_child;
        }

        else
        {
            if (temp_node->right_child == NULL)
            {
                temp_node->right_child=newNode(val);
                flag = false;
            }
            else
                temp_node = temp_node->right_child;
        }
    }

    }
    return T;
}
于 2013-09-12T11:52:18.580 回答
0

您的插入功能中有错误。我可以假设，最初你的树是空的。所以第一次插入节点时，第二个参数是NULL，对吧？然后这个函数总是返回 NULL 给你，因为你总是传递一个 NULL 值。

于 2012-09-23T06:00:33.693 回答
0 
template <class T>
class TreeNode{
private:
    T data;
    TreeNode<T>* right,*left;
public:
void setData(T d){
    this->data =d;
}
T getData(){
    return this->data;
}
void setRight(TreeNode<T>* r){
    this->right =r;
}
TreeNode<T>* getRight(){
    return this->right;
}
void setLeft(TreeNode<T>* r){
    this->left =r;
}
TreeNode<T>* getLeft(){
    return this->left;
}
static TreeNode<T>* newNode(T data){
    TreeNode<T>* n = new TreeNode<T>();
    n->setData(data);
    n->setRight(NULL);
    n->setLeft(NULL);
    return n;
}
};



template <class T>
class BinaryTree{
private:
        TreeNode<T>* root;
public:
    void insert(T data){
        TreeNode<T>* n = TreeNode<T>::newNode(data);

        if(root==NULL)
            root = n;
        else{
        TreeNode<T>* t = root;
        while(t!=NULL){

            if(n->getData() >= t->getData()){
                if(t->getRight()==NULL){
                    t->setRight(n); //newnode attached as right child in tree
                    t = NULL;
                }
                else
                    t = t->getRight();
            }
            else{
                if(t->getLeft()==NULL){
                    t->setLeft(n); //newnode attached as left child in tree
                    t=NULL;
                }
                else
                    t = t->getLeft();
            }
        }

        }

    }

    void preorder(){
        TreeNode<T>* t = root;
        preorderUtil(t);
    }

    void preorderUtil(TreeNode<T>* node){
        if(node==NULL)
            return;
        preorderUtil(node->getLeft());
        cout<<node->getData()<<" ";
        preorderUtil(node->getRight());
    }
};

您的更改不会反映在树中。我按照这种方式迭代插入数据，效果很好。关键是在二叉树中创建一个节点来指向新创建的节点，以便它附加到树上。

于 2016-12-17T08:18:12.207 回答
0

这是我的版本，它似乎正在工作。

struct tree{
tree *left;
tree *right;
int key;
};
void insertBst(int k,tree *t)
{
    tree *newK = new tree[sizeof(tree)];
    newK->key = k;
    newK->left = NULL;
    newK->right = NULL;
    if((t)->key == NULL)
    {
        t=newK;
        return;
    }
    else{
        bool found = false;
        tree *root = t;
        tree *parent = NULL;
        while(root != NULL)
        {
        parent = root;
            if(root->key < newK->key)
            {
                root=root->right;
            }
            else if(root->key > newK->key)
            {
                root=root->left;
            }
            else{
            //Here we have duplicates!! so do nothing
            root = root;
            }
        }
        if(parent->key > newK->key) parent->left = newK;
        else parent->right = newK;  
    }   

}
于 2017-11-11T19:49:25.747 回答