0

我已经查看了几个问题，但我似乎无法弄清楚发生了什么。我正在尝试将我的二叉树转换为前/后顺序的链表。我的代码返回一个由零组成的链表。我排除了 post-order 的代码，因为在这种情况下它与 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);
}
4

2 回答 2

0

您的函数仅分配节点，但从不将它们返回给调用者。我会这样写：

void slist_add(struct list *head, struct list **root)
{
     head->next = *root;
     *root = head;
}

struct list **preOrder(node *tree, List **list)
{   
    struct list *node;

    if (tree == NULL)
        return list;

    node = createNode(tree->data);
    slist_add(node, list);

    list = &list->next;    
    list = preOrder(tree->left, list);
    list = preOrder(tree->right, list);

    return list;
}

并将其称为

List *preList = NULL;
preOrder(a, &preList);
于 2018-04-01T19:27:54.150 回答
0

您在理解列表的工作方式方面存在一些错误：

  1. list*是指向列表中第一个元素且仅指向第一个元素的指针
  2. 将元素添加到列表的尾部时，您应该循环列表以便将元素添加到列表的后面。这意味着您必须更新list->next
    • 在您的预购代码中，您不会更新 new created 的 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);
}

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

于 2018-04-01T19:35:46.250 回答