c-将BST转换为数组

Question

我有一个二进制树，我需要在数组中对它进行排序，然后返回它

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));

点击此处阅读更多信息：C 中的动态内存分配

现在，要将树按排序顺序存储在数组中，需要遍历树的左侧部分，然后遍历根，然后遍历右侧部分(可以递归执行(。这被称为有序遍历(Tree Traversals(。只需在interder遍历函数中传递上述数组，并在遍历时存储根值。

有序遍历函数可以是这样的：

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;
}

我希望这能有所帮助。如果你有任何疑问，请随时询问。