首页 笔记 数据结构

# 一、二叉搜索树

# 1. 二叉搜索树是什么

二叉搜索树（BST，Binary Search Tree), 又称二叉排序树或二叉查找树，是一棵二叉树，可以为空，当不为空时满足以下性质：

  • 非空左子树的所有键值小于其根结点的键值
  • 非空右子树的所有键值大于其根结点的键值
  • 左、右子树都为二叉搜索树
    图源百度百科

# 2. 二叉搜索树的操作函数

# (1) 二叉搜索树的查找操作 Find

要查找的值为 X

  • 从根结点开始查找，若树为空，则返回 NULL
  • 若搜索树非空，则将 X 与根节点的键值进行比较并进行以下处理
    1. 若 X 小于根结点键值，则在左子树中搜索
    2. 若 X 大于根结点键值，则在右子树中搜索
    3. 若 X 与根结点键值相等，则搜索完成，返回指向该结点的指针

# 尾递归实现

Position Find(ElementType X, BinTree BST) {
 if( !BST ) return NULL;// 查找失败
 if( X > BST->Data )
  return Find(X, BST->Right);// 操作 1
 else if (X < BST->Data) 
  return Find(X, BST->Left); // 操作 2
 else 
  return BST; // 操作 3 查找成功
}

# 迭代函数实现

Position Find(ElementType X, BinTree BST) {
 while(BST) {
  if (X > BST->Data)
   BST = BST->Right;// 操作 1
  else if (X < BST->Data)
   BST = BST->Left;// 操作 2
  else 
   return BST;// 操作 3 查找成功
 }
 return NULL;// 查找失败
}

# (2) 查找最大元素和最小元素

  • 最大元素一定是在树的最右分支的端结点上
  • 最小元素一定是在树的最左分支的端结点上
    在这里插入图片描述

# 查找最大元素

递归函数

Position FindMin(BinTree BST) {
 if (!BST ) return NULL;// 空树，返回 NULL
 else if ( !BST->Left )
  return BST; // 找到了最左叶结点
 else 
  return FindMin(BST->Left);// 沿左分支继续查找
}

迭代函数

Position FindMin(BinTree BST) { 
 if (BST) {
  while (BST->Left) BST = BST->Left;
 }
 return BST;
}

# 查找最小元素

递归函数

Position FindMax(BinTree BST) {
 if (!BST ) return NULL;// 空树，返回 NULL
 else if ( !BST->Right )
  return BST; // 找到了最左叶结点
 else 
  return FindMin(BST->Right);// 沿右分支继续查找
}

迭代函数

Position FindMax(BinTree BST) { 
 if (BST) {
  while (BST->Right) BST = BST->Right;
 }
 return BST;
}

# (3) 二叉搜索树的插入

要保证插入后还为二叉搜索树，关键时要找到元素应该插入的位置。

BinTree Insert(ElementType X, BinTree BST) {
 if(!BST) { // 原树为空，生成并返回一个结点的二叉搜索树
  BST = malloc(sizeof(struct TreeNode));
  BST->Data = X;
  BST->Left = BST->Right = NULL;
 } else { // 开始寻找待插入元素的位置
  if (X < BST->Data)
   BST->Left = Insert(X, BST->Left);
  else if (X > BST->Data)
   BST->Right = Insert(X, BST->Right);
  else printf("该值已存在"); 
 }
 return BST;
}

# (4) 二叉搜索树的删除

考虑三种情况

  • 要删除的是叶结点：直接删除，并修改其父结点的指针
  • 要删除的结点只有一个孩子结点：将其父节点的指针指向要删除结点的孩子结点在这里插入图片描述
  • 要删除的结点有左、右两棵子树：要用另一个结点替代被删除的结点（右子树的最小元素或左子树的最大元素）
BinTree Delete(ElementType X, BinTree BST) {
 Position Tmp;
 if(!BST) printf("要删除的元素未找到");
 else if (X < BST->Data) 
  BST->Left = Delete(X,BST->Left);
 else if (X > BST->Data) 
  BST->Right = Delete(X,BST->Right);
 else { // 找到了要删除的结点
  if (BST->Left && BST->Right) { // 待删除结点有左右两个孩子
   Tmp = FindMin(BST->Right); // 在右子树中找最小的元素填充删除节点
   BST->Data = Tmp->Data;
   BST->Right = Delete(BST->Data,BST->Right);// 填充完后，在右子树中删除该最小元素
  }
  else { // 待删除结点有 1 个或无子结点
   Tmp = BST;
   if (!BST->Left) // 有有孩子或无子节点
    BST = BST->Right;
   else if (!BST->Right)
    BST = BST->Left;
   free(Tmp);
  }
 }
 return BST;
}

