c - 为什么我的二叉树没有正确填充？

Question

我正在寻找一种方法，将字符串按出现顺序填充到我的二叉树中，并按照我将它们输入树中的顺序访问它们。我只是想不出一种方法来创建这样一棵树。

我有一个根节点，它分成两个分支，分支本身也创建了另外两个分支。等等。我想要的只是创建一棵树，如果有意义的话，它会按照我输入的顺序保存我的输入。

我希望树看起来像这样:

    A
   / \
  B   C
 / \ / \
 D E F G

A、B、C、D、E、F、G 等是我需要存储在树中的随机文件名。如何按照随机字符串出现的顺序将其存储在二叉树中？做这样的事情最好的方法是什么？任何帮助将不胜感激。

这是我用 C 编写的代码，但它似乎不起作用。右手边被搞乱了，存储在第一个 B 叶之后。使用带注释的 printf 函数，您可以看到它产生段错误。

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

struct node
{
  char *titel;
  struct node *A;
  struct node *B;
};

int bitPos (int n)
{
  return n & -n;
}

void display(struct node *leaf)
{
if (leaf != NULL)
{
    display(leaf->A);
    printf("%s\n",leaf->titel);
    display(leaf->B);
}
}

void insert(char* titel, struct node **leaf, int nodeCount, int bitPos)
{
if (*leaf == 0)
{
  *leaf = (struct node*)malloc(sizeof(struct node));
  (*leaf)->titel = malloc(strlen(titel)+1);
  strcpy((*leaf)->titel,titel);
  (*leaf)->A = NULL;
  (*leaf)->B = NULL;
}
else
{
 int currentBit = (nodeCount >> bitPos) & 1;
 if (currentBit == 0) {
   // insert to left
   insert(titel, &((*leaf)->A), nodeCount, bitPos - 1);
 }
 else
 {
   // insert to right
   insert(titel, &((*leaf)->B), nodeCount, bitPos - 1);
 }
}
}

int main(int argc, char const *argv[])
{
  struct node *root = 0;
  insert("root",&root,1,bitPos(1));
  insert("chapter_1A",&root,2,bitPos(2));
  insert("chapter_1B",&root,3,bitPos(3));
  insert("chapter_2A",&root,4,bitPos(4));
  insert("chapter_2B",&root,5,bitPos(5));
  insert("chapter_3A",&root,6,bitPos(6));
  insert("chapter_3B",&root,7,bitPos(7));
  insert("chapter_4A",&root,8,bitPos(8));
  insert("chapter_4B",&root,9,bitPos(9));
  display(root);
  //printf("%s\n",root->B->A->titel);
  return 0;
}

输入: 输入如主函数中所示。

root => chapter_1A => chapter_1B => chapter_2A => chapter_2B and so on.

应该输出(没有chapter_):

        root
       /    \
     1A     1B
    /  \    / \
   2A  2B  3A 3B
  /  \
 4A  4B

使用显示函数的程序的实际输出:

chapter_4B
chapter_4A
chapter_2B
chapter_2A
chapter_1A
root
chapter_1B
chapter_3A
chapter_3B

Answer 1

将二叉树用于此特定目的是完全没有意义的。但是，我知道有几种情况，按顺序和存储顺序 indexing很有用，这实际上导致了这种特殊情况下的解决方案。这是:

如果您有一个二叉树，其中第 N 个级别(因此有 2^N-1 个节点)和第 N+1 个级别中的 K 个最左边的节点，则到的路径下一个空闲节点由 K 给出，从最高有效位读取到最低有效位，0 表示左子节点，1 表示右子节点。

你可能不会相信，但这是真的；关键是 K 的变化范围为 0 到 2^N-1。让我帮您验证上述说法，并解决上述问题。

首先，让我们定义几个辅助函数。

让BITS(n)返回n中的位数，即ceil(log(n)/log(的无符号整数(精确)版本) 2))。一个简单的 C 实现是

size_t BITS(size_t value)
{
    size_t  result = 0;
    while (value) {
        result++;
        value >>= 1;
    }
    return result;
}

