将所有节点指针存储在二叉搜索树的指针数组中

Question

最近我试图操纵二叉搜索树，被困在这里。我想要一个数组(指针数组)里面我想按顺序存储二叉搜索树每个节点的指针。我不需要每个节点的值，我需要指针，这样我就可以访问它们的值，左子树和右子树。我所做的是

struct node{
int key;
struct node *left, *right;
};
node **arr;
int x=0;
void inorder(struct node *root){
if (root != NULL){
    inorder(root->left);
    //cout<<"X : "<<x<<endl;
    arr[x] = root;
    x++;
    printf("%d n", root->key);
    inorder(root->right);
}
}

请帮助。谢谢。

Answer 1

您可以这样做，但是如果节点指针的排序数组满足您的需要，那么您不需要二叉搜索树:您可以在数组上执行二叉搜索。这种数据结构具有与树相同的访问速度(甚至可以稍微快一点，因为数据被紧密地封装在内存中)，并且非常节省内存。但是插入新数据的代价是0 (n)。因此，如果期望进行许多插入，则此解决方案不适合。但在这种情况下，通过维护排序数组，你失去了树结构的所有好处。