tree/linked 列表结构中的遍历

Question

它有点像混合 tree/linked 列表结构。这是我定义结构的方式

struct node {
    nodeP sibling;
    nodeP child;
    nodeP parent;
    char name[100];    
};

一个节点有一个child，连接到一个链表。链表上的其他元素可能有自己的 child 连接到链表或本身

现在回答我的问题，我将如何遍历这个结构来搜索和打印到特定节点的路径。

如有任何建议，我们将不胜感激。谢谢

更新这是 printPath 函数：

//node -> root of the tree
//current = this is the node that i need to print path to

void printPath(nodeP node, nodeP current){ 

    if (node != NULL){
        if ((strcmp(node->name, current->name) == 0))
        {
            printf("%s/", node->name);
            return; //it returns to the previous recursive call and then continues until the node is null
        }
        printPath(root->childDir, currentDir);
        printPath(root->sibling, currentDir);
        printf(" %s/", node->name);
    }
}

我的问题是退出递归调用，一旦完成打印到当前节点的路径。

Answer 1

问题中的节点结构与使用名称 child 和 sibling 而不是传统的 left 和 [=14= 的常规二叉树相同]. 如果要打印到所需节点的路径，则应打印包含该节点的每个 subtree 的 root 值。所以这是伪代码：

function printPath(root, searchName)
    if root is null
         return false
    if root.name is searchName or 
       printPath(root.child, searchName) or
       printPath(root.sibling, searchName) then
         print root.name
         return true
    else
        return false

在这里，如果 root 为 null，则它不包含所需的节点，因此我们 return false 对于此路径不打印任何内容。但是如果它的名字是我们想要的，或者它的一个子树包含我们想要的，我们打印名字并且 return 为真。这样你就会得到按照从叶子到根的顺序打印的路径。

tree/linked 列表结构中的遍历

Traversal in tree/linked list structure

c

data-structures

linked-list

binary-search-tree

traversal