0

バイナリツリーのアイテムが正しく挿入されないという問題があります。各ノードに文字列を挿入しています。私はいつも間違った木になってしまうように見えるので、私は何か間違ったことをしているのではないかと思います。すなわち

A、B、C

私が持っている必要があります

   B
  /  \
 A    C

しかし、どういうわけか私は次のようになります：

   C
  / \
 B   A

または、ツリーに挿入する順序によって異なるものがあります。

これは私のツリークラスです：

これは私の挿入メソッドと挿入ヘルパーメソッドです。見て、私が間違っていることを確認できますか？前もって感謝します。

void BinarySortTree::insert(string key)
{
    if(root != NULL)
    {
        insert(key, root);
    }
    else
    {
        root = new TreeNode;
        root->item = key;
        root->left = NULL;
        root->right = NULL;
    }
}

void BinarySortTree::insert(string key, TreeNode *node)
{
    bool done = false;

    while(!done)
    {
        if(key.compare(node->item) < 0)
        {
            if(node->left != NULL)
            {
                node = node->left;
            }
            else
            {
                node->left = new TreeNode;
                node->left->item = key;
                node->left->left = NULL;
                node->left->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) > 0)
        {
            if(node->right != NULL)
            {
                node = node->right;
            }
            else
            {
                node->right = new TreeNode;
                node->right->item = key;
                node->right->left = NULL;
                node->right->right = NULL;
                done = true;
            }
        }
        else if(key.compare(node->item) == 0)
        {
            done = true;
        }
    }

}
4

1 に答える 1

1

たとえば、最初に C を挿入した場合、次に挿入する項目 (たとえば b) はルートで発生しないため、「C」、「B」、「A」を挿入するとこの順序で、次のような形のツリーができます。

    C
   /
  B
 /
A

現在のノードを変更する必要がある場合は、毎回チェックする必要があります! 挿入するたびにルートが変更される可能性があるため、キーを再挿入します。そして、あなたが描く木は、あなたのコードが生成する唯一の危険な形の木を決して生成しません。

 ABC        ACB      BAC        CBA     CAB
                     BCA        
 A          A         B            C       C            
  \          \       / \          /       /      
   B          C     A   C        B       A            
    \        /                  /         \ 
     C      B                  A           B
于 2011-03-13T19:47:07.443 に答える