c - 使用先序遍历从二叉树创建链表

Question

我想在二叉树上进行预序遍历时将元素添加到链接列表中。我不想破坏BT，只是复制一个链表中的元素。这是我的代码片段。

void Preorder(treeNode *node, Nodelist * head){
    if(node==NULL){
        return;
    }
    //printf("%d\n", node->data);
    head = List_insert(head, node->data);
    Preorder(node->left, head);
    Preorder(node->right, head);
}

Nodelist * List_insert(Nodelist * head, int v)
{
    Nodelist * p = Node_construct(v);
    p->depth = 2222;
    p -> next = head;
    return p;
}

void List_print(Nodelist * head)
{
    while (head != NULL)
    {
        printf("%d ", head -> value);
        printf("%d ", head -> depth);
        printf("\n");
        head = head -> next;
    }
    printf("\n\n");
}

treeNode * Insert(treeNode *node,int data)
{
        if(node==NULL)
        {
                treeNode *temp;
                temp = (treeNode *)malloc(sizeof(treeNode));
                temp -> data = data;
                temp -> left = temp -> right = NULL;
                return temp;
        }

        if(data >(node->data))
        {
                node->right = Insert(node->right,data);
        }
        else if(data < (node->data))
        {
                node->left = Insert(node->left,data);
        }
        return node;

}

int main(int argc, char**argv) {
        treeNode *root = NULL;
        root = Insert(root, 14);
        root = Insert(root, 15);
        root = Insert(root, 4);
        root = Insert(root, 9);
        root = Insert(root, 7);
        root = Insert(root, 18);
        root = Insert(root, 3);
        root = Insert(root, 5);
        root = Insert(root, 16);
        root = Insert(root, 20);
        root = Insert(root, 17); 

        Nodelist * head = NULL;
        Preorder(root, head);
        List_print(head);

    return 0;
}

上面的代码没有打印任何内容。我认为问题在于使用 head = List_insert(head, node->data);在预订功能中。如有任何帮助，我们将不胜感激。

Answer 1

您将 NULL 传递给 Preorder 作为列表头。这是按值传递的，您不能以这种方式更改主函数中的头部。相反，像这样定义 Preorder:

void Preorder(treeNode *node, Nodelist **head)

这样你就可以做到:

*head = Linst_insert....

在函数内部修改列表。当然，您需要从 main 函数中调用 preorder，如下所示:

Preorder(root, &head);