void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 先访问根节点
    // 然后遍历子节点
    for (int i = 0; i < root->numChildren; ++i) {
        preOrderTraversal(root->children[i]);
    }
}

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 先遍历子节点
    for (int i = 0; i < root->numChildren; ++i) {
        postOrderTraversal(root->children[i]);
    }
    // 然后访问根节点
}

#define MAX_SIZE 100

ElementType tree[MAX_SIZE];

ElementType lchild(int index) {
    return tree[2 * i + 1];
})

ElementType rchild(int index) {
    return tree[2 * i + 2];
}

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    // operation here
    inorderTraversal(root->right); // 遍历右子树
}

void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 遍历左子树
    inorderTraversal(root->right); // 遍历右子树
    // operation here
}

// 层次遍历二叉树
void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Queue* queue = createQueue();
    enqueue(queue, root);

    while (queue->front != NULL) {
        struct TreeNode* current = dequeue(queue);
        // operation here

        if (current->left != NULL) {
            enqueue(queue, current->left);
        }

        if (current->right != NULL) {
            enqueue(queue, current->right);
        }
    }
}

// 中序遍历，找到中序遍历的第一个节点，然后遍历 rchild 即可
void InOrder(ThreadNode *n) {
    ThreadNode *p = n;
    while (p->lchild) {
        p = p->lchild;
    }
    for (; p != NULL; p = p->rchild) {
        visit(p);
    }
}

// 插入新节点
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

// 查找节点
TreeNode* search(TreeNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    }
    return search(root->right, data);
}

// 删除节点
TreeNode* deleteNode(TreeNode* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = deleteNode(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNode(root->right, data);
    } else {
        // 节点有一个或没有子节点
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // 节点有两个子节点，找到右子树的最小节点
        TreeNode* temp = findMin(root->right);

        // 复制右子树的最小节点的值
        root->data = temp->data;

        // 删除右子树的最小节点
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

struct TreeNode* leftRotate(struct TreeNode* x) {
    struct TreeNode* y = x->right;
    struct TreeNode* T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;
}

struct TreeNode* rightRotate(struct TreeNode* y) {
    struct TreeNode* x = y->left;
    struct TreeNode* T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;
}

// 计算以 node 为根节点的子树高度
int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 获取平衡因子
int getBalanceFactor(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 在插入时需要使用该操作，重新计算子树高度
void updateHeight(struct TreeNode* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

struct TreeNode* insert(struct TreeNode* node, int data) {
    // 步骤 1：执行标准 BST 插入
    if (node == NULL) {
        return createNode(data);
    }

    if (data < node->data) {
        node->left = insert(node->left, data);
    } else if (data > node->data) {
        node->right = insert(node->right, data);
    } else { // 如果键值相等，则不插入
        return node;
    }

    // 步骤 2：更新节点的高度
    updateHeight(node);

    // 步骤 3：获取节点的平衡因子
    int balanceFactor = getBalanceFactor(node);

    // 步骤 4：平衡调：根据新插入结点的位置 相对于 最小不平衡子树根节点的位置进行旋转
    // LL 型：右旋
    if (balanceFactor > 1 && data < node->left->data) {
        return rightRotate(node);
    }
    // RR 型：左旋
    if (balanceFactor < -1 && data > node->right->data) {
        return leftRotate(node);
    }
    // LR 型：先左旋，再右旋
    if (balanceFactor > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    // RL 型：先右旋，再左旋
    if (balanceFactor < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 返回未被修改的节点指针
    return node;
}