使用Preorder Traversal從二叉樹製作鏈表

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作爲列表頭傳遞給預訂。這是通過值傳遞的，你不能通過這種方式改變主函數中的頭部。相反定義預購是這樣的：

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

所以，你可以這樣做：

*head = Linst_insert.... 

在函數內部修改的列表。當然，你需要從main函數調用序是這樣的：

Preorder(root, &head); 

Answer 2

嘗試......希望可以幫助

Nodelist *Preorder(treeNode *node, Nodelist ** tail) { // use name 'tail' instead of 'head' because you are inserting on the tail, but this functions returns head.. 

    Nodelist *head; 

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

Nodelist * List_insert(Nodelist ** tail, int v) 
{ 
    Nodelist * p = Node_construct(v); 
    p->depth = 2222; 
    p->next = NULL; 
    if (!tail) { 
     *tail = p; // (*tail) is NULL, true when first time List_Insert called 
    } 
    else { 
     (*tail)->next = p; 
    } 
    return p; 
} 

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; 
     head = Preorder(root, &head); 
     List_print(head); 

    return 0; 
}