Вставка бинарного дерева поиска C ++ с корнем в текущем узле - PullRequest
Новая
       34

Вставка бинарного дерева поиска C ++ с корнем в текущем узле

0 голосов
/ 17 октября 2011

Мне нужно добавить элемент в двоичное дерево, учитывая только элемент, который будет добавлен.

Вот код, который мне дали: 

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

где root - закрытая переменная BinaryTree, определенная как BinaryTreeNode.

Мне нужно реализовать метод: 

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

Ответы [ 2 ]

2 голосов
/ 17 октября 2011

Вы устанавливаете темп для этого и затем сравниваете его с NULL.это никогда не должно быть NULL.Вы должны проверить, являются ли левые и правые значения NULL.

0 голосов
/ 17 октября 2011

Ну, двоичное дерево, по крайней мере, насколько я знаю, как реализовать, включает в себя что-то вроде следующего с двумя объектами, один из которых содержит объект 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.

Надеюсь, это поможет.

...