时间戳

首页 > 解决方案 > 在 C 中使用递归 DFS 返回节点本身

c - 在 C 中使用递归 DFS 返回节点本身

问题描述

我想编写一个搜索树的递归，寻找具有适当数据的节点，然后返回节点本身。我需要节点本身，因为然后我将使用该节点继续构建树。我已经尝试过这个函数的许多版本，但下面的代码是我最接近的。请注意，我将一般树表示为二叉树，如此处所述，因此我认为出于所有意图和目的，这可以视为二叉树。

struct node {
     int id;
     struct node *firstChild;
     struct node *nextSibling;
};

struct node* findNode(struct node* node, int id) {
     if (node->id == id) 
          return node;

     if (node->firstChild != NULL)
          return findNode(node->firstChild, id);

     if (node->nextSibling != NULL)
          return findNode(node->nextSibling, id);

     return node;
}

我了解此代码的问题：如果存在左（子）分支并且所需的节点不在该分支中，则它返回该分支的叶子而不是探索右分支。我知道我的代码有太多的返回语句；我尝试过其他回报较少的版本，但没有找到有效的功能。

提前致谢。

标签： calgorithmbinary-tree

解决方案

对于初学者来说，结构定义中有一个错字

struct node {
     int id;
     int node *firstChild;
     int node *nextSibling;
};

看来你的意思

struct node {
     int id;
     struct node *firstChild;
     struct node *nextSibling;
};

您的函数不检查指向节点的当前指针是否等于 NULL。

该函数可以通过以下方式定义

struct node * findNode( struct node *node, int id ) 
{
    if ( node == NULL || node->id == id )
    {
        return node;
    }

    struct node *target = findNode( node->firstChild, id );

    if ( target == NULL )
    {
        target = findNode( node->nextSibling, id );
    }

    return target;
}

虽然在 C 中没有函数重载，但函数应该像这样声明和定义

struct node * findNode( const struct node *node, int id ) 
{
    if ( node == NULL || node->id == id )
    {
        return ( struct node * )node;
    }

    struct node *target = findNode( node->firstChild, id );

    if ( target == NULL )
    {
        target = findNode( node->nextSibling, id );
    }

    return target;
}

推荐阅读