2012-04-11 25 views
0

私は実践のために単純なバイナリ検索ツリーを実装しようとしていました。私はちょうど値を追加し、ノードの値を印刷しようとしました。しかし、私はノードの値の適切な昇順を取得していません。ここで私が持っているものである。バイナリ検索ツリーC++

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; 
} 

Iが結果を印刷する場合、これは私が得たものである: 0、2、4、6、8、10、1、3、5、7、9、11、およびヘッドノードの値は1

+0

Re: 'typedef Node * Node_ptr'。 'Node_ptr'は' Node * 'よりも多くのキーストロークであり、それでもやはり不必要な空白を含むことに注意してください。 :) – Kaz

答えて

1

:あなたが考えるかもしれません

何かがそうのような方法にコメントを追加して最後の挿入から始まるサブツリー。奇数を追加し直す時間を除いて、頭の中で挿入を開始するとき。

あなたが先頭ポインタが含まれているclass BinarySearchTree、およびNode::insert(head, value)を呼び出すint valueを取っinsertメソッドを作成する場合、あなたはそれにノードを通過することなく、そのクラスに挿入を呼び出すことができ、それが常にあること、それに見ることができます挿入は、再帰の開始にツリーのルートを使用します。

私はちょうど私ですが、私はintを取り、NULLへのポインタを初期化するNode用のコンストラクタを持っています。そうすれば、挿入メソッドでそれを行う必要はありません。

0

リーフ→ノード? != NULLの場合は、私が代わりに

insert_value(leaf, key); 

を呼び出すあなたは

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

どこを言いたいと思いますか?もちろん、LかRのどちらかです。あなたが挿入した位置が常に使用され

root = insert_value(root, i); 

:としてあなたが挿入を呼び出しているので

// 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) { ... } 
関連する問題