이진 검색 트리

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). 많은 삽입이 예상되는 경우이 솔루션은 적절하지 않습니다. 그러나이 경우 정렬 된 배열을 유지함으로써 트리 구조의 모든 이점을 잃어 버리게됩니다.