将 BST 转换为数组

Question

我有一个二叉树，我需要在数组中对它进行排序，然后 return 它。这是功能和我目前所在的位置

struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
};

typedef struct treeNode* BSTree;

static int* writeSortedToArray(const BSTree tree)
{
    int i=0;
    int leng = numberOfNodes(tree);
    int *arrayBST = malloc(leng*sizeof(int));

}

我不知道如何继续，或者即使分配部分是正确的任何关于如何使这项工作的建议都将不胜感激，如果在我之前问过类似的问题，如果有人能指导我，我会很高兴。

Answer 1

首先，您需要正确分配数组。

您可以这样做：

int* arrayBST = (int*)malloc(leng*sizeof(int));

在此处阅读更多相关信息：Dynamic Memory Allocation in C

现在，要在数组中按排序顺序存储树，您需要遍历树的左侧部分，然后是根，然后是右侧部分（可以递归执行）。这称为中序遍历（Tree Traversals）。在中序遍历函数中传入上述数组，并在遍历时存储根值即可。

中序遍历函数可以这样：

typedef struct treeNode* BSTree; 

// you can pass the index in the array as reference
void inorderTraversal(const BSTree tree, int* arrayBST, int* ind) {
    if(tree) {
        //store the left subtree
        inorderTraversal(tree->left, arrayBST, ind);

        //store current root value
        arrayBST[*ind] = tree->data;
        (*ind)++;

        //store the right subtree
        inorderTraversal(tree->right, arrayBST, ind);
    }
}

static int* writeSortedToArray(const BSTree tree)
{
    int ind = 0;
    int leng = numberOfNodes(tree); 
    int* arrayBST = (int*)malloc(leng*sizeof(int));
    inorderTraversal(tree, arrayBST, &ind);
    return arrayBST;
}

希望对您有所帮助。如果您有任何疑问，请随时提出。

将 BST 转换为数组

Converting a BST to an array

arrays

c

sorting

binary-search-tree