树

#include <stdio.h>
#include <stdlib.h>
// 树存储结构
typedef struct BiTNode {
  int data;
  struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, * BiTree;

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50   // 定义队列中元素的最大个数
typedef struct {
  BiTree data[MaxSize]; // 存放队列元素
  int front, rear;   // 队头和队尾指针 
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
  Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
  return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, BiTree e) {
  if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
  Q.data[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
  return true;
}

// 出队
bool Queue_De(SqQueue &Q, BiTree &e) {
  if (Queue_Empty(Q)) return false; // 队空则报错
  e = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
  return true;
}

// 通过给定数组创建二叉树，0为空结点
// nums 为数组、len 为数组长度、i 为当前数组下标
BiTNode * BiTree_Create (char* nums, int len , int i) {
  if (i >= len || nums[i] == 0) return NULL;
  BiTNode * node = (BiTNode *)malloc(sizeof(BiTNode));
  node->data = nums[i];
  node->lchild = BiTree_Create(nums, len, 2 * i + 1);
  node->rchild = BiTree_Create(nums, len, 2 * i + 2);
  return node;
}

// 先序遍历: 根左右(NLR)
void Order_Pre(BiTree tree) {
  if(tree == NULL) return;
  printf("%d,", tree->data);  // 访问根树内容
  Order_Pre(tree->lchild); // 递归遍历左子树
  Order_Pre(tree->rchild); // 递归遍历右子树
}

// 中序遍历: 左根右(LNR)
void Order_In(BiTree tree) {
  if(tree == NULL) return;
  Order_In(tree->lchild); // 递归遍历左子树
  printf("%d,", tree->data);  // 访问根树内容
  Order_In(tree->rchild); // 递归遍历右子树
}

// 后序遍历: 左根右(LRN)
void Order_Post(BiTree tree) {
  if(tree == NULL) return;
  Order_Post(tree->lchild); // 递归遍历左子树
  Order_Post(tree->rchild); // 递归遍历右子树
  printf("%d,", tree->data);  // 访问根树内容
}

// 层次遍历
void Order_Level (BiTree tree) {
  SqQueue Q; // 初始化队列
  Queue_Init(Q);
  BiTree p;
  Queue_En(Q, tree); // 根节点入队
  while (!Queue_Empty(Q)) { // 队列不空则继续遍历
    Queue_De(Q, p); // 队头结点出队
    printf("%d,", p->data); // 访问出队结点内容
    if (p->lchild != NULL)
      Queue_En(Q, p->lchild); // 左子树不为空，则左子树根入队
    if (p->rchild != NULL)
      Queue_En(Q, p->rchild); // 右子树不为空，则右子树根入队
  }
}

int main() {
  char nums[11] = {1, 2, 3, 0, 4, 0, 5, 0, 0, 6, 0};
  BiTree tree = BiTree_Create(nums, 11, 0);
  printf("先序遍历：");
  Order_Pre(tree);
  printf("\n");

  printf("中序遍历：");
  Order_In(tree);
  printf("\n");

  printf("后序遍历：");
  Order_Post(tree);
  printf("\n");

  // 层次遍历需要借助队列实现
  printf("层次遍历: ");
  Order_Level(tree);

  return 0;
}

二叉排序树-链式存储

#include <stdio.h>
#include <stdlib.h>
// 树存储结构
typedef struct BiTNode {
  int data;
  struct BiTNode *lchild, *rchild; // 左右孩子指针
} BSTNode, * BSTree;

// 循环队列算法，辅助完成二叉树层次遍历
#define MaxSize 50   // 定义队列中元素的最大个数
typedef struct {
  BSTree data[MaxSize]; // 存放队列元素
  int front, rear;   // 队头和队尾指针 
} SqQueue;

// 初始化队列（带头结点）
void Queue_Init(SqQueue &Q) {
  Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool Queue_Empty(SqQueue Q) {
  return Q.front == Q.rear;
}

// 入队
bool Queue_En(SqQueue &Q, BSTree e) {
  if ((Q.rear + 1) % MaxSize == Q.front) return false; // 队满则报错
  Q.data[Q.rear] = e;
  Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针加 1 取模
  return true;
}

// 出队
bool Queue_De(SqQueue &Q, BSTree &e) {
  if (Queue_Empty(Q)) return false; // 队空则报错
  e = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
  return true;
}

// 插入关键字为 k 的新结点
int BST_Insert (BSTree &tree, int s) {
  if (tree == NULL) { // 传入的为空节点，新插入的结点为根节点
    tree = (BSTNode *)malloc(sizeof(BSTNode));
    tree->data = s;
    tree->lchild = tree->rchild = NULL;
    return 1;
  }
  else if (s == tree->data) return 0; // 相同节点，失败
  else if (s < tree->data) // 插入到 tree 的左子树
    return BST_Insert(tree->lchild, s);
  else if (s > tree->data) // 插入到 tree 的右子树
    return BST_Insert(tree->rchild, s);
}

// tree 根节点、 nums 数组、len 数组长度
void BST_Create (BSTree &tree, char* nums, int len) {
  tree = NULL;
  for (int i = 0; i < len; i++) {
    BST_Insert(tree, nums[i]);
  }
}

// 删除结点
void BST_Delete (BSTree &tree, int e) {
  // 要删除的结点
  BSTree p = tree;
  // 要删除结点的父结点
  BSTree f = NULL;

  while (p) { // 查找
    if (p->data == e) {
      break; // 找到指定结点，结束循环
    }
    f = p; // 记录要删除结点的父结点
    if (p->data > e)
      p = p->lchild; // 在 p 的左子树中查找
    else
      p = p->rchild; // 在 p 的右子树中查找
  }

  // 要删除的结点不存在
  if (!p) return;

  // 二叉树待删除结点有四种情况
  // 待删除的为叶子结点、仅有一颗子节点树、左右子树均不为空
  // 情况1：要删除的结点为叶子结点，直接删除
  if (p->lchild == NULL && p->rchild == NULL) {
    if (f == NULL)
      tree = NULL; // 删除根结点
    else if (p == f->lchild)
      f->lchild == NULL; // 删除左子树结点
    else
      f->rchild = NULL; // 删除右子树结点
    free(p);
  }
  // 情况2：要删除的结点只有一个子树
  else if (p->lchild == NULL) { // 仅有右子树
    if (f == NULL)
      tree = p->rchild; // 删除根节点
    else if (p == f->lchild)
      f->lchild = p->rchild; // 删除左子树
    else
      f->rchild = p->rchild; // 删除右子树
    free(p);
  }
  else if (p->rchild == NULL) { // 仅有左子树
    if (f == NULL)
      tree = p->lchild; // 删除根节点
    else if (p == f->lchild)
      f->lchild = p->lchild; // 删除左子树
    else
      f->rchild = p->lchild; // 删除右子树
    free(p);
  }
  // 情况3: 左右子树均不为空
  else if (p->lchild && p->rchild) {
    BSTree s = p->lchild; // 待替换p的结点
    BSTree sf = p; // 指向 s 结点的父
    // 左子树中找到最大的值（即最右的结点）
    while (s->rchild) {
      sf = s;
      s = s->rchild; // 往最右下走
    }
    p->data = s->data; // 替换值，然后删除

    if (s == sf->lchild) {
      // s为sf的左子树，由于s已经为最大结点，所以s没有右子树
      sf->lchild = s->lchild;
    } else {
      // s为sf的右子树，由于s已经为最大结点，所以s没有右子树
      sf->rchild = s->lchild;
    }
    free(s);
  }
}

// 先序遍历: 根左右(NLR)
void Order_Pre(BSTree tree) {
  if(tree == NULL) return;
  printf("%d,", tree->data);  // 访问根树内容
  Order_Pre(tree->lchild); // 递归遍历左子树
  Order_Pre(tree->rchild); // 递归遍历右子树
}

// 中序遍历: 左根右(LNR)
void Order_In(BSTree tree) {
  if(tree == NULL) return;
  Order_In(tree->lchild); // 递归遍历左子树
  printf("%d,", tree->data);  // 访问根树内容
  Order_In(tree->rchild); // 递归遍历右子树
}

// 后序遍历: 左根右(LRN)
void Order_Post(BSTree tree) {
  if(tree == NULL) return;
  Order_Post(tree->lchild); // 递归遍历左子树
  Order_Post(tree->rchild); // 递归遍历右子树
  printf("%d,", tree->data);  // 访问根树内容
}

// 层次遍历
void Order_Level (BSTree tree) {
  SqQueue Q; // 初始化队列
  Queue_Init(Q);
  BSTree p;
  Queue_En(Q, tree); // 根节点入队
  while (!Queue_Empty(Q)) { // 队列不空则继续遍历
    Queue_De(Q, p); // 队头结点出队
    printf("%d,", p->data); // 访问出队结点内容
    if (p->lchild != NULL)
      Queue_En(Q, p->lchild); // 左子树不为空，则左子树根入队
    if (p->rchild != NULL)
      Queue_En(Q, p->rchild); // 右子树不为空，则右子树根入队
  }
}

int main() {
  char nums[11] = {50,30,60,40,70,10,20,80};
  BSTree tree;
  BST_Create(tree, nums, 11);
  printf("先序遍历：");
  Order_Pre(tree);
  printf("\n");

  printf("中序遍历：");
  Order_In(tree);
  printf("\n");

  printf("后序遍历：");
  Order_Post(tree);
  printf("\n");

  // 层次遍历需要借助队列实现
  printf("层次遍历: ");
  Order_Level(tree);

  return 0;
}

哈夫曼树-顺序存储

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

// 树存储结构
typedef struct HTNode {
  int weight; // 权值
  char data; // 待编码字符
  int parent; // 父节点
  int lchild, rchild; // 左右孩子
} HTNode, * HuffmanTree;

typedef char **HuffmanCode; // 字符指针数组中存储的元素类型

// 查找在 0 到 i 中的两个最小值，且没有被处理过(parent == 0)
void Select(HuffmanTree &HT, int n, int &min1, int &min2) {
    int min;
    // 找到第一个最小值
    for (int i = 0; i < n; i++) {
        if (HT[i].parent == 0) {
            min = i;
            break;
        }
    }
    for (int i = min + 1; i < n; i++) {
        if (
            HT[i].parent == 0 &&
            HT[i].weight < HT[min].weight
        ) {
            min = i;
        }
    }
    min1 = min; // 第一个最小值给 s1
    // 找第二个最小值
    for (int i = 0; i < n; i++) {
        if (HT[i].parent == 0 && i != min1) {
            min = i;
            break;
        }
    }
    for (int i = min + 1; i < n; i++) {
        if (
            HT[i].parent == 0 &&
            HT[i].weight < HT[min].weight &&
            i != min1
        ) {
            min = i;
        }
    }
    min2 = min; // 第二个最小值
}

// 构建哈夫曼树 HT=哈夫曼树、w=权值、n=待编码数量
void Huffman_Create (HuffmanTree &HT, int *w, char *data, int n) {
  int m = 2 * n - 1; // 哈夫曼树的节点总数为 2n-1
  HT = (HuffmanTree)calloc(m, sizeof(HTNode)); // 创建 m 个结点，注意malloc和calloc区别
  for (int i = 0; i < n; i++) {
      HT[i].weight = w[i]; // 权值给 n 个叶子结点
      HT[i].data = data[i];
  }
  for (int i = n; i < m; i++) {
      int min1, min2;
      // 找到权值最小的两个结点，期中min1权值小于min2的权值
      Select(HT, i, min1, min2);
      // 新结点的左右权值为两个最小树的权值之和
      HT[i].weight = HT[min1].weight + HT[min2].weight;
      HT[min1].parent = i;
      HT[min2].parent = i;
      // 较小的为左孩子
      HT[i].lchild = min1;
      HT[i].rchild = min2;
  }
}

// 生成哈夫曼编码 HT=哈夫曼树、HC=编码结果保存(相当于二维数组)、n=待编码字符个数
void Huffman_Coding (HuffmanTree &HT, HuffmanCode &HC, int n) {
    // 开辟需要编码的个数空间(编码串地址)
    HC = (HuffmanCode)malloc(sizeof(char *) * n);
    // 辅助空间(编码串)，编码最长为n-1
    char *code = (char*)malloc(sizeof(char) * n); // 字符串最后一位\0表示结束
    code[n - 1] = '\0';
    for (int i = 0; i < n; i++) {
        int j = i; // 当前第i个数据的编码
        int p = HT[j].parent; // 找到该数据的根结点
        // 由于是从编码结点一直向上找父，所以编码顺序是相反的
        int start = n - 1; // 那么存储编码的时候从最后面开始存即编码正序了
        // 直到父结点为0，即父结点为根节点时停止
        while (p) {
            // 如果该节点是其父结点的左孩子，则编码为0，否则为1
            if (HT[p].lchild == j)
                code[--start] = '0';
            else
                code[--start] = '1';
            j = p; // 继续向上进行编码
            p = HT[j].parent; // j 的父节点
        }
        // 由于code是整个n长度，所以这里从新根据编码长度开辟存储编码的空间
        HC[i] = (char*)malloc(sizeof(char) * (n - start));
        strcpy(HC[i], &code[start]); // 字符串拷贝
    }
    free(code); // 释放辅助空间
}

// 打印哈夫曼树，n=编码节点个数
void HuffmanTree_Print(HuffmanTree HT, int n) {
  printf("哈夫曼树为:>\n");
  printf("下标   字符   权值     父结点   左孩子   右孩子\n");
  for (int i = 0; i < n; i++) {
    printf("%-4d   %-4c   %-6d   %-6d   %-6d   %-6d\n", i, HT[i].data, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
  }
  printf("\n");
}

void HuffmanCode_Print (HuffmanTree HT, HuffmanCode HC, int n) {
  for (int i = 0; i < n; i++) {
    printf("数据%c的编码为:%s\n", HT[i].data, HC[i]);
  }
}

int main() {
  int n = 4;
  HuffmanTree HT;
  int w[] = {7, 5, 2, 4};
  char data[] = {'a', 'b', 'c', 'd'};
  Huffman_Create(HT, w, data, n);
  HuffmanTree_Print(HT, n);

  HuffmanCode HC;
  Huffman_Coding(HT, HC, n);
  HuffmanCode_Print(HT, HC, n);
  return 0;
}

// 定义二叉树节点的数据类型为整数
#define ElemType int

// 定义二叉树节点的结构体，包括数据域，左右孩子指针，以及左右线索标记
// ltag, rtag 为 0 表示指向孩子节点的指针
//            为 1 表示指向前驱或后继线索的指针
typedef struct ThreadNode {
  ElemType data;
  struct ThreadNode *lchild, *rchild;
  int ltag, rtag;
} ThreadNode, * ThreadTree;

// 前序线索化中用于记录前驱节点的全局变量
ThreadNode *pre = NULL;

// 通过给定数组创建二叉树，0 表示空节点
// nums 为数组、len 为数组长度、i 为当前数组下标
ThreadTree Thread_Create(char* nums, int len, int i) {
  if (i >= len || nums[i] == 0) return NULL;
  // 分配内存创建新节点
  ThreadTree node = (ThreadTree)malloc(sizeof(ThreadNode));
  node->data = nums[i];
  // 递归创建左右子树
  node->lchild = Thread_Create(nums, len, 2 * i + 1);
  node->rchild = Thread_Create(nums, len, 2 * i + 2);
  node->ltag = 0;
  node->rtag = 0;
  return node;
}

// 前序线索化函数
void PreThread(ThreadTree T) {
  if (T != NULL) {
    // 当前节点的左孩子为空，建立前驱线索
    if (T->lchild == NULL) {
      T->lchild = pre;
      T->ltag = 1;  // 设置左线索标记
    }

    // 前驱节点的右孩子为空，建立后继线索
    if (pre != NULL && pre->rchild == NULL) {
      pre->rchild = T;
      pre->rtag = 1;  // 设置右线索标记
    }
    pre = T;  // 更新前驱节点

    // 递归处理左子树
    if (T->ltag == 0) {
      PreThread(T->lchild);
    }
    // 递归处理右子树
    if (T->rtag == 0) {
      PreThread(T->rchild);
    }
  }
}

// 创建前序线索二叉树
void CreatePreThread(ThreadTree T) {
  pre = NULL;  // 初始化前驱节点
  if (T != NULL) {
    PreThread(T);

    // 处理最后一个节点的后继线索
    if (pre->rchild == NULL)
      pre->rtag = 1;
  }
}

// 中序线索化函数
void InThread(ThreadTree T) {
  if (T != NULL) {
    // 递归处理左子树
    InThread(T->lchild);

    // 当前节点的左孩子为空，建立前驱线索
    if (T->lchild == NULL) {
      T->lchild = pre;
      T->ltag = 1;  // 设置左线索标记
    }

    // 前驱节点的右孩子为空，建立后继线索
    if (pre != NULL && pre->rchild == NULL) {
      pre->rchild = T;
      pre->rtag = 1;  // 设置右线索标记
    }
    pre = T;  // 更新前驱节点

    // 递归处理右子树
    InThread(T->rchild);
  }
}

// 创建中序线索二叉树
void CreateInThread(ThreadTree T) {
  pre = NULL;  // 初始化前驱节点
  if (T != NULL) {
    InThread(T);

    // 处理最后一个节点的后继线索
    if (pre->rchild == NULL) {
      pre->rtag = 1;
    }
  }
}

// 后序线索化函数
void PostThread(ThreadTree T) {
  if (T != NULL) {
    // 递归处理左子树
    PostThread(T->lchild);

    // 递归处理右子树
    PostThread(T->rchild);
    // 当前节点的左孩子为空，建立前驱线索
    if (T->lchild == NULL) {
      T->lchild = pre;
      T->ltag = 1;  // 设置左线索标记
    }

    // 前驱节点的右孩子为空，建立后继线索
    if (pre != NULL && pre->rchild == NULL) {
      pre->rchild = T;
      pre->rtag = 1;  // 设置右线索标记
    }

    pre = T;  // 更新前驱节点
  }
}

// 创建后序线索二叉树
void CreatePostThread(ThreadTree T) {
  pre = NULL;  // 初始化前驱节点
  if (T != NULL) {
    PostThread(T);

    // 处理最后一个节点的后继线索
    if (pre->rchild == NULL) {
      pre->rtag = 1;
    }
  }
}

// 前序线索二叉树的前序遍历输出
void PreThreadTraverse(ThreadTree T) {
  if (T != NULL) {
    printf("%d ", T->data);  // 输出节点数据
    // 如果左孩子不是线索节点，递归遍历左子树
    if (T->ltag == 0) {
      PreThreadTraverse(T->lchild);
    }
    // 如果右孩子不是线索节点，递归遍历右子树
    if (T->rtag == 0) {
      PreThreadTraverse(T->rchild);
    }
  }
}

// 中序线索二叉树的中序遍历输出
void InThreadTraverse(ThreadTree T) {
  if (T != NULL) {
    // 递归遍历左子树
    if (T->ltag == 0) {
      InThreadTraverse(T->lchild);
    }
    printf("%d ", T->data);  // 输出节点数据
    // 递归遍历右子树
    if (T->rtag == 0) {
      InThreadTraverse(T->rchild);
    }
  }
}

// 后序线索二叉树的后序遍历输出
void PostThreadTraverse(ThreadTree T) {
  if (T != NULL) {
    // 递归遍历左子树
    if (T->ltag == 0) {
      PostThreadTraverse(T->lchild);
    }
    // 递归遍历右子树
    if (T->rtag == 0) {
      PostThreadTraverse(T->rchild);
    }
    printf("%d ", T->data);  // 输出节点数据
  }
}

int main() {
  // 创建测试二叉树
  char nums[11] = {1, 2, 3, 0, 4, 0, 5, 0, 0, 6, 0};
  ThreadTree preTree = Thread_Create(nums, 11, 0);
  ThreadTree inTree = Thread_Create(nums, 11, 0);
  ThreadTree postTree = Thread_Create(nums, 11, 0);

  // 创建前序线索二叉树
  CreatePreThread(preTree);

  // 输出前序遍历结果
  printf("前序遍历结果：");
  PreThreadTraverse(preTree);
  printf("\n");

  // 创建中序线索二叉树
  CreateInThread(inTree);

  // 输出中序遍历结果
  printf("中序遍历结果：");
  InThreadTraverse(inTree);
  printf("\n");

  // 创建后序线索二叉树
  CreatePostThread(postTree);

  // 输出后序遍历结果
  printf("后序遍历结果：");
  PostThreadTraverse(postTree);
  printf("\n");

  return 0;
}

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

typedef struct TreeNode {
  struct TreeNode* lchild;
  struct TreeNode* rchild;
  int data;
  int height; // 新增一个高度字段
} TreeNode;

// 计算节点的高度
int height(TreeNode* node) {
  if (node == NULL)
    return -1;
  return node->height;
}

// 更新节点的高度
void updateHeight(TreeNode* node) {
  // 计算左子树的高度
  int leftHeight = height(node->lchild);
  // 计算右子树的高度
  int rightHeight = height(node->rchild);
  // 将节点的高度设置为左右子树中较大的高度加1
  // 这样可以确保节点的高度是其子树高度的最大值加1
  node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 获取节点的平衡因子
int getBalanceFactor(TreeNode* node) {
  if (node == NULL)
    return 0;
  return height(node->lchild) - height(node->rchild);
}

// 单旋转 - LL平衡旋转（右单旋转）
TreeNode* LL(TreeNode* node) {
  // 创建一个指针 newRoot，用来存储将要成为新根节点的左孩子
  TreeNode* newRoot = node->lchild;
  // 将原根节点的左孩子设置为 newRoot 的右孩子
  node->lchild = newRoot->rchild;
  // 将原根节点作为 newRoot 的右孩子
  newRoot->rchild = node;

  // 更新节点高度
  updateHeight(node);
  updateHeight(newRoot);
  // 返回新的根节点
  return newRoot;
}

// 单旋转 - RR平衡旋转（左单旋转）
TreeNode* RR(TreeNode* node) {
  // 将右孩子作为新的根节点
  TreeNode* newRoot = node->rchild;
  // 将原根节点的左孩子设置为新根节点的左孩子
  node->rchild = newRoot->lchild;
  // 将原根节点作为新根节点的左孩子
  newRoot->lchild = node;

  // 更新节点高度
  updateHeight(node);
  updateHeight(newRoot);
  // 返回新的根节点
  return newRoot;
}

// 插入节点
TreeNode* insert(TreeNode* root, int data) {
  // 如果树为空，创建一个新节点并返回
  if (root == NULL) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    newNode->height = 0;
    return newNode;
  }

  // 如果要插入的数据小于当前节点的数据，插入到左子树中
  if (data < root->data)
    root->lchild = insert(root->lchild, data);
  // 如果要插入的数据大于当前节点的数据，插入到右子树中
  else if (data > root->data)
    root->rchild = insert(root->rchild, data);
  else
    return root; // 已存在相同值的节点，不插入

  // 更新节点高度
  updateHeight(root);

  // 获取平衡因子
  int balance = getBalanceFactor(root);

  // 平衡维护
  // 平衡因子 大于 0 则是左孩子，小于 0 则是右孩子
  // 插入的数据在左孩子的左子树 LL
  if (balance > 1 && data < root->lchild->data)
    return LL(root);

  // 插入的数据在右孩子的右子树 RR
  if (balance < -1 && data > root->rchild->data)
    return RR(root);

  // 插入的数据在左孩子的右子树 LR
  if (balance > 1 && data > root->lchild->data) {
    root->lchild = RR(root->lchild);
    return LL(root);
  }

  // 插入的数据在右孩子的左子树 RL
  if (balance < -1 && data < root->rchild->data) {
    root->rchild = LL(root->rchild);
    return RR(root);
  }

  return root; // 返回更新后的根节点
}

// 前序遍历以打印树的内容
void preorderTraversal(TreeNode* root) {
  if (root == NULL)
    return;

  printf("%d ", root->data);
  preorderTraversal(root->lchild);
  preorderTraversal(root->rchild);
}

// 中序遍历以打印树的内容
void inorderTraversal(TreeNode* root) {
  if (root == NULL)
    return;

  inorderTraversal(root->lchild);
  printf("%d ", root->data);
  inorderTraversal(root->rchild);
}

// 主函数
int main() {
  int arr[6] = {15, 3, 7, 10, 9, 8};

  TreeNode* root = NULL;
  for (int i = 0; i < 6; i++) {
    root = insert(root, arr[i]);
  }

  printf("中序遍历结果：");
  inorderTraversal(root);
  printf("\n");

  printf("前序遍历结果：");
  preorderTraversal(root);
  return 0;
}