展开二进制搜索到单链表[C]

二叉搜索树：

扁平单链表：

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

我似乎无法弄清楚如何将它扁平化为一个单独的链表。我已经看到很多其他线程和站点讨论将二叉搜索树转换为双向链表或循环链表，但没有关于将值复制到单个链接列表中的问题。如果任何人都可以提出建议，我可以如何完成这一点，我会非常感激。这是一个家庭作业的任务，所以如果你还可以提供一个小的解释来帮助我学习这将是伟大的。

来源

2013-04-11 kyle

查找 “中序遍历”。 – 2013-04-11 02:12:14

@CarlNorum我实际上试图使用inorder遍历实现扁平化，但我无法弄清楚要在哪些位置设置列表，以及在哪里创建新的列表节点。 – kyle 2013-04-11 02:23:04

这是比较简单的递归做：

检查左侧的节点;如果有什么东西，请将左侧展平为列表＃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; 
}

来源

2013-04-11 02:23:02 dasblinkenlight

非常感谢您的帮助。我试图解决它的方式是远离目标。我甚至没有考虑制作多个列表节点。 – kyle 2013-04-11 02:35:47

你需要做一个中序遍历，将每个元素依次与名单。

这种情况的伪代码：

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²)。

因为在插入的元素开始链表几乎总是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)。

来源

2013-04-11 02:23:10 paxdiablo

下面是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; 
}

来源

2014-02-27 05:24:46 mihirk

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

来源

2014-08-03 03:00:11 plzdontkillme

抱歉没有意识到你想在链接列表中。对不起，关于 – plzdontkillme 2014-08-03 03:01:18

，我们建立一个链表树中的每个级别和列表添加到列表中的一个载体，我们可以使用recurssion。有了这个解决方案，我们需要跟踪我们所处的级别，所以如果我们已经有一个链接列表用于一个级别，并且我们访问访问级别上的一个节点，然后才可以添加到该列表。

我没有为自己的节点类添加任何代码，因为它与问题不相关，也没有内存清理正在演示，但更好的解决方案是使用boost :: shared_ptr来处理清理。

void generateLists(vector<list<node*>* >*& 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<node*>* ls = new list<node*>(); 
     ls->push_back(root); 
     lists->push_back(ls); 
    } 
    else 
    { 
     //re-use existing list 
     list<node*>* 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<list<node*>* >* lists = new vector<list<node*>* >(); 
    int level=0; 
    generateLists(lists, &root, level); 
    vector<list<node*>* >::iterator it; 

    //convert each level in the tree to a single linked list 
    list<node*> flattened; 
    for(it = lists->begin(); it != lists->end(); it++) 
    { 
     list<node*>* linkedList = (*it); 
     list<node*>::iterator itNode; 
     for(itNode = linkedList->begin(); itNode != linkedList->end(); itNode++) 
      flattened.push_back(*itNode); 
    } 

    //output the tree as a linked list 
    list<node*>::iterator itNode; 
    for(itNode = flattened.begin(); itNode != flattened.end(); itNode++) 
     cerr<<(*itNode)->val<<" "; 
}

来源

2015-01-10 13:19:18 gilla07

注意：问题是关于'C' c没有模板也没有迭代器。 – wildplasser 2015-01-10 13:28:07

对于问题here也存在非递归解决方案。

它给你的O（n）的时间复杂度和O（1）空间复杂度。使用递归解决方案，你可以获得堆栈溢出，例如，你将它应用到它自己的输出中，以用于大节点集。

来源

2015-03-16 10:54:00 Alexey

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()); 

    }

来源

2018-01-20 20:38:34 user525146

展开二进制搜索到单链表[C]

回答

相关问题