0

練習のために単純な二分探索木を実装しようとしていました。値を追加して、ノードに値を出力しようとしました。ただし、ノード内の値の適切な昇順が得られません。これが私が持っているものです：

struct Node
{
    int data;
    Node* leftN;
    Node* rightN;

};

typedef Node* Node_ptr;
Node_ptr head;

//INSERT_VALUE FUNCTION
Node* insert_value(Node_ptr leaf, int key)
{
    //Root case when there is no set value yet  
    if(leaf == NULL)
    {
        leaf = new Node;
        head = leaf;
        cout << "Make the first node" << endl;
        leaf->data = key;
        leaf->leftN = NULL;
        leaf->rightN = NULL;
        return leaf;
    }   
    //Left child Node
    if(key < leaf->data)
    {
        //Search for a spot in the tree to add a Node (left value < root value < right value)
        //This is only true for the left child Node
        if(leaf->leftN != NULL)
            insert_value(leaf, key);
        //We have found a spot in the tree to add a new Node and add the value of key
        else 
        {
            cout << "Insert-left" << endl;
            leaf->leftN = new Node;
            leaf = leaf->leftN;
            leaf->data = key;
            leaf->leftN = NULL;
            leaf->rightN = NULL;
            return leaf;
        }
    }

    //Right child Node
    else if(key >= leaf->data)
    {
        //Search for a spot to add a new Node in the tree (only amongst the right child Nodes)
        if(leaf->rightN != NULL)
            insert_value(leaf, key);    
        //Once we have found a spot to add a new Node, append the new Node
        else
        {
            cout << "Insert-right" << endl;
            leaf->rightN = new Node;
            leaf = leaf->rightN;    
            leaf->data = key;
            leaf->leftN = NULL;
            leaf->rightN = NULL;
            return leaf;
        }
    }   
}

//PRINT FUNCTION
void printTree(Node_ptr leaf)
{
    if(leaf == NULL)
        return;
    printTree(leaf->leftN);
    cout << "Data element: " << leaf->data << endl;
    printTree(leaf->rightN);
}

//MAIN
int main()
{
    Node_ptr root = NULL;
    int i;

    //initialize values
    for(i = 1; i < 12; i+=2)
        root = insert_value(root, i);
    root = head;
    for(i = 0; i < 11; i+=2)
        root = insert_value(root, i);
    root = head;
    printTree(root);

    root = head;
    cout << "Head Node: " << root->data << endl;

    return 0;
}

結果を印刷すると、0、2、4、6、8、10、1、3、5、7、9、11 となり、ヘッド ノードの値は 1 です。

4

2 に答える 2

1

挿入を次のように呼び出しているためです。

    root = insert_value(root, i);

挿入する場所は常に、最後の挿入から始まるサブツリーを使用しています。先頭から挿入を開始するとき、奇数を追加し直すときを除いて。

class BinarySearchTreeヘッド ポインタを含むを作成し、それint valueを呼び出すを受け取る挿入メソッドを作成するNode::insert( head, value )と、ノードを渡すことなく、そのクラスで単に挿入を呼び出すことができ、挿入がそのルートを使用することを常に確認できます。再帰の開始のためのツリー。

私だけですが、ノードを取りint、ポインターを NULL に初期化するコンストラクターが必要です。そうすれば、挿入メソッドでそれを行う必要はありません。

于 2012-04-11T23:45:08.550 に答える
0

リーフ - >ノードで？!= NULL の場合、呼び出す代わりに考える

insert_value(leaf, key);

あなたが言いたい

leaf->node? = insert_value(leaf->node?, key)

どこ ？もちろんLかRです。

あなたが考えるかもしれないことは、次のようにメソッドにコメントを追加することです:

// Adds the given key to the (sub-)tree rooted at node* then returns the new root
// of that (sub-)tree.
node *insert_value_and_return_root(node *root, int value) { ... }
于 2012-04-11T23:43:13.967 に答える