二叉樹搜索無返回結果（C++）

我正在研究一些二叉樹算法，並需要一個「find searchindex ...」查找節點。 treenodes的設計基本上是二叉樹搜索無返回結果（C++）

class TreeNode { 
    int index; // some identifier 
    TreeNode *left; 
    TreeNode *right; 
}

並且樹由指向根節點的指針定義。

我對搜索功能的實現是：

void Tree::searchNode(TreeNode * root, int nodeIndex, TreeNode *resultNode){ 
/* Recursive search */ 

    if (root->index == nodeIndex) { 
      resultNode = root; 
    } else { 

    /* search children if the current node is not a leaf */ 

    if(!root->isLeaf()) { 
     this->searchNode(root->left,nodeIndex,resultNode); 
     this->searchNode(root->right,nodeIndex,resultNode); 
     } 
    } 
}

參數： * 根是樹的根節點，nodeIndex是搜索索引和* resultNode是指向樹中找到（或不）節點的指針。

該函數不返回引用或指針所找到的節點，但修改了指針resultNode使其指向所找到的節點。這個想法是用NULL初始化resultNode，如果匹配發生，執行搜索並修改它。否則它仍然是NULL，我可以輕鬆地檢查是否有搜索結果。

另一類與樹buildingTree作爲成員利用這樣的搜索功能：

TreeNode *resultNodePtr = NULL; 
this->buildingTree->searchNode(this->buildingTree->rootPtr, 
           currentNodeIndex, resultNodePtr); 

// do sth. with resultNodePtr if != NULL

我創造* resultNodePtr堆棧，因爲我只需要它暫時裏面的功能上。這是否正確完成？但是：該功能不起作用。 resultNodePtr始終爲NULL，即使樹包含具有search-index的節點。我調試它非常仔細地一步一步，它檢測

(root->index == nodeIndex)

正確，但

resultNode = root;

不起作用（我想resultNode指向同一個地址根點）。調試器說resultNode在賦值之前是0x0,根節點是一些地址，賦值resultNode仍然是0x0。

是否必須重載運算符=在這種情況下爲類TreeNode？

我已經嘗試過了：

TreeNode & TreeNode::operator=(const TreeNode & oldTreeNode){ 
*this = oldTreeNode; 
return *this; 
// ignore childs for now 
}

我不是專家，但這個操作符=似乎微不足道。它會影響兩個TreeNode指針* node1 = * node2的分配嗎？

也許你可以幫我。感謝您的閱讀，感謝您的幫助。如果我自己找到解決方案，我會在這裏發佈。

問候，馬克

來源

2011-08-26 Mark

是否有一個原因的指針傳遞和修改呢？使用返回值似乎更簡潔，並且可以避免以下答案中解釋的問題。 – mwd

完全無關您的問題，但通常一個樹排序，該搜索可以更快的方式來實現。是否有理由搜索樹的每個節點？實際上，你的類在std :: list上搜索比std :: find慢！ –

另外，該運算符=您實現的是一個無限遞歸循環。它應該像'index = oldTreeNode.index; left =（oldTreeNode.left？new TreeNode（* oldTreeNode.left）：nullptr）;右=（？oldTreeNode.right新的TreeNode（* oldTreeNode.right）：nullptr）;' –

因爲你傳遞resultNode到函數的指針通過價值，其原始值永遠不會改變。的TreeNode*看成是字面上沒有什麼比代表存儲器地址的數量較多;當你將其重新分配：

resultNode = root;

這將修改searchNode有副本，而不是原來的指針，在該調用searchNode的代碼。拿這個簡單的例子：

void Foo(int x) 
{ 
    x = 100; 
} 

void Bar() 
{ 
    int x = 0; 
    Foo(x); 
    // at this point, x is still 0 
}

resultNode的價值不會改變NULL出於同樣的原因被調用函數Bar時x不會0改變。要解決這個問題，通過引用的一個指針傳遞指針的指針，或指針：

void Tree::searchNode(TreeNode* root, int nodeIndex, TreeNode*& resultNode) 
{ 
    // same code 
}

...或：

void Tree::searchNode(TreeNode* root, int nodeIndex, TreeNode** resultNodePtr) 
{ 
    // assign to *resultNodePtr instead 
}

來源

2011-08-26 17:44:59 Dawson

問題修復。非常感謝您的詳細幫助。 :) – Mark

你resultNode指針被按值傳遞，不作參考。所以當函數調用完成時，主叫方的指針沒有收到一個值。

你的算法看起來不錯:)

來源

2011-08-26 17:47:26 lettucemode

問題修復。謝謝你的幫助！ :) – Mark

二叉樹搜索無返回結果（C++）

回答

相關問題