AVL 트리. 위치별로 요소 인쇄

Question

#include<stdio.h> 
#include<stdlib.h> 

// An AVL tree node 
struct node 
{ 
    int key; 
    struct node *left; 
    struct node *right; 
    int height; 
}; 

// A utility function to get maximum of two integers 
int max(int a, int b); 

// A utility function to get height of the tree 
int height(struct node *N) 
{ 
    if (N == NULL) 
     return 0; 
    return N->height; 
} 

// A utility function to get maximum of two integers 
int max(int a, int b) 
{ 
    return (a > b)? a : b; 
} 

/* Helper function that allocates a new node with the given key and 
    NULL left and right pointers. */ 
struct node* newNode(int key) 
{ 
    struct node* node = (struct node*) 
         malloc(sizeof(struct node)); 
    node->key = key; 
    node->left = NULL; 
    node->right = NULL; 
    node->height = 1; // new node is initially added at leaf 
    return(node); 
} 

// A utility function to right rotate subtree rooted with y 
// See the diagram given above. 
struct node *rightRotate(struct node *y) 
{ 
    struct node *x = y->left; 
    struct node *T2 = x->right; 

    // Perform rotation 
    x->right = y; 
    y->left = T2; 

    // Update heights 
    y->height = max(height(y->left), height(y->right))+1; 
    x->height = max(height(x->left), height(x->right))+1; 

    // Return new root 
    return x; 
} 

// A utility function to left rotate subtree rooted with x 
// See the diagram given above. 
struct node *leftRotate(struct node *x) 
{ 
    struct node *y = x->right; 
    struct node *T2 = y->left; 

    // Perform rotation 
    y->left = x; 
    x->right = T2; 

    // Update heights 
    x->height = max(height(x->left), height(x->right))+1; 
    y->height = max(height(y->left), height(y->right))+1; 

    // Return new root 
    return y; 
} 

// Get Balance factor of node N 
int getBalance(struct node *N) 
{ 
    if (N == NULL) 
     return 0; 
    return height(N->left) - height(N->right); 
} 

struct node* insert(struct node* node, int key) 
{ 
    /* 1. Perform the normal BST rotation */ 
    if (node == NULL) 
     return(newNode(key)); 

    if (key < node->key) 
     node->left = insert(node->left, key); 
    else 
     node->right = insert(node->right, key); 

    /* 2. Update height of this ancestor node */ 
    node->height = max(height(node->left), height(node->right)) + 1; 

    /* 3. Get the balance factor of this ancestor node to check whether 
     this node became unbalanced */ 
    int balance = getBalance(node); 

    // If this node becomes unbalanced, then there are 4 cases 

    // Left Left Case 
    if (balance > 1 && key < node->left->key) 
     return rightRotate(node); 

    // Right Right Case 
    if (balance < -1 && key > node->right->key) 
     return leftRotate(node); 

    // Left Right Case 
    if (balance > 1 && key > node->left->key) 
    { 
     node->left = leftRotate(node->left); 
     return rightRotate(node); 
    } 

    // Right Left Case 
    if (balance < -1 && key < node->right->key) 
    { 
     node->right = rightRotate(node->right); 
     return leftRotate(node); 
    } 

    /* return the (unchanged) node pointer */ 
    return node; 
} 

/* Given a non-empty binary search tree, return the node with minimum 
    key value found in that tree. Note that the entire tree does not 
    need to be searched. */ 
struct node * minValueNode(struct node* node) 
{ 
    struct node* current = node; 

    /* loop down to find the leftmost leaf */ 
    while (current->left != NULL) 
     current = current->left; 

    return current; 
} 

struct node* deleteNode(struct node* root, int key) 
{ 
    // STEP 1: PERFORM STANDARD BST DELETE 

    if (root == NULL) 
     return root; 

    // If the key to be deleted is smaller than the root's key, 
    // then it lies in left subtree 
    if (key < root->key) 
     root->left = deleteNode(root->left, key); 

    // If the key to be deleted is greater than the root's key, 
    // then it lies in right subtree 
    else if(key > root->key) 
     root->right = deleteNode(root->right, key); 

