打印逆序AVL树

Question

我正在构建一个AVL树，并试图以相反的顺序（降序）打印它。我不想更改我的insert函数，因为我有时也会使用经典的有序打印。所以，我认为 - >我需要交换访问right和left节点，它将被反向打印。

void inOrder(struct node *root) 
{ 
    if(root != NULL) 
    { 
     inOrder(root->left); 
     printf("%lf\n", root->key); 
     inOrder(root->right); 
    } 
} 

void inOrderDecreasing(struct node *root) 
{ 
    if(root != NULL) 
    { 
     inOrder(root->right); 
     printf("%lf\n", root->key); 
     inOrder(root->left); 
    } 
} 

但是，这是行不通的。 inOrder按原样工作，但其他功能不适用。

我得到什么：

45.943100 
78.321899 
99.200996 
32.750999 
10.475900 
25.170500 

如果有人想看看我的插入功能：

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

/* 
* RECAP Balance is based on Height 
*  Hn = Hl - Hr 
* so 
* positive => LEFT HEAVY 
* negative => RIGHT HEAVY 
*/ 
// 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, float key) 
{ 
    /* 1. Perform the normal BST insertion */ 
    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 

    /* CASE # 1 => LEFT-LEFT aka left? 
     T1, T2, T3 and T4 are subtrees. 
     z          y 
     /\         / \ 
     y T4  Right Rotate (z)   x  z 
    /\   - - - - - - - - -> /\ /\ 
    x T3        T1 T2 T3 T4 
    /\ 
    T1 T2 
    */ 
    // Left Left Case in code 
    if (balance > 1 && key < node->left->key) 
     return rightRotate(node); 

    /* Case #2 => RIGHT-RIGHT aka right? 

     z        y 
    /\       / \ 
    T1 y  Left Rotate(z)  z  x 
     /\ - - - - - - - --> /\ /\ 
    T2 x      T1 T2 T3 T4 
    /\ 
    T3 T4 

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


    /* CASE # 3 => LEFT-RIGHT aka left-right? 
    z        z       x 
    /\       / \      /\ 
    y T4 Left Rotate (y)  x T4 Right Rotate(z) y  z 
/\  - - - - - - - - -> /\  - - - - - - - ->/\ /\ 
T1 x       y T3     T1 T2 T3 T4 
    /\      /\ 
    T2 T3     T1 T2 

    */ 
    // Left Right Case in code 
    if (balance > 1 && key > node->left->key) 
    { 
     node->left = leftRotate(node->left); 
     return rightRotate(node); 
    } 
    /* CASE #4 = RIGHT-LEFT aka right-left? 
     z       z       x 
    /\      /\      /\ 
     T1 y Right Rotate (y) T1 x  Left Rotate(z) z  y 
    /\ - - - - - - - - -> /\  - - - - - - - ->/\ /\ 
    x T4      T2 y      T1 T2 T3 T4 
/\        /\ 
T2 T3        T3 T4 
    */ 
    // Right Left Case in code 
    if (balance < -1 && key < node->right->key) 
    { 
     node->right = rightRotate(node->right); 
     return leftRotate(node); 
    } 

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

Answer 1

你必须去适应你的inOrderDecreasing的递归还有：

void inOrder(struct node *root) 
{ 
    if(root != NULL) 
    { 
     inOrder(root->left); 
     printf("%lf\n", root->key); 
     inOrder(root->right); 
    } 
} 

void inOrderDecreasing(struct node *root) 
{ 
    if(root != NULL) 
    { 
     inOrderDecreasing(root->right); 
     printf("%lf\n", root->key); 
     inOrderDecreasing(root->left); 
    } 
} 

否则，你只交换两个顶尖的孩子，但剩下的部分仍然是有序的。