展平二分搜索以按顺序排列单链表[C]
展平二分搜索以按顺序排列单链表[C]
提问于 2013-04-11 10:10:47
我正在尝试将一个二进制搜索树扁平化为一个单链表。
二叉搜索树：
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) {
...
}我似乎就是想不出如何把它扁平化成一个单链表。我见过许多其他的线程和站点讨论将二叉树转换为双向或循环链表，但没有一个讨论将值复制到单链表中。如果有人能就我如何做到这一点提供建议，我将不胜感激。这是一个家庭作业，所以如果你也能提供一个小的解释来帮助我学习，那就太好了。
回答 6
Stack Overflow用户
回答已采纳
发布于 2013-04-11 10:23:03
这是相对简单的递归操作：
- 检查左侧的节点；如果有内容，将左侧展平为列表#1
- 检查右侧的节点；如果有内容，展平右侧的列表#2
- 使用当前代码的键创建单节点列表#3列表按顺序#1 -> #3 -> #2
- 返回连接的列表作为结果
<代码>F211
下面是如何对其进行编码：
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;
}Stack Overflow用户
发布于 2014-08-03 11:00:12
Why dont you do inorder traversal and add values to list in a way.
public List<Integer> inorderToList(TreeNode<Integer> node, List<Integer> list) {
if(node == null) {
return list;
}
if (node != null) {
list = inorderToList(node.getLeft(), list);
list.add(node.getValue());
list = inorderToList(node.getRight(), list);
}
return list;
}Stack Overflow用户
发布于 2014-02-27 13:24:46
如果有人感兴趣，下面是Java代码：
public static Node bTreeToLinkedList(TreeNode root) {
Node list1 = root.getLeftChild() != null ? bTreeToLinkedList(root.getLeftChild()) : null;
Node list2 = root.getRightChild() != null ? bTreeToLinkedList(root.getRightChild()) : null;
Node list3 = ll.new Node((int) root.getData());
list3.setNext(list2);
if (list1 == null)
return list3;
Node last = list1;
while (last.getNext() != null)
last = last.getNext();
last.setNext(list3);
return list1;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15939582
复制相关文章
相似问题
腾讯云开发者