# 二、平衡二叉树

# 1. 平衡二叉树是什么

平衡二叉树（AVL 树，Banlanced Binary Tree ), 可以为空，当不为空时满足以下性质：

  • 任一结点左、右子树高度差的绝对值不超过 1
  • 给定结点数为 n 的 AVL 树的最大高度为 O (log2n)!

平衡因子（BF,Banlanced Factor）:BF(T) = hL-hR,hL 和 hR 分别为 T 的左、右子树高度

# 2. 平衡二叉树的调整

# RR 插入 ——RR 旋转【右单旋】

破坏结点（麻烦结点）位于被破坏结点（发现者）的右子树的右子树上
在这里插入图片描述

# LL 插入 ——LL 旋转【左单旋】

破坏结点（麻烦结点）位于被破坏结点（发现者）的左子树的左子树上
在这里插入图片描述

# LR 插入 ——LR 旋转

破坏结点（麻烦结点）位于被破坏结点（发现者）的左子树的右子树上
在这里插入图片描述

# RL 插入 ——RL 旋转

破坏结点（麻烦结点）位于被破坏结点（发现者）的右子树的左子树上
在这里插入图片描述

# ps：有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子

# 3. 平衡二叉树实现

# 定义部分

typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
 ElementType Data;
 AVLTree Left, Right;
 int Height;
};
int Max(int a, int b) {
 return a>b?a:b;
}

# 左单旋

ps:A 必须要有一个左子节点 B，将 A 与 B 进行左单旋，并更新 A 与 B 的高度返回新的根结点 B

AVLTree SingleLeftRotation(AVLTree A) {
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( GetHeight(B->Left),A->Height ) + 1;
 return B;
}

# 右单旋

ps:A 必须要有一个右子节点 B，将 A 与 B 进行右单旋，并更新 A 与 B 的高度返回新的根结点 B

AVLTree SingleRightRotation(AVLTree A) {
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
 return B;
}

# LR 旋转

ps:A 必须要有一个左子节点 B，且 B 必须有一个右子节点 C
先将 B 与 C 做右单旋，返回 C
再将 A 与 C 做左单旋，返回 C

AVLTree DoubleLeftRightRotation(AVLTree A) {
 A->Left = SingleRightRotation(A->Left);
 return SingleLeftRotation(A);
}

# RL 旋转

ps:A 必须要有一个右子节点 B，且 B 必须有一个左子节点 C
先将 B 与 C 做左单旋，返回 C
再将 A 与 C 做右单旋，返回 C

AVLTree DoubleRightLeftRotation(AVLTree A) {
 A->Right = SingleLeftRotation(A->Right);
 return SingleRightRotation(A);
}

# 插入

将 X 插入 AVL 树 T 中，并返回调整后的 AVL 树

