二進制搜索樹C++

我試圖爲實踐實現一個簡單的二叉搜索樹。我試圖只添加值並在節點中輸出值。但是，我沒有得到節點中正確的升序值。這裏是我有：二進制搜索樹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; 
}

當我打印結果，這是我得到： 0，2，4，6，8，10，1，3，5，7，9，11和頭節點的值爲1

來源

2012-04-11 Josh

Re：'typedef Node * Node_ptr'。請注意，'Node_ptr'比'Node *'更多擊鍵，並且仍然設法包含無關緊要的空白。 :) – Kaz 2012-04-12 00:42:04

因爲您呼叫的插入爲：

root = insert_value(root, i);

的位置上，你插入總是使用從最後一次插入開始的子樹。除了重新開始添加奇數的時候，當你開始插入頭部時。

如果你創建一個class BinarySearchTree包含頭指針，以及插入方法服用int value調用Node::insert(head, value)，那麼你可以調用這個類的插入，沒有傳遞給它的一個節點，它總能看到它，插入使用樹的根來開始遞歸。

只是我，但我會有一個構造函數的節點，需要int並初始化指針爲NULL。這樣你就不必在插入方法中做到這一點。

來源

2012-04-11 23:45:08 DRVic

在leaf-> node？！= 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-11 23:43:13 caskey

二進制搜索樹C++

回答

相關問題