c - 将二分查找展平为单链表 [C]

Question

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

二叉搜索树：

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

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

score 6 · Accepted Answer

这是相对简单的递归执行：

检查左边的节点；如果那里有东西，请将左侧展平到列表 #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;
}

score 3 · Accepted Answer

您需要按顺序进行遍历，将每个元素依次添加到列表中。

这个的伪代码是：

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.

就是这样，就这么简单。第一步，处理左子树。第二步，添加数据。第三步，处理右子树。

唯一的“聪明”位是以使代码简洁的方式正确处理空子树。

请记住，为了获得最大效率，如果指向最终元素（尾部）的指针未缓存在某处，则附加到链表可能是一项相对昂贵的操作。这将需要为每个添加的元素找到尾部，这会将你的展平算法变成一个。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)。

score 1 · Accepted Answer

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

score 0 · Accepted Answer

如果有人感兴趣，下面是 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;
}

score 0 · Accepted Answer

我们可以使用递归，为树中的每个级别构建一个链表，并将该列表添加到列表向量中。使用此解决方案，我们需要跟踪我们所在的级别，因此，如果我们已经有一个级别的链接列表，并且我们访问了访问级别上的节点，然后我们就可以添加到该列表中。

我没有为我自己的节点类添加任何代码，因为它与问题无关，也没有演示内存清理，但是更好的解决方案是使用 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<<" ";
}

score 0 · Accepted Answer

这里的问题也有非递归解决方案。

它为您提供 O(n) 时间复杂度和 O(1) 空间复杂度。使用递归解决方案，如果您将其应用于自己的输出以获取大节点集，则可能会出现堆栈溢出。

score 0 · Accepted Answer

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

   }

c - 将二分查找展平为单链表 [C]

7 回答 7

Related

Reference