AVLTree Insert(AVLTree T,ElementType X) {
 if (!T) { // 若要插入的树是空树，则新建一个包含结点 X 的树
  T = (AVLTree) malloc(sizeof(struct AVLNode));
  T->Data = X;
  T->Height = 0;
  T->Left = T->Right = NULL;
 } else if( X < T->Data) {
  T->Left = Insert(T->Left, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {// 需要左旋
   if (X < T->Left->Data)
    T = SingleLeftRotation(T); // 需要左单旋
   else 
    T = DoubleLeftRightRotation(T);// 左 - 右双旋
  }
 } else if (X > T->Data) {
  T->Right = Insert(T->Right, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {// 需要右旋
   if (X > T->Right->Data)
    T = SingleRightRotation(T); // 需要右单旋
   else 
    T = DoubleRightLeftRotation(T);// 右 - 左双旋
  }
 }
 // 更新树高
 T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
 return T;
}

# 完整代码演示

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
 ElementType Data;
 AVLTree Left, Right;
 int Height;
};
int Max(int a, int b) {
 return a>b?a:b;
}
int GetHeight(AVLTree A) {
    if (A)
        return A->Height;
    else 
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A) {// 左单旋
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( GetHeight(B->Left),A->Height )+ 1;
 return B;
}
AVLTree SingleRightRotation(AVLTree A) {// 右单旋
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
 B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
 return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A) {// 左 - 右双旋
 A->Left = SingleRightRotation(A->Left);
 return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A) {// 右 - 左双旋
 A->Right = SingleLeftRotation(A->Right);
 return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T,ElementType X) {// 将 X 插入 AVL 树 T 中
 
 if (!T) { // 若要插入的树是空树，则新建一个包含结点 X 的树
  T = (AVLTree) malloc(sizeof(struct AVLNode));
  T->Data = X;
  T->Height = 0;
  T->Left = T->Right = NULL;
        
 } else if( X < T->Data) {
  T->Left = Insert(T->Left, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {// 需要左旋
   if (X < T->Left->Data)
    T = SingleLeftRotation(T); // 需要左单旋
   else 
    T = DoubleLeftRightRotation(T);// 左 - 右双旋
  }
 } else if (X > T->Data) {
  T->Right = Insert(T->Right, X);
  if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {// 需要右旋
   if (X > T->Right->Data)
    T = SingleRightRotation(T); // 需要右单旋
   else 
    T = DoubleRightLeftRotation(T);// 右 - 左双旋
  }
 }
 // 更新树高
 T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
    return T;
}
void PreOrderTraversal(AVLTree T) {
 if(T) {
  printf("%d", T->Data);
  PreOrderTraversal( T->Left);
  PreOrderTraversal( T->Right);
 }
}
void InOrderTraversal(AVLTree T) {
 if(T) {
  InOrderTraversal( T->Left);
  printf("%d", T->Data);
  InOrderTraversal( T->Right);
 }
}
int main() {
    AVLTree T = NULL;
    int i;
    for (i = 1; i < 10; i++) {
        T = Insert(T,i);
    }
    PreOrderTraversal(T);// 前序遍历
    printf("\n");
    InOrderTraversal(T);// 中序遍历
    return 0;
}

输出结果：

421365879
123456789

根据前序遍历与中序遍历易还原得到这样一个平衡二叉树

在这里插入图片描述

# 三、判断是否同一棵二叉搜索树

题意：给定一个插入序列确定唯一一棵二叉搜索树，对于输入的各种插入序列，判断它们是否能生成一样的二叉搜索树

如何判断两个序列是否对应相同搜索树呢
建一棵树，再判别其他序列是否与该树一致！
如输入 3 1 4 2 确定一颗二叉搜索树，判断 3 4 1 2 和 3 2 4 1 是否对应同一棵树

# 1. 搜索树表示

typedef struct TreeNode *Tree;
struct TreeNode {
 int v;
 Tree Left,Right;
 int flag; // 用来标记该结点是否已经被搜索过 为 1 则搜索过
};

# 2. 建搜索树 T

Tree MakeTree(int N) {
 Tree T;
 int i, V;
 scanf("%d", &V);
 T = NewNode(V);
 for(i = 1; i < N; i++) {
  scanf("%d",&V);
  T = Insert(T,V);// 将剩余结点插入二叉树
 }
 return T;
}
Tree NewNode(int V) {
 Tree T = (Tree)malloc(sizeof(struct TreeNode));
 T->v = V;
 T->Left = T->Right = NULL;
 T->flag = 0;
 return T;
}
Tree Insert(Tree T, int V) {
 if(!T) T = NewNode(V);
 else {
  if (V > T->v) 
   T->Right = Insert(T->Right, V);
  else 
   T->Left = Insert(T->Left,V);
 }
 return T;
}

# 3. 判别一序列是否与搜索树 T 一致

方法：在树 T 中按顺序搜索序列 3 2 4 1 中的每个数

  • 若每次搜索所经过的结点在前面均搜索过，则一致
  • 否则（某次搜索中遇到了前面未出现的结点），则不一致
int check(Tree T,int V) {
 if(T->flag) {// 这个点查找过了，则判断要在左子树还是右子树查找
  if(V < T->v) return check(T->Left,V);
  else if(V > T->v) return check(T->Right,V);
  else return 0;
 }
 else { // 要查找的刚好是这个点，进行标记
  if(V == T->v) {
   T->flag = 1;
   return 1;
  }
  else return 0; // 碰到了以前没见过的点
 }
}

判断长度为 N 的插入序列产生的树是否与搜索树一致

int Judge(Tree T,int N) {
 int i, V, flag = 0;//flag=0 代表当前还一致，为 1 则说明已经不一致了
 scanf("%d",&V);
 if (V != T->v) flag = 1;
 else T->flag = 1;
 for(i = 1; i < N; i++) {
  scanf("%d", &V);
  if( (!flag) && (!check(T,V)) ) flag = 1;
 }
 if(flag) return 0;
 else return 1;
}

清除 T 中个结点的 flag 标记使其为 0

void ResetT(Tree T) {
 if(T->Left) ResetT(T->Left);
 if(T->Right) ResetT(T->Right);
 T->flag = 0;
}

释放 T 的空间

void FreeTree(Tree T) {
 if(T->Left) FreeTree(T->Left);
 if(T->Right) FreeTree(T->Right);
 free(T);
}