c - 二分查找树没有打印任何内容

Question

我正在尝试从给定输入创建一个不平衡的二叉搜索树作为(未排序的)整数序列。
我的方法是递归地为每个单独的节点找到正确的位置，然后为其分配内存并为其定义数据。
但我无法有效地调试该程序，因为尽管正确检查了该程序，但我似乎无法识别问题。对于输入如下:

11
15 6 4 8 5 3 1 10 13 2 11

预期的输出应该是后序和中序遍历，但奇怪的是没有打印任何内容(除了我在中间给出的换行符)。

注意:这个问题与我之前提出的 BST 相关问题密切相关，但方法完全不同，我面临的挑战也是如此。因此，在攻击我的脖子并可能结束这个话题之前要三思而后行。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arrmax 100
/***Pointer-based BST implementation, developed by Abhineet Saxena***/


/***The data-type declaration***/
typedef struct node{
int data;
struct node* parent;
struct node* leftChild;
struct node* rightChild;
}Node;

typedef struct tree
{
    Node* root;
    int size;
}BSTree;

/***Method prototypes***/
/*Method to create a tree*/
Node* createTree(int[],int,int);
void insert(Node*,int);

Node* createNode(int);
void inOrder(Node* root);
void postOrder(Node *root);

int main(void) {

    BSTree* bs_tree;
    bs_tree=malloc(sizeof(BSTree));
    bs_tree->root=NULL;
    bs_tree->size=0;
    /****Taking the input****/
    int num_elem,iterv;
    scanf("%d\n",&num_elem);
    int *arr=malloc(sizeof(int)*(num_elem));
    for(iterv=0;iterv<num_elem;iterv++)
    {
        scanf("%d",&arr[iterv]);
    }
    bs_tree->root=createTree(arr,0,num_elem-1);
    postOrder(bs_tree->root);

    printf("\n");
    inOrder(bs_tree->root);

    return 0;
}
Node* createTree(int marr[],int left,int right)
{
    int iterv;
    Node* root;
    root=NULL;
//  Node** root_ptr;
    //*root_ptr=root;
    for(iterv=left;iterv<=right;iterv++)
    {

        insert(root,marr[iterv]);

    }
    return root;
}
Node* createNode(int key)
{
        Node* tree_node;
        tree_node=malloc(sizeof(Node));
        //printf("Used malloc here for key: %d\n",key);
        tree_node->data=key;
        tree_node->leftChild=NULL;
        tree_node->rightChild=NULL;
        tree_node->parent=NULL;
        return tree_node;
}
void insert(Node* root,int key)
{
        if(root==NULL)
    {
        root=createNode(key);
        //return root;
    }
    else if(root->leftChild!=NULL && root->rightChild!=NULL)
        {
            if(key<root->data)

                        insert(root->leftChild,key);
                        else

                       insert(root->rightChild,key);
        }
        else if(root->leftChild!=NULL && root->rightChild==NULL)
        {
            if(key>root->data)
            {
                Node* tnode=createNode(key);
                root->rightChild=tnode;
                tnode->parent=root;
                return;
            }
            else if(key<root->data)
                insert(root->leftChild,key);

        }
        else if(root->leftChild==NULL && root->rightChild!=NULL)
        {
            if(key<root->data)
            {
                Node* tnode=createNode(key);
                root->leftChild=tnode;
                tnode->parent=root;
                return;
            }
            else if(key>root->data)
                insert(root->rightChild,key);
        }
        else
        {
            if(key<root->data)
            {
                Node* tnode=createNode(key);
                root->leftChild=tnode;
                tnode->parent=root;
                return;
            }
            else if(key>root->data)
            {
                Node* tnode=createNode(key);
                root->rightChild=tnode;
                tnode->parent=root;
                return;
            }
        }

}

void inOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        inOrder(bst_tree->leftChild);
        printf("%d ",bst_tree->data);
        inOrder(bst_tree->rightChild);
    }
    else
        return;
}
void postOrder(Node* bst_tree)
{
    if(bst_tree!=NULL)
    {
        postOrder(bst_tree->leftChild);
        postOrder(bst_tree->rightChild);
        printf("%d ",bst_tree->data);
    }
    else
        return;
}

Answer 1

你的问题是这样的:在createTree中，你将root设置为NULL，然后调用

insert(root, marr[iterv]);

...现在神奇地期望 root 之后为非 NULL。您需要更改为以下调用约定:

insert(&root, marr[iterv]);

...并将 insert 的签名更改为 void insert(Node**,int);

然后，在插入函数中，使用 *root 代替 root，使用 (*root)->something 代替 root->something。我用这些更改测试了您的程序，它有效。

一个额外的挑剔:整数范围应该包含左值和右值排除，因此你应该以这种方式调用 createTree:

bs_tree->root=createTree(arr,0,num_elem);

然后有这个循环:

for(iterv=left;iterv<right;iterv++)

那么范围的长度是从右到左，这样更方便。