使用一维向量实现非二叉树的算法？

Question

树的每个节点可能有任意数量的子节点。我需要一种构建和遍历这样的树的方法，但要使用一维向量或列表来实现。

- GabiMe

---

@Juliano 我希望.. 我的作业日子早已过去了 :) @danben 没有限制。 - GabiMe

它真的必须有任意数量的子节点吗？如果我们可以限制每个节点的最大子节点数，那么就有一个简单的解决方案（尽管随着最大子节点数的增加，它将占用越来越多的内存；这样做的唯一原因是使获取特定节点的时间复杂度为O(1)；否则，内存折衷可能不值得）。 - BlueRaja - Danny Pflughoeft

@BlueRaja 这个解决方案是什么？ - GabiMe

你可以将每个节点存储在数组的位置上，就像在一个完整的n叉树中它所在的位置一样。请参考http://en.wikipedia.org/wiki/Binary_tree#Ahnentafel_list - 这个链接是关于二叉树的，但是将其扩展到n叉树并不困难。 - BlueRaja - Danny Pflughoeft

如果这是你真正想要的，我可以把它作为答案，但我会感到不舒服 - 没有人这样做的原因是你（几乎？）从不需要将随机访问和随机插入结合在数据结构中；如果你需要其中之一，只需使用数组或树。你为什么需要两者？ - BlueRaja - Danny Pflughoeft

Answer 1

如果只能使用一个向量（问题中未指定），且节点不应包含自己的列表，而只有一些指针（向量中的地址），则可以尝试以下操作：

1. 每个节点都保存其兄弟节点的地址
2. 给定节点后的第一个节点（如果它不是其兄弟节点）是其子节点，带有指向第二个子节点等的指针
3. 每个子节点都有自己的子节点

因此，对于这样的树：

A
| \
B  E ___
|\  \ \ \
C D  F G H

你的向量看起来会像这样：

idx:    0 1 2 3 4 5 6 7
nodes:  A B C D E F G H
next:   _ 4 3 _ _ 6 7 _

其中_是空指针。

编辑:
另一种方法:

1. 每个节点都保存其子节点占用的向量区域的地址
2. 子节点相邻
3. 向量中存在空节点，标记兄弟组的末尾

对于该方法给定的树将如下所示:

idx:    0 1 2 3 4 5 6 7 8 9 A B
nodex:  A _ B E _ C D _ F G H _
child:  2   5 8   _ _   _ _ _

这样你就可以轻松地找到任意给定节点的子节点，并重新组织数组，而不必移动所有元素（只需将子节点复制到表格末尾，更新指针并将下一个子节点添加到表格末尾）

- MBO

---

那么在你的例子中，这不会使E成为D的子级吗？ - danben

@danben 只有在从任意随机节点遍历时才会出现这种情况。如果你从根节点（索引0）开始遍历，那么就不可能出现这种情况。虽然这不是理想的解决方案，但这是我在看到这个问题后的第一个猜测。 - MBO

好的，我明白了。不过我仍然认为原帖作者想要一个单一的列表 - 否则你可以为每个兄弟组创建一个列表并完成它。 - danben

这个答案中的两种方法是对偶的。要表示一个n元树，至少需要两个链接：firstChild和nextSibling。（它们在DOM树中可用，在Inform 6文本冒险编程环境中也可用：http://www.inform-fiction.org/manual/html/s3.html#s3_2。）你可以在每个节点中存储这两个链接，也可以只存储其中一个，并让向量的顺序编码另一个链接。 - Jason Orendorff

如果您通过排序存储nextSibling并编码firstChild，则向量是树的深度优先遍历。如果您通过排序存储firstChild并编码nextSibling，则向量是树的广度优先遍历。但无论哪种方式，任何编辑都将非常麻烦。存储两个链接似乎是最简单的方法。 - Jason Orendorff

Answer 2

你基本上要做的是编写一个内存管理器的开端，通过将向量的元素成对配对到 cons 单元中来实现 Lisp 解释器。这是我刚刚用 C 拼凑出来的东西：

#include <stdbool.h>
#include <iso646.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define MEMORY_SIZE 1024
#define NIL 0
#define IVAL_MASK 0x8000000

struct pair
{
    bool allocated;
    size_t first;
    size_t second;
};

