给出了一个树结构，你如何使用递归将它变成一个简单的链接列表？

Question

给定一个二叉树（只有左右孩子），你如何编写一个递归函数使它成为一个简单的链接列表就地？ （不应该创建新的数据结构，伪代码可以）。假设每个节点都有一个整数值，如123或2或3.最终链接列表应该包含树中的所有节点。顺序并不重要。

更新：需要在原地。不应该创建新的数据结构。

Answer 1

总是有不同的方式来遍历一棵树，因为有：

• 序
• 预购
• 后序

您可以选择它们来形成你的列表...

例如（伪代码，PreOrder）：

function treeToList(LinkedList l, Tree t) 
    if(t not nil) 
     l.add(t.element) 
     treeToList(l, t.Left) 
     treeToList(l, t.Right) 
    endif 
end function 

Remenber：如果您在二叉搜索树上执行了InOrder，您将按照排序顺序获取元素。

Answer 2

你真的在问我如何走一棵二叉树。答案可以在任何关于算法和数据结构的书中找到。

Answer 3

不要粗鲁，但这听起来有点像功课。我给出一个描述作为答案：

• 您为结果创建一个空链表。

• 建立一个帮助函数，它需要一个链表和一个节点。

• 的辅助函数应该添加子节点（如果有的话）的列表和递归调用本身的子节点（如果有的话）。

• 将根节点添加到结果列表中。

• 呼叫根节点辅助功能和结果列表。

• 返回结果列表给调用者。

当然也有很多关于这个维基百科：binary trees和tree traversal。

编辑：还是看凯文张贴:-)

Answer 4

可以“走一棵树”在许多订单伪代码，其中主要有前，后，和有序。下面是一些伪代码的顺序，例如：

def in_walk(tree, doit): 
    if tree is null: return 
    in_walk(tree.left, doit) 
    doit(tree.root) 
    in_walk(tree.right, doit) 

我希望在这个伪代码的假设是显而易见的：一棵树有左，右连杆，它可以为null，意思是“没有更多的是在这儿散步”，并一个根节点;你可以传递一个函数或者闭包，这个函数或者闭包在给定节点参数的情况下进行正确的思考（追加到链表或者其他）。

Answer 5

/* bst.c: sort the input numbers and print them forward and backward with no duplicates */ 

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int key; 
    struct node *left; 
    struct node *right; 
}; 

static struct node **bst_find(struct node **root, int key) { 
    struct node **n; 

    n = root; 
    while (*n != NULL && (*n)->key != key) { 
     if (key < (*n)->key) { 
      n = &(*n)->left; 
     } else { 
      n = &(*n)->right; 
     } 
    } 
    return n; 
} 

static void bst_insert(struct node **root, int key) { 
    struct node **n; 

    n = bst_find(root, key); 
    if (*n == NULL) { 
     *n = malloc(sizeof (**n)); 
     (*n)->key = key; 
     (*n)->left = NULL; 
     (*n)->right = NULL; 
    } 
} 

/* massage the tree rooted at "root" to be a doubly-linked list 
* return the leftmost and rightmost nodes via the parameters "leftend" and "rightend" 
* bst_flatten() is invoked 2N+1 times, where N is the number of tree elements 
*/ 
static long Flatten_count = 0; 
static void bst_flatten(struct node **leftend, struct node **rightend, struct node *root) { 
    Flatten_count++; 
    if (root != NULL) { 
     /* flatten the left side of the tree */ 
     *leftend = root; 
     bst_flatten(leftend, &root->left, root->left); 
     /* if necessary, splice "root" onto the right end */ 
     if (root->left != NULL) { 
      root->left->right = root; 
     } 
     /* flatten the right side of the tree */ 
     *rightend = root; 
     bst_flatten(&root->right, rightend, root->right); 
     /* if necessary, splice "root" onto the left end */ 
     if (root->right != NULL) { 
      root->right->left = root; 
     } 
    } 
} 

int main(void) { 
    int key; 
    long N = 0; 
    struct node *root = NULL; 
    struct node *leftend = NULL; 
    struct node *rightend = NULL; 
    struct node *n; 

    /* read the input into a bst */ 
    while (scanf("%d", &key) == 1) { 
     N++; 
     bst_insert(&root, key); 
    } 
    /* make a list */ 
    bst_flatten(&leftend, &rightend, root); 
    /* traverse the list forward */ 
    for (n = leftend; n != NULL; n = n->right) { 
     printf("%d\n", n->key); 
    } 
    /* traverse the list backward */ 
    for (n = rightend; n != NULL; n = n->left) { 
     printf("%d\n", n->key); 
    } 
    fprintf(stderr, "%ld items input, %ld invocations of bst_flatten()\n", N, Flatten_count); 
    return 0; 
} 

