c - 如何从二叉树制作链表(前/后顺序)

我已经浏览了几个问题，但似乎无法弄清楚发生了什么。我试图将我的二叉树转换为以前后顺序排列的链表。我的代码返回了一个由零组成的链表。我排除了后置订单代码，因为在这种情况下它与pre基本上相同。这是我的相关代码：

typedef struct list {
    int data;
    struct list *next;
} List;

List* createNode(int data)
{
    // create node in memory
    List* list = malloc(sizeof(list));
    // init parameters
    list->data = data;
    list->next = NULL;
}

void printList(List *list)
{
    //if(list->next == NULL) printf("y");
    while(list != NULL) {
        printf("%d", list->data);
        list = list->next;
    }
}

void preOrder(node *tree, List *list)
{
    if(tree == NULL) return;
    // visit root
    list = createNode(tree->data);
    // left
    preOrder(tree->left, list->next);
    // right
    preOrder(tree->right, list->next);
}

int preL(node *a)
{
    // create preList
    List *preList = malloc(sizeof(List));
    preOrder(a,preList);
    printList(preList);
}

最佳答案

您在理解列表的工作方式时遇到一些错误：


list*是指向列表中第一个元素且仅指向第一个元素的指针
将元素添加到列表的末尾时，应循环列表以将元素添加到列表的末尾。这意味着您必须更新list->next


在您的预订代码中，您不会更新新创建的list的下一个指针。
本质上，您是用一个新节点覆盖list变量，从而失去了所有其他处理过的节点。



上面的方法效率不高，因为每次插入注释时，我们都必须传递列表中的所有节点。

修改后的代码：

void insertList(List *list,List *element)
{
    while(list->next != NULL) {
        printf("%d", list->data);
        list = list->next;
    }
    list->next=element;
}
void preOrder(node *tree, List *list)
{
    if(tree == NULL) return;
    // visit root
    // the new element
    List *element = createNode(tree->data);
    //insert to the tail of the list
    insertList(list,element);
    // left
    // pass the initial list with the head inserted
    preOrder(tree->left, list);
    // right
    // pass the initial list with the head inserted and the left tree nodes
    preOrder(tree->right, list);
}

int preL(node *a)
{
    // create preList
    List *preList = malloc(sizeof(List));
    preOrder(a,preList);
    printList(preList);
}

为了使代码高效，您每次插入元素时都不得循环列表。
尝试自己动手！（提示：您可以保留指向最后一个元素的指针：）。