3

私は楽しみのために C++ で二分探索木を実装しようとしています。私の問題は、挿入機能に問題があることです。以下は私がこれまでに持っているものです：

class TreeNode{

public: 
    int data;          
    TreeNode *left;    
    TreeNode *right;  
    void Insert(int value, TreeNode *x);
    void TreeNode::Print(TreeNode *x);
    TreeNode();
};


TreeNode::TreeNode(){

left = NULL;
right = NULL;

}

.

void TreeNode::Insert(int value, TreeNode *x){

    if(x->left == NULL && x->right == NULL){
           TreeNode *tree = new TreeNode();                        
           tree->datavalue;                               
           x->left = tree;                                  
    }

    else if(x->left == NULL && x->right != NULL){

           TreeNode *tree = new TreeNode();                
           tree->data = value;                          
           x->left = tree;                                 
    }

    else if(x->left != NULL && x->right == NULL){

           TreeNode *tree = new TreeNode();                      
           tree->data = value;                            
           x->right = tree;                          
    }

    else if(x->left != NULL && x->right != NULL){

        ??????

    }

}
4

2 に答える 2

4

盲目的に挿入しないでください。以下のロジックに従ってください。x.valueがルート値よりも小さい場合は、左側に挿入してみてください。x.valueが>=root.valueの場合は、右に移動します。NULL値に達するまで、このロジックを繰り返します。それはあなたの要素を挿入するための適切な場所になります。

ロジックを反転することもできます。私は<を左に選択しました。これは、少しでも左に矢印が表示されるためです。<-：P

TreeNode *root = this;
TreeNode *parent = root;
//Traverse the tree, go left if x.val < , else go right(>=)
while(root) {
    parent = root;
    root = (root->value > x.value) ? root->left : root->right;
}
if(parent->value > x->value) 
    parent->left = x;
else
    parent->right = x;

順序を気にしない場合は、キューを使用して深さ優先探索を実行します。

queue<TreeNode*> nodes;
nodes.push(this);
while(1)
{
    if(!nodes.front()->left)
    {
        nodes.front()->left = x;
        return;
    } 
    else if (!nodes.front()->right)
    {
        nodes.front()->right = x;
        return;
    }
    nodes.push(nodes.front()->left);
    nodes.push(nodes.front()->right);
    nodes.pop();
}
于 2012-12-02T09:19:43.713 に答える
0

左右の子が両方とも NOT null の場合に挿入する場合は、ツリーの一番左のノードに再帰的に移動して項目を挿入できます。また、特定の順序で値を挿入しているだけなので、追跡するのは困難です。その場合は、むしろ二分探索木を実装してください。

else if(x->left != NULL && x->right != NULL){
         Insert(value,x->left);
         x-> data  = value;
         x->left = x->right = NULL;
}

そして最も重要なことは、再帰から抜け出すために BASE ケースを挿入することです。

于 2012-12-02T09:12:30.927 に答える