c - 尝试在c中创建前一棵树的预遍历时，BST节点未保存

我想看看树A是否是树B的优先遍历，为此，我创建了两棵树，在遍历过程中应该保存这些值。但是，经过几个小时的调试，我发现树的值总是0。我不明白为什么树的值是0我已经做了大量的打印语句（其中一些我已经在下面的代码中留下了），但我似乎无法确定为什么会发生这种情况。有人能把我推到正确的方向吗？我想函数可能是在退出变量时删除变量，为了达到问题的底部，我有预序函数返回树（如下所示），但是，树的输出总是0。
代码：

typedef struct node
{
    // Each node holds a single integer.
    int data;

    // Pointers to the node's left and right children.
    struct node *left, *right;
} node;
int tree_diff(node *a, node *b)
{
    if (a == NULL && b == NULL)
        return 0;

    else if (a == NULL || b == NULL)
        return 1;


    else if (a->data != b->data)
        return 1;
    printf("A %d , B %d", a->data, b->data);

        return tree_diff(a->left, b->left) || tree_diff(a->right, b->right);
}

node *preorder_recursive(node *root, node *A)
{
    if (root == NULL)
        return A;

    printf("root %d ", root->data);
    A = root;
    printf("= data %d\n", A->data);
    preorder_recursive(root->left, A->left);
    preorder_recursive(root->right, A->right);
}

void postorder_recursive(node *root, node *B)
{
    if (root == NULL)
        return;
    B = root;
    postorder_recursive(root->left, B->left);
    postorder_recursive(root->right, B->right);
    printf("root %d ", root->data);
    printf("= data %d\n", B->data);
}

int kindredSpirits(node *a, node *b)
{

  // Get the preorder of a
  node *A = malloc(sizeof(node));
  A = preorder_recursive(a, A);

  // Get the postorder of b
  printf("\n\n");
  node *B = malloc(sizeof(node));
  postorder_recursive(b, B);

if(tree_diff(A,B) == 1)
  return 0;
else
  return 1;
}

测试用例：

#include <stdio.h>
#include <stdlib.h>
#include "KindredSpirits.h"
  node *create_node(int data)
{
    node *n = malloc(sizeof(node));

    n->data = data;
    n->left = n->right = NULL;

    return n;
}

node *forest_fire(node *root)
{
    if (root == NULL)
        return NULL;

    forest_fire(root->left);
    forest_fire(root->right);
    free(root);
}

int main(void)
{
    node *root;

    root = create_node(23);
    root->left = create_node(12);
    root->left->left = create_node(5);
    root->left->right = create_node(18);
    root->right = create_node(71);
    root->right->right = create_node(56);

    printf("%s\n", !kindredSpirits(root, root) ? "Success!" : "fail whale :(");

    forest_fire(root);

    return 0;
}

最佳答案

下面是一个代码片段，可以帮助您开始：

typedef struct node {
    // Each node holds a single integer.
    int data;

    // Pointers to the node's left and right children.
    struct node *left,
    struct node *right;
} node;

typedef struct list {
    int lst_max;                        // maximum number of allocated cells
    int lst_cur;                        // current number of filled cells
    int *lst_base;                      // traversal list
} list;

list list_a = { 0, 0, NULL };
list list_b = { 0, 0, NULL };

void
list_append(list *lst,int data)
{
    int newidx;

    newidx = lst->lst_cur;

    if (newidx >= lst->lst_max) {
        lst->lst_max += 100;
        lst->lst_base = realloc(lst->lst_base,sizeof(int) * lst->lst_max);
        if (lst->lst_base == NULL) {
            printf("list_append: malloc error\n");
            exit(1);
        }
    }

    lst->lst_base[newidx] = data;

    lst->lst_cur = newidx + 1;
}

void
preorder_recursive(node *root,list *lst)
{

    if (root == NULL)
        return;

    list_append(lst,root->data);
    preorder_recursive(root->left,lst);
    preorder_recursive(root->right,lst);
}

void
postorder_recursive(node *root,list *lst)
{

    if (root == NULL)
        return;

    postorder_recursive(root->left,lst);
    postorder_recursive(root->right,lst);
    list_append(lst,root->data);
}

int
main(void)
{

    preorder_recursive(a,&list_a);
    postorder_recursive(b,&list_b);

    // compare list_a and list_b ...

    return 0;
}

关于c - 尝试在c中创建前一棵树的预遍历时，BST节点未保存，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43175400/