c++ - 如何获取n叉树中的元素

Question

我遇到了一个关于 n 元树的问题。给定根指针和元素名称，我想获取元素的指针。我尝试递归地编写它，但出现段错误。

Node* findNode(Node* ptr, const string& name)
{   
    if(ptr->getNextSibling() == NULL)
        return NULL;
    if(ptr->getFirstChild() == NULL)
       return NULL;

    if(ptr->getName() == name)

            return ptr;     
    else
    {
        findNode(ptr->getNextSibling(), name);
        findNode(ptr->getFirstChild(), name);   
    }   

}

n 叉树由指向其下一个子节点的指针、指向其下一个兄弟节点的指针、指向根节点和数据的指针组成。

Answer 1

基本的二分搜索看起来有点像这样:

Node* findNode(Node* ptr, const string& name)
{   
    if(ptr == NULL)
        return NULL;

    if(ptr->getName() == name)
        return ptr;     

    Node *pTarget = findNode(ptr->getLeftChild(), name);
    if (pTarget == NULL)
        pTarget = findNode(ptr->getRightChild(), name);   

    return pTarget;  // might be NULL
}

n 元搜索可能看起来更像这样:

Node* findNode(Node* ptr, const string& name)
{   
    if(ptr == NULL)
        return NULL;

    if(ptr->getName() == name)
            return ptr;   

    for (Node *pChild=ptr->getFirstChild(); 
         pChild!=NULL; 
         pChild=pChild->getNextSibling())
    {
        Node *pTarget = findNode(pChild, name);
        if (pTarget != NULL)
            return pTarget;
    }

    return NULL;  
}

我没有对此进行编译或测试，但我认为算法还可以(尽管不是最优的)。