c - 逆序打印 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);
    }
}

否则，你只交换了前两个 child ，但剩下的部分仍然是有序的。