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 功能

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