c - 二叉树的中序遍历

Question

我尝试编写一个函数来按顺序遍历二叉树并将其项目按顺序放入整数数组中。我知道这段代码包含一些不好的做法，但我想知道的是为什么我的函数不会创建目标整数数组。例如，即使我的函数可以找到保留 bst 的所有项目所需的大小，它也无法正确放置这些项目。有时它只放置 2 个节点，有时只放置根。

我看不出有任何理由将任何 main 函数放在这里，因为我只会将它用于打印该数组的元素。

我的 TreeNode 函数、全局变量和 typedef block ；

typedef struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

    int ctr = 0;
    int size = 0;

    int* inorder(TreeNode *root, int* arr){

        if(ctr==0) /*if first call to this function*/
            arr = malloc(size*sizeof(int)) ;

        ctr++ ; 

        if(root){

            if(!root->left && !root->right){        
                arr = realloc(arr, ++size*sizeof(int)) ;
                arr[size-1] = root->val ;
            }

            else if(!root->left&&root->right){
                arr = realloc(arr, ++size*sizeof(int)) ;
                arr[size-1] = root->val ;
                arr=inorder(root->right,arr) ;  
            }
            else if(!root->right&&root->left){
                arr=inorder(root->left,arr) ;
                arr = realloc(arr, ++size*sizeof(int)) ;
                arr[size-1] = root->val ;
            }
            else{
                arr=inorder(root->left,arr) ;
                arr = realloc(arr, ++size*sizeof(int)) ;
                arr[size-1] = root->val ;
                arr=inorder(root->right,arr) ;

            }

            return arr ;
        }
        else
            return arr ;
    }

Answer 1

哎呀，你在每次函数调用时都执行了 realloc() 。 realloc() 的成本很高，应尽可能少地使用。您应该将树的大小保留在某处。如果不行，可以先遍历一遍，统计一下元素个数。

另一件事:你的 if/elseif/elseif/else 是没用的:你总是可以应用相同的处理方法。伪代码，假设对于任何节点 left->val < node->val < right->val :

1. 获取树的大小(如果还没有)
2. malloc() 一个大小为 size*sizeof(int) 的数组(这是唯一的分配你需要)，将索引初始化为 0

然后你可以做一个简单的递归:

void inorder(Treenode *root, int *array, int *index) {
    if (!root)
        return;

    inorder(root->left, array, index);
    array[*index] = root->val;
    (*index)++;
    inorder(root->right, array, index);
}

就是这样!