我怎样才能把一棵树变成 C 语言中括号表示的字符串？

Question

#include <stdio.h>
#include <stdlib.h>
typedef struct node_st {
    int data;
    struct node_st* left;
    struct node_st* right;
};

void preorder(struct node_st *root) {
    if (root != NULL) {
        printf("%d\n", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct node_st *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d\n", root->data);
    }
}

struct node_st* createNode(value) {
    struct node_st* newNode = malloc(sizeof(struct node_st));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node_st* insertLeft(struct node_st* root, int value){
    root->left = createNode(value);
    return root->left;
}

struct node_st* insertRight(struct node_st* root, int value){
    root->right = createNode(value);
    return root->right;
}


int main() {
    struct node_st* root = createNode(2);
    insertLeft(root, 6);
    insertRight(root, 9);
    insertLeft(root->left, 2);
    insertLeft(root->right, 1);

    printf("\nPreorder\n");
    preorder(root);
    printf("\nPostorder\n");
    postorder(root);
}

我需要创建一个函数来将树存储到带有方括号表示的字符串中，例如 (A(B)(C)) 并读取它来生成树，但我无法在线查找信息如何在 C 中执行此操作，将不胜感激。

这之后的下一步是存储它并从文件中读取它，但我可以通过文档处理它。

Answer 1

这里是用括号表示形式打印树的代码。您请求的格式不明确——如果一个节点只有一个 child，您无法判断 child 是左 child 还是右 child。这种不明确的格式是由名称中带有 _v1_ 的函数产生的：print_v1_tree()、print_v1_preorder()、print_v1_postorder()、print_v1_inorder().

有一种替代格式，空子树由 () 表示，除非该节点是叶节点（两个 child 节点都为空）。

还有一个free_tree()函数来释放树的内存。

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

typedef struct node_st
{
    int data;
    struct node_st *left;
    struct node_st *right;
} Node;

typedef void (*Print)(const Node *node);

extern struct node_st *createNode(int value);
extern struct node_st *insertLeft(struct node_st *root, int value);
extern struct node_st *insertRight(struct node_st *root, int value);
extern void postorder(struct node_st *root);
extern void preorder(struct node_st *root);
extern void inorder(struct node_st *root);

extern void print_v1_postorder(const Node *node);
extern void print_v1_inorder(const Node *node);
extern void print_v1_preorder(const Node *node);
extern void print_v1_tree(const char *tag, const Node *node, Print print);

extern void print_v2_postorder(const Node *node);
extern void print_v2_inorder(const Node *node);
extern void print_v2_preorder(const Node *node);
extern void print_v2_tree(const char *tag, const Node *node, Print print);

extern void free_tree(Node *node);

void preorder(struct node_st *root)
{
    if (root != NULL)
    {
        printf("%d\n", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(struct node_st *root)
{
    if (root != NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d\n", root->data);
    }
}

void inorder(struct node_st *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d\n", root->data);
        inorder(root->right);
    }
}

struct node_st *createNode(int value)
{
    struct node_st *newNode = malloc(sizeof(struct node_st));
    if (newNode == NULL)
    {
        fprintf(stderr, "Failed to allocate memory for a node\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node_st *insertLeft(struct node_st *root, int value)
{
    root->left = createNode(value);
    return root->left;
}

struct node_st *insertRight(struct node_st *root, int value)
{
    root->right = createNode(value);
    return root->right;
}

void print_v1_preorder(const Node *node)
{
    printf("%d", node->data);
    if (node->left != NULL)
    {
        putchar('(');
        print_v1_preorder(node->left);
        putchar(')');
    }
    if (node->right != NULL)
    {
        putchar('(');
        print_v1_preorder(node->right);
        putchar(')');
    }
}

void print_v1_inorder(const Node *node)
{
    if (node->left != NULL)
    {
        putchar('(');
        print_v1_inorder(node->left);
        putchar(')');
    }
    printf("%d", node->data);
    if (node->right != NULL)
    {
        putchar('(');
        print_v1_inorder(node->right);
        putchar(')');
    }
}

void print_v1_postorder(const Node *node)
{
    if (node->left != NULL)
    {
        putchar('(');
        print_v1_postorder(node->left);
        putchar(')');
    }
    if (node->right != NULL)
    {
        putchar('(');
        print_v1_postorder(node->right);
        putchar(')');
    }
    printf("%d", node->data);
}

void print_v1_tree(const char *tag, const Node *node, Print print)
{
    printf("%s: (", tag);
    if (node != NULL)
        (*print)(node);
    putchar(')');
    putchar('\n');
}

void print_v2_preorder(const Node *node)
{
    if (node == NULL)
        return;
    printf("%d", node->data);
    if (node->left != NULL || node->right != NULL)
    {
        putchar('(');
        print_v2_preorder(node->left);
        putchar(')');
    }
    if (node->right != NULL || node->left != NULL)
    {
        putchar('(');
        print_v2_preorder(node->right);
        putchar(')');
    }
}

void print_v2_inorder(const Node *node)
{
    if (node == NULL)
        return;
    if (node->left != NULL || node->right != NULL)
    {
        putchar('(');
        print_v2_inorder(node->left);
        putchar(')');
    }
    printf("%d", node->data);
    if (node->right != NULL || node->left != NULL)
    {
        putchar('(');
        print_v2_inorder(node->right);
        putchar(')');
    }
}

void print_v2_postorder(const Node *node)
{
    if (node == NULL)
        return;
    if (node->left != NULL || node->right != NULL)
    {
        putchar('(');
        print_v2_postorder(node->left);
        putchar(')');
    }
    if (node->right != NULL || node->left != NULL)
    {
        putchar('(');
        print_v2_postorder(node->right);
        putchar(')');
    }
    printf("%d", node->data);
}

void print_v2_tree(const char *tag, const Node *node, Print print)
{
    printf("%s: (", tag);
    if (node != NULL)
        (*print)(node);
    putchar(')');
    putchar('\n');
}

/* Must be post-order release, but could do right before left */
void free_tree(Node *node)
{
    if (node != NULL)
    {
        free(node->left);
        free(node->right);
        free(node);
    }
}

int main(void)
{
    struct node_st *root = createNode(3);

    insertLeft(root, 6);
    insertRight(root, 9);
    insertLeft(root->left, 2);
    insertLeft(root->right, 1);

    printf("\nPreorder\n");
    preorder(root);
    printf("\nPostorder\n");
    postorder(root);
    printf("\nInorder\n");
    inorder(root);

    printf("\nAmbiguous:\n");
    print_v1_tree("Preorder",  root, print_v1_preorder);
    print_v1_tree("Inorder",   root, print_v1_inorder);
    print_v1_tree("Postorder", root, print_v1_postorder);
    print_v1_tree("Empty",     NULL, print_v1_inorder);

    printf("\nUnambiguous:\n");
    print_v2_tree("Preorder",  root, print_v2_preorder);
    print_v2_tree("Inorder",   root, print_v2_inorder);
    print_v2_tree("Postorder", root, print_v2_postorder);
    print_v2_tree("Empty",     NULL, print_v2_inorder);

    insertRight(root->right, 13);
    insertRight(root->left, 3);
    insertRight(root->left->right, 4);
    insertRight(root->left->right->right, 5);

    printf("\nExtended tree - unambiguous:\n");
    print_v2_tree("Preorder",  root, print_v2_preorder);
    print_v2_tree("Inorder",   root, print_v2_inorder);
    print_v2_tree("Postorder", root, print_v2_postorder);
    print_v2_tree("Empty",     NULL, print_v2_inorder);

    free_tree(root);

    return 0;
}

这个输出是：

Preorder
3
6
2
9
1

Postorder
2
6
1
9
3

Inorder
2
6
3
1
9

Ambiguous:
Preorder: (3(6(2))(9(1)))
Inorder: (((2)6)3((1)9))
Postorder: (((2)6)((1)9)3)
Empty: ()

Unambiguous:
Preorder: (3(6(2)())(9(1)()))
Inorder: (((2)6())3((1)9()))
Postorder: (((2)()6)((1)()9)3)
Empty: ()

Extended tree - unambiguous:
Preorder: (3(6(2)(3()(4()(5))))(9(1)(13)))
Inorder: (((2)6(()3(()4(5))))3((1)9(13)))
Postorder: (((2)(()(()(5)4)3)6)((1)(13)9)3)
Empty: ()

将其转换为将数据存储在字符串中并不难。解析它比较麻烦——不管你使用哪种格式。预购可能是最容易处理的。

Answer 2

这是我使用 sprintf（return 存储的字符数）将树存储在字符串中的代码，给定：

要开始存储的节点（第一次调用时为根节点）
一个预分配的字符串，可以修改代码重新分配
您正在打印的字符串的位置 (i)
字符串的最大大小

    int string_parenthesis_by_node(node_t *nd, char *str, int i, int max){
    if (!nd) return 0;

    // checks the size limit
    int added = (ceil(log10(nd->key > 0 ? nd->key : 1)) + 2);
    if (i + added >= max){
        fprintf(stderr, "TOO LARGE INPUT TO BUFFER, tried to add %d on top of %d, maxing %d", added, i, max);
        return 0;
    }

    // res is the current position you are storing
    // it is incremented after every sprint
    int res = i;
    res += sprintf(str+res, "(%d", nd->key);
    res += string_parenthesis_by_node(nd->left, str, res, max);
    res += string_parenthesis_by_node(nd->right, str, res, max);
    res += sprintf(str+res, ")");

    return res-i;
}```

我怎样才能把一棵树变成 C 语言中括号表示的字符串？

How can I turn a tree into a string of bracket representation in C?

c

binary-tree

struct