时间戳

首页 > 解决方案 > 如何在 C 中将一棵树变成一串括号表示？

c - 如何在 C 中将一棵树变成一串括号表示？

问题描述

#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，将不胜感激任何帮助。

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

标签： cstructbinary-tree

解决方案

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

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

还有一个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: ()

将其转换为将数据存储在字符串中并不太困难。解析它更复杂——无论您使用哪种格式。预购可能是最容易处理的。

推荐阅读