將所有節點指針存儲在二叉搜索樹的指針數組中

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

您可以這樣做，但是如果排序的節點指針數組滿足您的需求，那麼您不需要二叉搜索樹：您可以對數組執行二分搜索。這個數據結構具有與樹相同的訪問速度（因爲數據緊密地封裝在內存中，所以速度可能會稍微快一些），並且具有很高的內存效率。但插入新數據代價昂貴：o（n）。所以如果預計會有很多插入，這個解決方案是不合適的。但在這種情況下，通過維護該排序的數組，您可以放棄樹結構的所有優點。