让REV(v, n)返回n位数量v的位反转值。例如，REV(1, 1) = 1、REV(1, 2) = 2、REV(1, 4) = 8 、REV(7, 3) = 7 等等。 (此处，“位反转”表示二进制的 010011_B 到 110010_B，因此 REV(19,6) = 50。) C 中的简单通用实现是

size_t REV(size_t value, size_t bits)
{
    size_t  result = 0;
    while (bits-->0) {
        result = (result << 1) | (value & 1);
        value >>= 1;
    }
    return result;
}

让FBT(n)生成OEIS A092323整数序列；即FBT(0) = 0、FBT(1) = 1、FBT(2) = 1、FBT(3) = 3、FBT(4) = 3、FBT(5) = 3、FBT(6) = 3、FBT(7) = 7，依此类推。该名称是“满二叉树”的缩写，表示最多具有 n 个节点的最大满二叉树的大小。对于无符号 32 位 n，FBT(n) 可以在 C 中实现为

uint32_t set_low_bits(uint32_t u)
{
    u |= u >> 1;
    u |= u >> 2;
    u |= u >> 4;
    u |= u >> 8;
    u |= u >> 16;
    /* Add u |= u >> 32; for 64-bit u */
    return u;
}

uint32_t FBT(uint32_t n)
{
    return set_low_bits((n + 1) >> 1);
}

如果树是空的，那么要添加的新节点当然会成为根节点。否则，我们假设您已填充 count 个节点。计算

full = FBT(count);
levels = BITS(full);
path = REV(count - full, levels);

这里，full是树中初始完整级别的节点数。 levels是添加新节点时树的层数；即，在添加新节点之前，树中的完整级别数加一。在添加新节点之前，最终级别中填充了 count - full 个最左边的节点。 path 是从 root 到要添加的新节点的路径，从最低有效位向上读取，0 表示左子节点，1 表示右子节点。

所以，假设您有一个非空树，根位于 root，新节点为 newnode，临时节点指针 parent >，以及前面提到的三个无符号整数变量。要将 newnode 添加到非空树，您需要这样做

    parent = root;
    while (levels-->1) {
        if (path & 1)
            parent = parent->right;
        else
            parent = parent->left;
        path >>= 1; /* Equivalent to path = path / 2; */
    }

    if (path & 1)
        parent->right = newnode;
    else
        parent->left = newnode;

请注意，我已经验证了该逻辑适用于测试程序，但为了确保我不会给任何人布置作业，而是帮助他们学习，我将有趣的内容复制粘贴到此处。因此，可能会出现复制粘贴错误。如果您发现任何问题，或怀疑您发现了任何问题，请在评论中告诉我，我将进行验证并修复。

<小时/>

为了测试树和图算法以及实现此类算法的程序，我建议在 Graphviz DOT language 中输出数据。 ;一种简单的文本语言，可用于通过指定节点关系来绘制图形或树。将输出重定向到文件，并将该文件提供给 dot，然后您将获得树的漂亮图形表示。

下面是一个简单的示例，它将 .dot 文件保存到命名文件中，以便于在所有操作系统中使用:

struct node {
    struct node *left;
    struct node *right;
    char        *value;
};

static void dot_node_recurse(FILE *out, struct node *at)
{
    fprintf(out, "\t\"%p\" [ label=\"%s\" ];\n", (void *)at, at->value);
    if (at->left) {
        dot_node_recurse(out, at->left);
        fprintf(out, "\t\"%p\" -> \"%p\";\n", (void *)at, (void *)(at->left));
    }
    if (at->right) {
        dot_node_recurse(out, at->right);
        fprintf(out, "\t\"%p\" -> \"%p\";\n", (void *)at, (void *)(at->right));
    }
}

int dot_node(const char *filename, struct node *root)
{
    FILE *out;

    if (!filename || !filename[0])
        return -2; /* NULL or empty filename */
    if (!root)
        return -3; /* No tree to save */

    out = fopen(filename, "w");
    if (!out)
        return -1; /* Cannot open file (for writing) */

    fprintf(out, "digraph {\n");
    dot_node_recurse(out, root);
    fprintf(out, "}\n");

    if (ferror(out)) {
        fclose(out);
        return -4; /* Write error */
    }
    if (fclose(out))
        return -4; /* Write error */

    return 0;
}