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

挿入機能にバグがあります。私が推測するように、最初はあなたのツリーは空です。最初にノードを挿入するとき、2 番目の引数は 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 に答える