c++ - 从二叉树中删除并找到一个节点

Question

我正在为普通的二叉树（不是搜索）创建“查找”和“删除”功能。下面是查找函数的代码：

bool Find_Node(FileItem * item, Node *current )  //function starts with root
{
    if (current->getNameItem() == item->getName() )  //getNameItem() retrieves the data name in node.
    {
        currentItem = current;   //I have set currentItem as an attribute ( pointer to a Node ) in the tree class. I created it to point to the node I want to find.
        return true;
    }
    Node* child [2];

    child[0] = current->getLeft();
    child[1] = current->getRight();

    bool res = false;

    for (int i = 0; res == false && i < 2 ; i++) 
    {   
        if(child[i] != NULL)
            res = Find_Node(item, child[i]);
    }
    return res;
}

有没有更好的方法来查找节点？可能有人请帮助我删除功能。

Answer 1

添加基本​​案例NULL以使逻辑简单。

bool Find_Node(FileItem * item, Node *current )
{
    if(current == NULL ) return false;
    if (current->getNameItem() == item->getName() ) {
        currentItem = current;
        return true;
    }
    return Find_Node(current->getLeft()) || Find_Node(current->getRight());
}

void Delete_Node(Node*& current)
{
    if(current == NULL) return;
    Delete_Node(current->getRight());
    Delete_Node(current->getLeft());
    delete current;
    current = NULL;
}

如果我能看到 Node 的实现，我可以告诉你如何实现swap你需要的功能

如果树真的很大，这可能会导致堆栈溢出。但是可以通过将解决方案从递归解决方案更改为迭代解决方案来解决该问题。