将二叉搜索树展平为列表

Question

typedef struct node *blah;

int *breath_search(struct node *root){

    int *numbers = calloc(20,sizeof(*numbers)); int listpointer = 0;
    struct node **currentlist = calloc(20,sizeof(struct node*));
    struct node **updatedlist = calloc(20,sizeof(struct node*));
    currentlist[0] = root;
    int iterations = 1;

    int depths = 3;
    while(depths){


        int i = 0; int j;
        for(j=0;j<iterations;j++){
            if(currentlist[j] == NULL){
                updatedlist[i] = NULL; i++;
                updatedlist[i] = NULL; i++;
                numbers[listpointer] = 0; listpointer++;
            }
            else if(currentlist[j] != NULL){
                updatedlist[i] = currentlist[j]->left; i++;
                updatedlist[i] = currentlist[j]->right; i++;
                numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key); listpointer++;
            }
        }

        currentlist = updatedlist;
        updatedlist = (blah[])     {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};
        iterations = iterations*2;

        depths--;

    }

    return numbers;
}

我已经查看这段代码几个小时了，我不明白为什么它不起作用。我打算给函数一个节点，它会 return 返回给我一个指针，一个包含二叉树中所有数字的列表。

我的二叉树就像

        231
     /      \
    82      247
   /  \     /  \
  80  137 NULL 263

我的函数仅 return 返回指向列表的指针

231,82,247,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

我预计

231,82,247,80,137,0,263,0,0,0,0,0,0...

Answer 1

我认为您的代码中的错误是行 ::

updatedlist = (blah[]) {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};

我怀疑这是一个有效的语法。由于您正在尝试分配一个新数组，您可以在其中保存刚访问过的节点的子节点，因此建议 calloc 一个新数组，然后您可以在代码中使用它。

所以，上面提到的那行应该改成这个::

updatedlist = calloc(20,sizeof(struct node*));

你应该考虑的几点，分配这么多内存是为了释放不再使用的内存，因为 C 没有明确地为你做这件事，你需要注意这一点你自己，以避免任何内存泄漏。因为，在 while 循环的每次迭代之后，currentList 是无用的，你应该添加一个语句（在将 updatedList 分配给 currentList 之前）

free(currentList);

并在程序结束时释放 updatedList。

其次，你现在做的是类似二叉树的层序遍历。因此，您可以尝试使用 STL queue，并且不需要像您正在做的那样创建和交换数组。像这样的东西::

int *breath_search(struct node *root){

    int *numbers = calloc(20,sizeof(*numbers));
    int listpointer = 0;
    queue<node*> q;
    q.push(root);
    int iterations = 1;

    int depths = 3;
    while(depths){
        int i = 0, j;
        for(j=0; j<iterations; j++){
            node* currentNode = q.pop();
            if(currentNode == NULL){
                q.push(NULL);
                q.push(NULL);
                numbers[listpointer] = 0;
                listpointer++;
            }
            else if(currentNode != NULL){
                q.push(currentNode->left);
                q.push(currentNode->right);
                numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key);
                listpointer++;
            }
        }
        iterations = iterations*2;
        depths--;
    }
    return numbers;
}

我相信这是一种更好的方法，因为您不必继续分配和释放内存，因此它减少了开销。我用的是STL队列，你完全可以用自己的队列。

将二叉搜索树展平为列表

Flattening a binary search tree into a list

c

binary-tree

breadth-first-search

binary-search-tree