拼合二进制搜索，以单链表[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.

我对树节点的结构：

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) {
    ...
}

我似乎无法弄清楚如何将它展平到一个单向链表。我已经看到了很多其他线程和讨论二叉搜索树的转换为双向或循环链表的网站，但没有有关复制值到一个单向链表中。如果任何人都可以提供多达我如何能做到这一点我真的AP preciate它的建议。这是一个家庭作业，因此，如果您也可以提供一个小的解释，​​帮助我学习，这将是巨大的。

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


• 返回连接列表作为你的结果

下面是你如何code起来：

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屋！