Answer 6

既然你已经标记它作为家庭作业，我就没有源代码或伪代码回复，但有一个更全面的描述。

由于您的树将包含您想要包含在链接列表中的所有值，因此我们必须确保将其全部覆盖。

要做到这一点，我们必须确保我们处理每个叶节点。

要做到这一点，我们需要确保我们处理每个节点的每个左侧和右侧子节点。

让我们从根节点开始，它通常是您在谈论二叉树时参考的根节点。

我假设你知道如何通过顺序追加项目来产生一个链表。

所以处理根节点，我们这样做：

• 如果根包含一个值：追加值列表

这需要照顾的单值的可任选存储在根节点中。一些二叉树只在叶节点（没有子节点的节点）中存储值，大部分存储值也在内部节点中（节点和子节点）。

但是，这当然会让我们无处可去，因为我们只添加一个项目，我们甚至不知道这个具体值的所有值在哪里，所以它可能是第一个或最后一个或任何值在之间。但是，我们知道如果根节点在左边的“方向”上有子节点，那么我们可能在所有这些节点中找到的任何值都将位于根节点中的节点之前。

而且我们也知道，如果根节点的子节点处于正确的“方向”，那么这些值将会在它之后出现。

所以我们可以做的是：

• 过程中左子树
• 所有节点附加价值的节点
• 过程的所有节点的右子树

这种方法假定：

• 节点值是有序的（即。左子树出现在节点本身的值之前）
• 你希望在他们有序序列值

如果定义了上述方法的方法，你就会有这样的事情：

to process a node, do this: 
    first process the left-child sub-node, if present 
    then append the value of the node, if any 
    then process the right-child sub-node, if present 

在上面的伪代码，在您看到单词“过程”的地方，您将相同的过程应用于上述节点。

这里的C＃代码来处理一个简单的二进制树并追加结果到给定链表：

public void AppendTreeToLinkedList<T>(Node<T> node, LinkedList<T> list) 
{ 
    if (node.LeftChild != null) 
     AppendTreeToLinkedList(node.LeftChild, list); 
    list.Append(node.Value); 
    if (node.RightChild != null) 
     AppendTreeToLinkedList(node.RightChild, list); 
} 

Answer 7

假设树有包含指向所谓左，右节点的节点。我们最终将只使用正确的节点指针。

listify(node) 
    if node has no children 
     return 

    else if node.left == null 
     listify(node.right) 

    else if node.right == null 
     listify(node.left) 
     mode.right = node.left 

    else 
     listify(node.left) 
     listify(node.right) 

     temp = node.left 
     while temp.right != null 
      temp = temp.right 

     temp.right = node.right 

     node.right = node.left 

Answer 8

要获得被以同样的方式进行排序作为原树，C＃代码双重喜欢列表：

function Listify(Node n, out Node First, out Node Last) 
{ 
    if (Node.Left != null) 
    { 
     Node Tmp; 
     Listify(Node.Left, out First, out Tmp); 
     Node.Left = Tmp; 
    } 
    else 
    { 
     First = Node; 
    } 
    if (Node.Right != null) 
    { 
     Node Tmp; 
     Listify(Node.Right, out Tmp, out Last); 
     Node.Right = Tmp; 
    } 
    else 
    { 
     Last = Node; 
    } 
} 

Answer 9

在流程，使用memoized递归，一个按顺序算法将是：

(define (tree->list tree) 
    (define empty-set (list)) 
    (define (copy-to-list tree result-list) 
    (if (null? tree) 
     result-list 
     (copy-to-list (left-branch tree) 
        (cons (entry tree) 
          (copy-to-list (right-branch tree) 
             result-list))))) 
    (copy-to-list tree empty-set)) 

这假定一个树结构表示为：

(define (entry tree) (car tree)) 
(define (left-branch tree) (cadr tree)) 
(define (right-branch tree) (caddr tree)) 
(define (make-tree entry left right) 
    (list entry left right)) 

N.B.我本来可以使用'()作为empty-set，但是SO会使用块引用代码的颜色编码。