    // if key is same as root's key, then This is the node 
    // to be deleted 
    else 
    { 
     // node with only one child or no child 
     if((root->left == NULL) || (root->right == NULL)) 
     { 
      struct node *temp = root->left ? root->left : root->right; 

      // No child case 
      if(temp == NULL) 
      { 
       temp = root; 
       root = NULL; 
      } 
      else // One child case 
      *root = *temp; // Copy the contents of the non-empty child 

      free(temp); 
     } 
     else 
     { 
      // node with two children: Get the inorder successor (smallest 
      // in the right subtree) 
      struct node* temp = minValueNode(root->right); 

      // Copy the inorder successor's data to this node 
      root->key = temp->key; 

      // Delete the inorder successor 
      root->right = deleteNode(root->right, temp->key); 
     } 
    } 

    // If the tree had only one node then return 
    if (root == NULL) 
     return root; 

    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE 
    root->height = max(height(root->left), height(root->right)) + 1; 

    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether 
    // this node became unbalanced) 
    int balance = getBalance(root); 

    // If this node becomes unbalanced, then there are 4 cases 

    // Left Left Case 
    if (balance > 1 && getBalance(root->left) >= 0) 
     return rightRotate(root); 

    // Left Right Case 
    if (balance > 1 && getBalance(root->left) < 0) 
    { 
     root->left = leftRotate(root->left); 
     return rightRotate(root); 
    } 

    // Right Right Case 
    if (balance < -1 && getBalance(root->right) <= 0) 
     return leftRotate(root); 

    // Right Left Case 
    if (balance < -1 && getBalance(root->right) > 0) 
    { 
     root->right = rightRotate(root->right); 
     return leftRotate(root); 
    } 

    return root; 
} 

// A utility function to print preorder traversal of the tree. 
// The function also prints height of every node 
void preOrder(struct node *root) 
{ 
    if(root != NULL) 
    { 
     preOrder(root->left); 
     printf("%d ", root->key); 
     preOrder(root->right); 
    } 
} 

/* Drier program to test above function*/ 
int main() 
{ 
    struct node *root = NULL; 

    /* Constructing tree given in the above figure */ 
    root = insert(root, 9); 
    root = insert(root, 5); 
    root = insert(root, 10); 
    root = insert(root, 0); 
    root = insert(root, 6); 
    root = insert(root, 11); 
    root = insert(root, -1); 
    root = insert(root, 1); 
    root = insert(root, 2); 
    root = insert(root, 10); 


    printf("Pre order traversal of the constructed AVL tree is \n"); 
    preOrder(root); 

    root = deleteNode(root, 10); 



    printf("\nPre order traversal after deletion of 10 \n"); 
    preOrder(root); 

    return 0; 
} 

특정 위치를 지정하면 요소를 인쇄 할 수 있습니까? 예 :

root = insert(root, 100); (add 100) 
root = insert(root, 300); (add 300) 
root = insert(root, 200); (add 200) 
root = insert(root, 200); (add 400) 

PRINT 1 -> Should print the first element (sorted). Which is 100 
PRINT 3 -> Should print the third element (sorted). Which is 300 

어떻게 내 AVL 트리에서이 PRINT를 구현할 수 있습니까?

나는이 기능을 수정하려고하지만 난

void preOrder(struct node *root) 
{ 
    if(root != NULL) 
    { 
     preOrder(root->left); 
     printf("%d ", root->key); 
     preOrder(root->right); 
    } 
} 

내가 사용하지 수 성공하지 않은 그들은 모두 같은 시간에 전달되기 때문에 값이 전달되는 것을 확인하기 위해 여기에 한 Statment합니다.

preOrder 함수가 숫자를 정렬합니다. 가장 낮은 것에서 낮은 것.

int findPositionPreOrder(
    struct node *root, 
    int targetPos, 
    int curPos) 
{ 
    if(root != NULL) 
    { 
     int newPos = findPositionPreOrder(root->left, targetPos, curPos); 
     newPos++; 
     if (newPos == targetPos) 
     { 
      printf("%d\n", root->key); 
     } 
     return findPositionPreOrder(root->right, targetPos, newPos); 
    } 
    else 
    { 
     return curPos; 
    } 
} 

그리고 당신은 findPositionPreOrder(root, targetPosition, 0)과 같이 호출 : 당신은 그냥 길을 따라 업데이 트를 그 현재 위치를 "기억"해야 -

Answer 1

당신이 그렇게 예약 주문을 수정할 수 없습니다 왜 이해가 안 돼요 ;

• 이것은 최적의 해결책은 아닙니다. 나머지 트리를 탐색하는 대신 원하는 위치를 찾은 다음 재귀를 중단 할 수 있습니다.