将二分查找展平为单向链表 [C] [英] Flatten binary search to in order singly linked list [C]

问题描述

我正在尝试将二叉搜索树展平为单向链表.

I am trying to flatten a binary search tree to a singly linked list.

二叉搜索树:

      6
    /   
   4     8
  /      
 1  5     11
         / 
       10

扁平单向链表:

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

由于某种原因，我似乎无法弄清楚这一点.

I can't seem to figure this out for some reason.

我有一个树节点的结构:

I have a struct for the tree nodes:

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

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

I have a function to create and allocate memory to the tree node:

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

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

I have a struct for the list nodes:

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

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

I have a function to create the list node:

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

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

And I have working functions to create the binary search tree, to insert the values, etc., but now I need to create a function to flatten the tree to a list.

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

我似乎无法弄清楚如何将其展平为单向链表.我已经看到很多其他线程和站点讨论将二叉搜索树转换为双向或循环链表，但没有将值复制到单向链表中.如果有人能就我如何完成这项工作提出建议，我将不胜感激.这是一个家庭作业，所以如果你也能提供一个小的解释来帮助我学习，那就太好了.

I just can't seem to figure out how to flatten it to a singly linked list. I have seen a lot of other threads and sites discussing a conversion of a binary search tree to a doubly or circular linked list, but none about copying the values into a singly linked list. If anyone can offer up suggestions on how I can accomplish this I would really appreciate it. This is for a homework assignment, so if you can also provide a small explanation to help me learn that would be great.

推荐答案

这个比较简单的递归实现:

This is relatively simple to do recursively:

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

您可以通过以下方式对其进行编码:

Here is how you can code it up:

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;
}

这篇关于将二分查找展平为单向链表 [C]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！