size_t allocate_pair(struct pair vector[])
{
    for (size_t i = 1; i < MEMORY_SIZE; i++)
        {
            if (not vector[i].allocated)
                {
                    vector[i].allocated = true;
                    return i;
                }
        }

    return NIL;
}

size_t make_pair(struct pair vector[], size_t a, size_t b)
{
    size_t the_pair = allocate_pair(vector);

    if (the_pair != NIL)
        {
            vector[the_pair].first = a;
            vector[the_pair].second = b;
            return the_pair;
        }
    else
        {
            fprintf(stderr,
                    "Out of pairs -- make_pair(%p, %zu, %zu)",
                    vector,
                    a,
                    b);
            exit(EXIT_FAILURE);
        }
}

size_t first(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].first;
}


size_t second(struct pair vector[], size_t index)
{
    assert(vector[index].allocated);

    return vector[index].second;
}

void print_pair_aux(struct pair[], size_t, size_t);
void print_pair(struct pair vector[], size_t p)
{
    assert(vector[p].allocated);

    size_t a = first(vector, p);
    size_t b = second(vector, p);

    printf("(");

    print_pair_aux(vector, a, b);

    printf(")");
}

void print_pair_aux(struct pair vector[], size_t a, size_t b)
{
    if (a == NIL)
        printf("NIL");
    else if (a >= IVAL_MASK)
        printf("%zu", a &~ IVAL_MASK);
    else
        print_pair(vector, a);

    if (b == NIL)
        printf("");
    else if (b >= IVAL_MASK)
        printf(" . %zu", b &~ IVAL_MASK);
    else
        {
            printf(" ");
            print_pair_aux(vector,
                           first(vector, b),
                           second(vector, b));
        }

}

int main(void) 
{
    struct pair *vector = calloc(MEMORY_SIZE, sizeof *vector);

#define cons(A,B) make_pair(vector, (A), (B))
#define ival(x) ((x) | IVAL_MASK)

    size_t a = cons(ival(3), cons(ival(4), NIL));
    size_t b = cons(ival(2), cons(a, NIL));
    size_t c = cons(ival(6), cons(ival(7), cons(ival(8), NIL)));
    size_t d = cons(ival(5), cons(c, NIL));
    size_t e = cons(ival(1), cons(b, cons(d, NIL)));

    print_pair(vector, e);
    puts("");
}

$ cc -std=c99 try.c
$ ./a.out
(1 (2 (3 4)) (5 (6 7 8)))

以上内容与编程有关。

- Nietzche-jou

Answer 3

用数组存储完全二叉树（如用于二叉堆实现）的标准方式非常好，因为您可以使用按层级遍历树的顺序来表示树的元素数组。使用该方案，有快速的技巧来计算父节点和子节点的位置。将树转换为每个节点可以具有任意数量元素的树会使这种方案变得复杂。

然而，有几种方案可以将任意树表示为二叉树。它们在Donald Knuth的《计算机程序设计艺术》第一卷第2.3节中详细讨论。

如果允许节点本身包含指针，则可以为每个节点存储子索引列表。在您的情况下是否可能呢？

- PeterAllenWebb

---

如果这些树是二叉树，这个问题会容易得多。但你的答案归结为“去读 Knuth”，这并没有什么帮助。 - danben

我的回答中有用的部分是要注意所有树都可以表示为二叉树，这不一定显而易见，并提供一个方案的来源来完成它。有很多种方法，哪种最好取决于提问者的要求。 - PeterAllenWebb

“去读 Knuth” 是解决大多数生活问题的答案。除了人际关系问题可能不适用。 - Trevoke

Answer 4

你可以使用一维链表来实现它，开销很小。

每个父节点都包含指向其子节点的指针。（但这需要事先确定节点的最大数量）。

对于以A为根节点，B、C、D为子节点的树，其表示如下。

A -> B A -> C A -> D

请注意，从A有3个链接。

克服节点数量上限的一种方法是在节点中添加额外的指针。

因此，现在A ->(child) B ->(adj) ->(adj) C ->(adj) -> D。

在删除发生时更新树相当复杂。

如果您能告诉各种操作的时间界限，那么设计更好的数据结构甚至更容易。

- Boolean

Answer 5

如果节点的值没有限制，并且假设您只能使用单个列表，我会按以下方式构建它：

将每个节点表示为(val; [int; ...])，其中val是节点的值，每个int是其子节点在列表中的位置。如有必要，可以使用不可打印的分隔符。

遍历速度非常慢。

- danben