将二进制搜索展平为单链表[C]

Question

我试图将二进制搜索树展平为单链表.

二叉搜索树:

      6
    /   \
   4     8
  / \     \
 1  5     11
         / 
       10

扁平化单链表:

1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11

出于某种原因,我似乎无法解决这个问题.

我有一个树节点的结构:

typedef stuct node {
    int key;
    struct node *left;
    struct node *right;
} Node;

我有一个函数来创建和分配内存到树节点:

Node* newNode (int key) {
    Node *new = malloc (sizeof(Node));
    new->left = NULL;
    new->right = NULL;
    new->key = key;
    return new;
}

我有一个列表节点的结构:

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

我有一个函数来创建列表节点:

List* newListNode (int key) {
    List *new = malloc(sizeof(List));
    new->key = key;
    new->next = NULL;
    return new;
}

我有工作函数来创建二叉搜索树,插入值等,但现在我需要创建一个函数来将树展平为列表.

List* flattenToLL(Node* root) {
    ...
}

我似乎无法弄清楚如何将它展平为单链表.我已经看到很多其他线程和站点讨论将二进制搜索树转换为双向或循环链表,但没有关于将值复制到单链表中的问题.如果有人能就如何实现这一目标提出建议,我将非常感激.这是一个家庭作业,所以如果你也可以提供一个小的解释,以帮助我了解这将是伟大的.

Answer 1

这是递归执行相对简单的:

• 检查左侧的节点; 如果那里有东西,将左边展平到列表#1
• 检查右边的节点; 如果那里有东西,将权利压平到列表#2
• 使用当前节点的密钥创建单节点列表#3
• 按顺序#1 - >#3 - >#2连接列表
• 返回连接列表作为结果

以下是编码方式:

List* flattenToLL(Node* root) {
    List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
    List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
    List *list3 = newNode(root->key);
    // The "middle" list3 cannot be NULL; append list2 to list3
    list3->next = list2; // If list2 is NULL, it's OK
    if (!list1) return list3; // Nothing to prepend
    List *last = list1;
    while (last->next) last=last->next; // Go to the end of list1
    last->next = list3; // Append list3+list2 to the end of list1
    return list1;
}