为什么我的 Preorder、Inorder 和 Postorder 函数不起作用

Question

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

节点创建

此结构创建结构节点数据类型

 struct node
    {
        int data;
        struct node *left, *right;
    } * newnode;

创建函数

create() - 它首先分配节点所需的内存。当用户输入数据时，递归调用自己创建自己的子节点，如此循环往复。当用户输入-1时，它终止递归并从调用它的地方返回。

    struct node *create()
    {
        int x;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->left = 0;
        newnode->right = 0;
        printf("Enter data(-1 for no node)\n");
        scanf("%d", &x);
        if (x == -1)
            return 0;
        newnode->data = x;
        printf("Enter left child of %d\n", x);
        newnode->left = create();
    
        printf("Enter right child of %d\n", x);
        newnode->right = create();
        return newnode;
    }

预购

preorder(struct node *root) - 该函数以预序方式显示树的数据

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

顺序

inorder(struct node *root) - 此函数按顺序显示树的数据

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

后序

Postorder(struct node *root) - 该函数以后序方式显示树的数据

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

主要功能

main函数要求用户创建一棵树，然后根据用户输入的选择进行遍历。问题是preorder, inorder, postorder没有给出需要的输出，导致执行后死循环

 void main()
    {
        struct node *root;
        root = 0;
        int choice = 3, opt = 1;
    
        while (opt)
        {
            printf("Select\n 1-for creation\n 2-for preorder\n 3-for inorder\n 4-for postorder\n");
            scanf("%d", &choice);
            switch (choice)
            {
            case 1:
                root = create();
                break;
            case 2:
                printf("Preorder is: ");
                preorder(root);
                break;
            case 3:
                printf("Inorder is: ");
                inorder(root);
                break;
            case 4:
                printf("Postorder is: ");
                postorder(root);
                break;
    
            default:
                printf("Invalid choice");
                break;
            }
            printf("Wanna continue \n1-for yes\n0-for no\n");
            scanf("%d", &opt);
        }
    }

Answer 1

您提供的任何遍历函数都没有错误。 create () 函数也没有设计或实现问题。

问题出在用结构定义声明的全局 struct node 指针 newnode。

因为对 create () 的每次递归调用基本上都是使用“相同”的 newnode 指针，所以树从未真正按照我们想要的方式构建。

让我们尝试干燥运行 create () 函数。

假设我们想要一棵这样的树：

    1
   / \
  2   3

create () 首先从 main 调用。

使用malloc ()函数分配内存，内存地址存储在newnode.
设置它的属性，left 和 right。
请求data并放入data属性，如果data == -1为真，return 0.

到目前为止，这是状态：

newnode -> 1
          / \
       Null  Null

create ()递归调用构建左子树

使用malloc ()为newnode分配内存，内存地址存储在newnode中。注意这个操作基本上已经“覆盖了”之前存储在newnode中的地址（因为newnode是一个全局变量)
然后，系统将再次提示用户输入 data 并设置其属性。

因此，树现在变成了：

newnode -> 2
          / \
       Null  Null

newnode 之前指向的 struct node 现在丢失了（因为它的地址丢失了）

同理，当对右子树进行递归调用时，则观察到：

newnode -> 3
          / \
       Null  Null

考虑到其余递归调用的相同情况，很明显最终没有构建我们期望的树，原因是全局变量 newnode，不断分配内存和覆盖newnode中的地址仅导致内存泄漏。

无限递归被发现的原因是，在多次递归调用期间，newnode的left或right指针指向newnode本身，导致一个循环。通过在递归调用期间密切跟踪 newnode 的 data 可以找到此节点。

因此，从结构声明中删除newnode指针的声明，并修改create ()函数中的以下语句：

newnode = (struct node *)malloc(sizeof(struct node));

对此：

struct node * newnode = (struct node *)malloc(sizeof(struct node));

和

struct node
{
    int data;
    struct node *left, *right;
};

是所有需要的。

这样每次对create ()函数的递归调用都会有自己的局部指针变量newnode并且不会被覆盖，不会泄漏，不会循环，不会无限递归。

为什么我的 Preorder、Inorder 和 Postorder 函数不起作用

Why my Preoder, Inorder and Postorder functions are not working

binary-tree

recursive-datastructures

inorder

preorder

postorder

节点创建

创建函数

预购

顺序

后序

主要功能