二叉搜索樹插入C++植根於當前節點

我需要添加一個項目到一個二叉樹只給予要添加的項目。二叉搜索樹插入C++植根於當前節點

這裏是我給出的代碼：

void BinaryTree::add(Data * data) { 
    if (root == NULL) { 
     root = new BinaryTreeNode(data); 
    } 
    else { 
     root->add(data); 
    } 
}

其中root被定義爲BinaryTreeNode一個BinaryTree的私有變量。

我需要實現的方法：

void BinaryTreeNode::add(Data * data);

其中一個BinaryTreeNode是：

class BinaryTreeNode { 
public: 
    Data * nodeData; 
    BinaryTreeNode * left; 
    BinaryTreeNode * right; 

    /** 
    * Constructor 
    */ 
    BinaryTreeNode(
     Data * data, 
     BinaryTreeNode * left = NULL, 
     BinaryTreeNode *right = NULL 
    ) 
     : nodeData(data), left(left), right(right) 
    { } 

    // ...

我想遞歸地做到這一點，但我還不能肯定是如何當你只有通過要添加的數據。

我不工作思路是：

void BinaryTreeNode::add(Data * newData) { 
    BinaryTreeNode * temp = this; 
    if (temp == NULL) { 
     temp->nodeData = newData; 
    } else { 
     if (newData->compareTo(nodeData) < 0) { 
      temp->left->add(newData); 
     } else { 
      temp->right->add(newData); 
     } 
    } 
}

來源

2011-10-16 HJM

沒有很好的理由來編輯你的問題以外的代碼。 – ildjarn

要設置臨時到此，然後比較爲NULL。這不應該是NULL。您需要檢查左側和右側是否爲空。

來源

2011-10-16 22:21:32

謝謝，這實際上是我剛纔意識到的，並且我運行了它。 – HJM

那麼一個二叉樹，至少我如何知道如何實現包含兩個對象，一個包含treenode對象，另一個充當整個樹的接口。

class cBinaryTree { 

public: 
bool insert(int inData); 
//Other operations 

private: 
cBinaryTreeNode* root; 
bool leftInsertion; 
cBinaryTreeNode* getRoot() { return root; }

由於您正在比較輸入數據的實際值並相應地放置它，因此這符合二叉搜索樹的要求。然後插入函數可以寫成

bool cBinaryTree::insert(int inData) { 

//handle case if its first node. 
cBinaryTreeNode *Parent = getInsertionNodePosition(getRoot(), inData); 
cBinaryTreeNode *newNode = createNewNode(inData); 

if(leftInsertion) //insert into left. add return statement 
    Parent->setLeftChild() = newNode; 
else //insert into right 
}

遞歸查詢功能將會像

cBinaryTreeNode* getInsertionNodePosition(cBinaryTreeNode* node,int inData) { 

//Check left subtree and proceed from there. 
if(inData < node->getData()) { 
    if(node->getLeftChild() == NULL) {    
     leftInsertion = true; 
     return node; 
    } 
    else { 
     node = node->getLeftChild(); 
     return getInsertionNodePosition(node, inData); 
    } 
} 
    //Similarly Check right subtree.

希望這有助於。

來源

2011-10-17 00:24:18 vishakvkt

二叉搜索樹插入C++植根於當前節點

回答

相關問題