二叉搜索树插入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++植根于当前节点

回答

相关问题