将二进制搜索展平为单链表
我试图将二进制搜索树展平为单链表。
二叉搜索树：
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) { ... }
我似乎无法弄清楚如何将其展平为单链表。 我已经看到很多其他线程和站点讨论将二进制搜索树转换为双向或循环链表，但没有关于将值复制到单链表中的问题。 如果有人能提出如何实现这一点的建议，我将非常感激。 这是一个家庭作业，所以如果你也可以提供一个小的解释，以帮助我了解这将是伟大的。
这是递归执行相对简单的：
- 检查左侧的节点; 如果那里有东西，将左边展平到列表＃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; }
您需要进行有序遍历，将每个元素依次添加到列表中。
伪代码是：
def traverse (node, list): if node == NULL: return # Ignore empty subtrees. traverse (node.left, list) # Do left subtree first. list.append (node.data) # Then current node. traverse (node.right, list) # Then right subtree. list = new List() # Create empty list. traverse (root, list) # Collapse tree to list.
就是这样，尽可能简单。 步骤1，处理左子树。 第2步，添加数据。 第3步，处理正确的子树。
唯一的“聪明”位是以一种使代码简洁的方式正确处理空子树。
请记住，为了获得最大效率，如果指向最终元素（尾部）的指针未在某处缓存，则附加到链接列表可能是相对昂贵的操作。 这将需要为每个添加的元素找到尾部，这将使您的展平算法变为O(n 2 ) 。
因为在链表的开头插入一个元素几乎总是O(1) ，因为你必须保持一个head指针，所以反向有序遍历通常更有效：
def traverse (node, list): if node == NULL: return # Ignore empty subtrees. traverse (node.right, list) # Do right subtree first. list.insert (node.data) # Then current node at list start. traverse (node.left, list) # Then left subtree.
这使展平操作保持在O(n) 。
Why dont you do inorder traversal and add values to list in a way. public List inorderToList(TreeNode node, List 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; }
如果有人感兴趣，下面是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; }
我们可以使用recurssion来为树中的每个级别构建链接列表，并将列表添加到列表向量中。 使用此解决方案，我们需要跟踪我们所处的级别，因此，如果我们已经有一个级别的链接列表，我们访问一个访问级别的节点，然后才能添加到该列表。
我没有为我自己的节点类添加任何代码，因为它与问题无关，也没有显示内存清理，但更好的解决方案是使用boost :: shared_ptr来处理清理。
void generateLists(vector* >*& lists, node* root, int level) { //base case if(root == NULL) return; //if we have don't have a linked list at this level so create this if((int)lists->size() == level) { list* ls = new list(); ls->push_back(root); lists->push_back(ls); } else { //re-use existing list list* ls = lists->at(level); if(ls != NULL) ls->push_back(root); } //in order traversal generateLists(lists, root->left, level+1); generateLists(lists, root->right, level+1); } int main(void) { //create a test binary tree node root(6); node n2(3); node n3(9); node n4(2); node n5(5); node n6(8); node n7(9); root.left = &n2; root.right = &n3; n2.left = &n4; n2.right=&n5; n3.left=&n6; n3.right=&n7; //will hold a vector of lists for each level in the tree vector* >* lists = new vector* >(); int level=0; generateLists(lists, &root, level); vector* >::iterator it; //convert each level in the tree to a single linked list list flattened; for(it = lists->begin(); it != lists->end(); it++) { list* linkedList = (*it); list::iterator itNode; for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++) flattened.push_back(*itNode); } //output the tree as a linked list list::iterator itNode; for(itNode = flattened.begin(); itNode != flattened.end(); itNode++) cerr<<(*itNode)->val<<" "; }
这里还有针对这个问题的非递归解决方案。
它为您提供O（n）时间复杂度和O（1）空间复杂度。 使用递归解决方案，您可以获得堆栈溢出，例如，您将其应用于自己的输出以获取大型节点集。
private static BSTNode head; private static BSTNode tail; public static void inorderTraversal(BSTNode node) { if(node.left != null) { inorderTraversal(node.left); } System.out.print(node.data + " "); constructLinkedList(node.data); if(node.right != null) { inorderTraversal(node.right); } } public static void constructLinkedList(int data) { if(head == null) { head = new BSTNode(data); head.left = null; tail = head; } else { BSTNode node = new BSTNode(data); tail.right = node; tail.left = null; tail = node; } } public static void linkedListToString() { BSTNode curr = head; StringBuilder sb = new StringBuilder(); sb.append("["); while(curr.right != null) { sb.append(curr.data).append("->"); curr = curr.right; } if(curr.right == null) sb.append(curr.data).append("->NULL"); sb.append("]"); System.out.print(sb.toString()); }