Lipsky

树和二叉树

字数统计: 7.3k阅读时长: 30 min
2019/05/27 Share

树与二叉树#

树(上)#

引子#

查找:根据某个给定关键字 K,从集合 R 中找出关键字与 K 相同的记录#

  • 静态查找:集合中记录是固定的。没有插入和删除操作,只有查找

    • 顺序查找:(通过设置哨兵,进行判断是否找到元素或者是否到达表末尾)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      int SequentialSearch(list Tbl, ElementType k){
      int i;
      Tb1->Element[0] = k; //建立哨兵,最后函数返回的时候如果值为0,则没找到
      for(i = Tab->Length; Tb1->Element[i]!=k; i--);
      return i;
      }

      typedef struct LNode *List;
      struct LNode{
      ElementType Element[MAXSIZE];
      int Length;
      };

      顺序查找的时间复杂度为 O(n)

    • 二分查找(Binary Search)

      假设 n 个数据元素的关键字满足有序(比如:小到大)

      并且是连续存放(数组),那么可以进行二分查找。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int BinarySearch(List Tal, ElementType K){
      int left, right, mid, NoFound = -1;

      left = 1; /*初始左边界*/
      right = Tbl->Length;
      while(left <= right){
      mid = (left+right)/2;
      if(K < Tbl->Element[mid]) right = mid-1;
      else if(K > Tbl->Element[mid]) left = mid+1;
      else return mid;
      }
      return NotFound; /*查找不成功,返回-1*/
      }

      11个元素的二分查找判定树

      Screen Shot 2019-05-27 at 22.16.28

      平均成功查找次数:

      ASL = (4*4 + 4*3 + 2*2 + 1)/11 = 3

  • 动态查找:集合中记录是动态变化的,除查找,还可能发生插入和删除

树形结构#

  • 二叉树
    • 概念:
      • 定义
      • 存储结构
    • 操作:
      • 三种遍历
      • 线索二叉树
    • 应用:
      • 排序二叉树—平衡二叉树
      • 哈夫曼树
  • 树和森林:
    • 概念:
      • 定义
      • 存储结构
    • 操作:
      • 与二叉树的转换
      • 遍历
    • 应用:并查集

树的定义#

树:n(n≥0)个结点构成的有限集合#

  • 当 n=0时,称为空树。

对于任何一棵非空树应满足:

  • 树中有且仅有一个特定的称为”根”(root)的特殊结点,用 r 表示;
  • 其余结点可分为 m(m≥0) 个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,称为原来树的”子树”(SubTree)

image-20190528185832208

  • 树的定义是递归的,是一种递归的数据结构。同时也是一种分层结构,具有以下特点:
    • 树的根节点没有前驱结点,除根节点外所有结点有且只有一个前驱结点
    • 树中所有结点可以有零个或多个后继结点
  • 树与非树

    image-20190528191617670

  • 子树是不相交的
  • 除了根结点外,每个节点有且仅有一个父节点
  • 一棵N个结点的树有 N-1条边

树的基本术语#

  • 结点的度(Degree):结点的子树个数(也就是当前辈分为孩子的个数,不包括孙子辈)
  • 树的度:树的所有结点中最大的度数(也就是所生个数最多的同亲一代的个数)
  • 叶结点(Leaf):度为 0 的结点(也叫做终端结点,没有孩子
  • 父结点(Child):若 A 结点是 B 结点的父结点,则称 B 结点是 A 结点的子节点;子结点也称孩子结点
  • 兄弟结点(Sibling):具有同一父结点的各结点彼此是兄弟结点
  • 路径和路径长度:从结点 n1到 nk 的路径为一个结点序列n1,n2,…nk,ni是 ni+1的父结点。路径所包含边的个数为路径的长度
  • 祖先结点(Ancestor):沿树根到某一结点路径上所有结点都是这个结点的祖先结点
  • 子孙结点(Descendant):某一结点的子树中所有结点是这个结点的子孙
  • 结点的层次(Level):规定根结点在1层,其他任一结点的层次数是其父结点的层次数加1
  • 树的深度(Depth):树中所有的结点中的最大层次是这棵树的深度

树的性质#

  • 非空树的结点总数等于树中所有结点的度之和加1(也就是所有的孩子加上祖宗)
  • 度为 K 的非空树的第 i 层最多有 $k^{i-1}$ 个结点(i≥1)
  • 深度为 h 的 k 叉树最多有$\frac{k^{h}-1}{k-1}$个结点
  • 具有 n 个结点的 K 叉树的最小深度为 [$log_k(n(k-1)+1)$]

树的表示#

儿子-兄弟表示法

image-20190528210258363

image-20190528210417340

二叉树的定义#

image-20190528210558400

特殊的二叉树

  • 斜二叉树(相当于列表)

  • 完美二叉树(满二叉树)

    image-20190528210712820

  • 完全二叉树

image-20190528210806322

image-20190528210854668

二叉树的几个重要性质#

  • 一个二叉树第 i 层的最大结点数为:,i≥1.

  • 深度为 K 的二叉树有最大结点总数为:,k≥1.(完美二叉树即为这样)

  • 对任何非空二叉树(至少有一个结点的二叉树叫做非空二叉树)T,若表示叶子结点的个数、是度为 2 的非叶子结点个数,那么二者之间满足关系:

    image-20190528211956710

二叉树的抽象数据类型定义#

image-20190528212620827

二叉树的存储结构#

顺序存储结构#

完全二叉树: 按从上至下、从左到右的顺序存储

​ n个结点的完全二叉树的结点父子关系:

image-20190530193241256

性质:

  • 非根结点(序号 i > 1)的父结点的序号是[i/2];
  • 结点(序号 i )的左孩子的结点的序号是2i;(要2i ≤ n,否则没有左孩子)
  • 结点(序号 i)的右孩子结点的序号是 2i+1;(要 2i+1≤n,否则没有右孩子)

一般二叉树: 也可以使用上述的完全二叉树的结构,但会造成空间浪费

image-20190530193809024

链表存储#

image-20190530194045889

1
2
3
4
typedef struct node{
datatype data; /*数据域*/
struct node *lchild, *rchild; /*指向左、右子树的指针区域*/
}BTNode, *BTREE;

二叉树的遍历#

先序遍历 -> 根左右#

遍历过程:

  • 访问根结点
  • 先序遍历其左子树
  • 先序遍历其右子树
1
2
3
4
5
6
7
void PreOrderTraversal (BinTree BT){
if(BT){
printf("%d", BT->Data);
PreOrderTraversal(BT->Left);
PreOrderTraversal(Bt->Right);
}
}

image-20190530220249086

先序遍历=> A B D F E C G H I

中序遍历 -> 左根右#

遍历过程:

  • 中序遍历其左子树
  • 访问根结点
  • 中序遍历其右子树
1
2
3
4
5
6
7
void InOrderTraversal (BinTree BT){
if(BT){
InOrderTreaversal(BT->Left);
printf("%d", BT->Data);
InOrderTraversal(Bt->Right);
}
}

image-20190530221219337

中序遍历=> D B E F A G H C I

后序遍历 -> 左右根#

遍历过程:

  • 后序遍历其左子树
  • 后序遍历其右子树
  • 访问根结点
1
2
3
4
5
6
7
void PostOrderTraversal(BinTree Bt){
if(BT){
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d", BT->Data);
}
}

image-20190530224411282

后序遍历=> D E F B H G I C A

总结

  • 先序、中序和后续遍历过程:遍历过程中经过结点的路线一样,只是访问各结点的时机不同

二叉树的非递归遍历#

中序遍历非递归遍历算法#

非递归算法实现的基本路线:使用堆栈

算法:

  • 遇到一个结点,就把它压栈,并去遍历它的左子树;
  • 当左子树遍历结束后,从栈顶弹出这个结点并访问它;
  • 然后按其右指针再去中序遍历该结点的右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InOrderTraversal(BinTree BT){
BinTree T=BT; /*将 BT 赋给临时变量T*/
Stack S = CreatStack(MaxSize); /*创建并初始化堆栈S*/
while(T || !IsEmpty(S)){ /*树不空,或者堆栈不空*/
while(T){ /*一直向左并将沿途结点压入栈*/
Push(S,T); /*如果树不空,就将树的根结点压入栈*/
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S); /*结点弹出堆栈*/
printf("5%d", T->Data); /*(访问)打印结点*/
T = T->Right; /*转向右子树*/
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define M 50
void INORDER(BTREE T){
/*T为二叉树根结点所在链结点的地址*/
BTREE STACK[M], p = T;
int top = -1;
if(T!=NULL){
do{
while(p!=NULL){
STACK[++top] = p; /*当前 p 所指的结点地址进栈*/
p = p->lchild;
}
p = STACK[top--]; /*退栈*/
VISIT(p); /*中序遍历,当第二次碰到某一结点时,访问*/
p = p->rchild;
}while(!(p==NULL && top = -1)); /*当根结点存在,或者堆栈不为空*/ /*while( p|| top!=-1*/
}
}
先序遍历的非递归算法#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PreOrderTraversal(BinTree BT){
BinTree T = BT;
Stack S = CreatStack(Maxsize);
While(T || !IsEmpty(S)){
while(T){
Push(S,T);
printf("%5d", T->Data);
T = T->Left;
}
if(!IsEmpty(S)){
T = Pop(S);
T = T->Right;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define M 50
void INORDER(BTREE T){
/*T为二叉树根结点所在链结点的地址*/
BTREE STACK[M], p = T;
int top = -1;
if(T!=NULL){
do{
while(p!=NULL){
STACK[++top] = p; /*当前 p 所指的结点地址进栈*/
VISIT(p); /*先序遍历,当第一次碰到结点的时候,就访问*/
p = p->lchild;
}
p = STACK[top--]; /*退栈*/
p = p->rchild;
}while(!(p==NULL && top = -1));
}
}
后序遍历非递归算法#

算法:

  • 先遍历其左子树
  • 再遍历其右子树
  • 最后访问该结点

注意:

  • 当是从左子树返回时,不能访问其根结点;
  • 当是从右子树返回时,才能访问其根结点

设置标识位的后序遍历非递归算法

所以为了表明某结点是否可以被访问,引入一个标志变量 flag:

  • 当 flag = 0,表示其从左子树返回,不可访问其根结点;
  • 当 flag = 1,表示其从右子树返回,可访问其根结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define M 50
void POSTORDER(BTREE T){
/*T 为二叉树根结点所在链结点的地址*/
BTREE STACK1[M], p = T;
int STACK2[M], flag, top = -1;
if(T!=NULL){
do{
while(p!=NULL){
STACK1[++top] = p;
STACK2[top] = 0; /*标志为左子树遍历*/
p = p->lchild;
}
p = STACK1[top]; /*此退栈将栈顶指针top进行-1操作*/
flag = STACK2[top--]; /*STACK2 退栈*/
if(flag == 0){
STACK1[++top] = p; /*从左子树返回,当前结点再次进栈*/
STACK2[top] = 1; /*标志为右子树遍历*/
p = p->rchild;
}
else{
VISIT(p);
p = NULL;
}
}while(!(p==NULL && top = -1));
}
}

层序遍历#

队列实现:#

遍历从根结点开始,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队

image-20190607204536584

层序基本过程:先根结点入队,然后:

  • 从队列中取出一个元素;
  • 访问该元素所指结点;
  • 若该元素所指结点的左、右孩子结点非空,则将其左、右孩子的指针顺序入队
1
2
3
4
5
6
7
8
9
10
11
12
13
void LevelOrderTraversal(BinTree BT){
Queue Q;
BinTree T;
if(!BT) return;/*若是空树,则直接返回*/
Q = CreatQueue(MaxSize);/*创建并初始化队列Q*/
AddQ(Q, BT); /*先把根结点放至队列中*/
while(!IsEmptyQ(Q)){
T = DeleteQ(Q);
printf("%d\n", T->Data);/*访问取出队列的结点*/
if(T->Left) AddQ(Q, T->Left);
if(T->Right) AddQ(Q, T->Right);
}
}

例:遍历二叉树的应用:输出二叉树中的叶子结点#

在二叉树的遍历算法中增加检测结点的”左右子树是否都为空”。

1
2
3
4
5
6
7
8
void PreOrderPrintLeaves(BinTree BT){
if(BT){
if(!BT->Left && !BT->Right)
prnitf("%d",BT->Data);
PreOrderPrintLeaves(BT->Left);
PreOrderPrintLeaves(BT->Right);
}
}

例:求二叉树的高度#

image-20190607210218198

1
2
3
4
5
6
7
8
9
10
11
int PostOrderGetHeight(BinTree BT){
int HL, HR, MaxH;
if(BT){
HL = PostOrderGetHeight(BT->Left); /*求左子树的深度*/
HR = PostOrderGetHeight(BT->Right); /*求右子树的深度*/
MaxH = (HL > HR)? HL : HR; /*取左右子树的较大深度*/
return(MaxH + 1); /*返回树的深度*/
}
else
return 0;
}

例:二元运算表达树及其遍历#

image-20190607211340885

解决中序遍历中受运算符优先级影响问题,通过在左子树开始的时候加一个左括号”(“,当左子树结束的时候再添加一个右括号”)”

例:由两种遍历序列确定二叉树#

已知三种遍历中的任意两种两种遍历序列,能否唯一确定一棵二叉树?

答案是:两种遍历中必须要包含有中序遍历才可以

image-20190607212019199

先序和中序遍历序列来确定一棵二叉树

[分析]

  • 根据先序遍历序列第一个结点来确定根结点
  • 根据根结点在中序遍历序列中分割出左右两个子序列
  • 对左子树和右子树分别递归使用相同的方法继续分解

image-20190607212417700

[例]

image-20190607212703867

类似的,后序和中序遍历序列也可以确定一棵二叉树

小白专场:树的同构#

image-20190607212946350

二叉树的表示#

结构数组表示二叉树:静态链表

1
2
3
4
5
6
7
8
9
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1 /*区分于 C 语言中的NULL(0),其代表为空指针*/
struct TreeNode{
ElementType Element;
Tree Left;
Tree Right;
}T1[MaxTree], T2[MaxTree];

image-20190607214842508

顺序可以不同

image-20190607215710594

对于 B,其左儿子存在且为 C ,其下标为 4。其右儿子为 D,其下标为 3

查找根结点是谁?

分析:这四个结点放在0、1、3、4中,且在0、1、3、4 中,0、3、4都出现了,所以 1 为根结点

程序框架搭建#

image-20190618200348496

如何建二叉树#

递归法#

用单个字符表示二叉树中一个结点的数据,这里采用前序遍历算法,建立二叉树的过程:

  • 输入一个根结点
  • 若输入的是” “(空字符),则表明二叉树为空,置 T 为 NULL
  • 若输入的不是” “(空字符),则将该字符赋给 T->data,然后,依次递归地建立它的左子树T->lchild,和右子树 T->rchild。

具体算法:

1
2
3
4
5
6
7
8
9
10
11
12
void BUILDBT(BTREE &T){
char ch;
scanf("%c", &ch); /*输入一个元素*/
if(ch == " ")
T = NULL; /*建立空二叉树*/
else{
T = (BTREE)malloc(sizeof(BTNode)); /*生成一个新的链结点*/
T->data = ch;
BUILDBT(T->lchild); /*递归建立左子树*/
BUILDBT(T->rchild); /*递归建立右子树*/
}
}

「幕课算法」

1
2
3
4
5
6
7
8
9
10
11
12
13
Tree BuildTree(struct TreeNode T[]){
scanf("%d\n", &N);
if(N){
...
for(i = 0; i < N; i++){
scanf("%c%c\n",&T[i].Element, &cl, &cr);
...
}
...
Root = ???
}
return Root;
}

image-20190618200916316

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Tree BuildTree(struct TreeNode T[]){
...
scanf("%d\n", &N);
if(N){
for(i = 0; i < N; i++) check[i] = 0; /*一开始将所有的check数组全部设为0, 有数据输入指向它,就将其数组位置变为1,方便之后检查是否存在,来判断是否为根结点*/
for(i = 0; i < N; i++) {
scanf("%c%c%c\n", &T[i].Element, &cl, &cr);
if(cl ! = '-'){
T[i].Left = cl-'0';
check[T[i].Left] = 1;
}
else T[i].Left = Null;
/*对 cr 的对应处理*/
if(cr ! = '-'){
T[i].Right = cl-'0';
check[T[i].Right] = 1;
}
else T[i].Right = Null;
}
for(i = 0; i < N; i++)
if(!check[i]) break;
Root = i;
}
return Root;
}

如何判别两二叉树同构#

image-20190618202133372

树(中)#

什么是二叉搜索树#

查找问题

  • 静态查找和动态查找
  • 针对动态查找,数据如何组织?

二叉搜索树(BST,Binary Search Tree),也称二叉排序树或二叉查找树

二叉搜索树:一棵二叉树,可以为空,如果不为空,满足以下性质:

  • 非空左子树的所有键值小于其根结点的键值
  • 非空右子树的所有键值大于其根结点的键值
  • 左、右子树都是二叉搜索树

image-20190618210913720

二叉搜索树操作的特别函数#

  • Position Find(ElementType X, BinTree BST):从二叉搜索树BST中查找元素X,返回其所在结点的地址
  • Position FindMin(BinTree BST):从二叉搜索树BST中查找并返回最小元素坐在结点的地址
  • Position FindMax(BinTree BST):从二叉搜索树BST中查找并返回最大元素所在结点的地址
  • BinTree Insert(ElementType X, BinTree BST):二叉搜索树的插入操作
  • BinTree Delete(ElementType X, BinTree BST):二叉搜索树的删除操作
二叉搜索树的查找操作:Find#

思路:

  • 查找从根结点开始,如果树为空,返回 NULL
  • 若搜索树非空,则根结点关键字和X进行比较,并进行不同的处理:
    • 若 X 小于根结点的键值,则需在左子树中继续搜索
    • 若 X 大于根结点的键值,则需在右子树中继续搜索
    • 若两者比较结果是相等,搜索完成,返回指向此结点的指针

image-20190618211627779

1
2
3
4
5
6
7
8
9
Position Find(ElementType X, BinTree BST){
if(!BST) return NULL;
if(X > BST->Data)
return Find(X, BST->Right); /*在右子树中继续查找*/
else if (X < BST->Data)
return Find(X, BST->Left); /*在左子树中继续查找*/
else /* X == BST->Data */
return BST; /*查找成功,返回找到的结点的地址*/
}

注:上述递归均为尾递归,效率低

用非递归函数的执行效率高,可将”尾递归”函数改为迭代函数,用循环来做

1
2
3
4
5
6
7
8
9
10
11
Position IterFind(ElementType X, BinTree BST){
while(BST){
if(X > BST->Data)
BST = BST->Right;
else if (X < BST->Data)
BST BST->Left;
else /* X == BST->Data*/
return BST; /*查找成功,返回结点的找到结点的地址*/
}
return NULL; /*查找失败*/
}
二叉搜索树的查找最大值和最小值递归函数#

思路:

  • 最大值一定是最右边到底
  • 最小值一定是最左边到底

最小值查找

1
2
3
4
5
6
7
Position FindMin(BinTree BST){
if(!BST) return NULL;
else if (!BST->Left)
return BST;
else
return FindMin(BST->Left);
}

最大值查找

1
2
3
4
5
6
7
Position FindMax(BinTree BST){
if(!BST) return NULL;
else if (!BST->Right)
return BST;
else
return FindMin(BST->Right);
}

二叉搜索树的插入#

「分析」关键是要找到元素应该插入的位置,可以采用与 Find 类似的方法

image-20190619202105335

「算法」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 X 已经存在,什么都不做*/
return BST;

}

「例题」

image-20190619204107020

注:按照字母先后进行排序

二叉搜索树的删除#

考虑三种情况:#

1. 要删除的是叶结点:直接删除,并再修改其父结点指针—置为 NULL

image-20190619204434753

2. 要删除的结点只有一个孩子结点:

​ 将其父结点的指针指向要删除结点的孩子结点

image-20190619204555885

3. 要删除结点有左、右两棵子树:

​ 用另一结点代替被删除结点:取右子树的最小元素代替之,或者取左子树的最大元素代替之。

​ 以上原则还是符合二叉搜索树的构成要求:左子树键值小于根结点键值,右子树键值大于根结点键值

「算法」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
BinTree Delete(ElementType X, BinTree BST){
Position Tmp;
if(!BST) printf("The elem doesn't exist\n");
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{ /*被删除结点有一个或者无子结点*/
Tmp = BST;
if(!BST->Left) /*有右孩子或者无子结点*/
BST = BST->Right;
else if(!BST->Right) /*有左孩子或者无子结点*/
BST = BST->Left;
free(Tmp);
}
return BST;
}

平衡二叉树#

image-20190620195505518

“平衡因子(Balance Factor,简称BF)”:BF(T)= $h_L- h_R$ ,其中$h_L- h_R$ 分别为 T 左、右子树的高度。

平衡二叉树(Balanced Binary Tree)(AVL树):

  • 空树
  • 或者,任一结点左、右子树高度差的绝对值不超过1,即|BF(T)|≤ 1

image-20190620200211141

平衡二叉树的高度能达到$log_2 n$?

image-20190620200313080

image-20190620201248169

image-20190620201316377

image-20190620201737694

平衡二叉树的调整#

image-20190819182910359

四种调整结构#

  • RR 旋转
  • LL 旋转
  • LR 旋转
  • RL 旋转

理解:对于 RR、LL 旋转,直接拎起左孩子,或者右孩子; 对于 LR 、RR 旋转,需要找到被破坏者,比较从被破坏者作为根节点的距离破坏者节点最近的最小不平衡树(三个节点),将其中平衡因子为中间的节点重新作为根节点。

注意:⚠️因为是平衡搜索树,一定需要满足左边小,右边大。

RR 旋转(右右旋转)具体例子:#

image-20190819183122716

image-20190819183218121

判断按不同的插入序列是否可以得到相同的二叉搜索树#

image-20190819214259251

求解思路:#

两个序列是否对应相同搜索树的判别:

  1. 分别建两棵搜索树的判别方法,进行递归判别每棵搜索树的每个节点的值是否一样
  2. 不建树的判别方法
    image-20190819214658539

  3. 建一棵树,在判别其他序列是否与该树一致

    • 搜索树表示
    • 建搜索树T
    • 判别一序列是否与搜索树T一致
搜索树的表示:#
1
2
3
4
5
6
typedef struct TreeNode *Tree;
struct TreeNode{
int v;
Tree Left, Right;
int flag; /*用于判别一个序列是否与树是一致的,后面如果某个节点没有被访问过,flag设为0,反之则1。flag 作为又没有被访问过的一个标记。用于帮助判别一个序列是否跟 T 是一样的。*/
};
程序框架的搭建#
1
2
3
4
5
6
7
8
int main(){
对每组数据
* 读入 N 和 L;
* 根据第一行序列建树T;
* 依据树T分别判别后面的L个序列是否能与T形成同一个搜索树并输出结果

return 0
}

需要设计的主要函数:

  • 读数据建搜索树T
  • 判别一序列是否与 T 构成一样的搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main(){
int N,L,i; /*N 个节点的树,L 个序列*/
Tree T;

scanf("%d", &N);
while(N){
scanf("%d", &L);
T = MakeTree(N);
for(i = 0; i < L; i++){
if(judge(T,N)) printf("Yes\n");
else printf("No\n");
ResetT(T); /*清楚 T 中的标记flag*/
}
FreeTree(T);
scanf("%d", &N);
}

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
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;
}
1
2
3
4
5
6
7
Tree NewNode(int V){
Tree T = (Tree)malloc(sizeof(struct TreeNode));
T->v = V;
T->Left = T->Right = NULL;
T->flag = 0;
return T;
}
1
2
3
4
5
6
7
8
9
10
11
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;
}

如何判别#

image-20190819222223206

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
int Judge(Tree T, int N){	/*有 bug 版本*/
int i,V;
if(V!=T->v) return 0;
else T->flag = 1;

for(i = 1; i < N; i++){
scanf("%d",&V);
if(!check(T,V)) return 0;
}
return 1;
}

image-20190819223227499

image-20190819223244996

1
2
3
4
5
6
void ResetT(Tree T)		/*清除 T 中各结点的 flag 标记*/
{
if(T->Left) ResetT(T->Left);
if(T->Right) ResetT(T->Right);
T->flag = 0;
}
1
2
3
4
5
void FreeTree(Tree T){
if(T->Left) FreeTree(T->Left);
if(T->Right) FreeTree(T->Right);
free(T); /*释放根结点*/
}

#

优先队列(Priority Queue)

特殊的“队列”,取出元素的顺序是依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序。

采用数组或链表实现优先队列#

image-20190828205023578

采用二叉树存储结构

image-20190828205241828

注意:从根结点到任意结点路径上结点序列的有序性,即由大到小

image-20190828205556627

最大堆的操作#

最大堆的创建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
ElementType *Elements; /*存储堆元素的数组*/
int Size; /*堆的当前元素个数*/
int Capacity; /*堆的最大容量*/
};

MaxHeap Create( int MaxSize ){
/*创建容量为 MaxSize 的空的最大堆*/
MaxHeap H = malloc(sizeof(struct HeapStruct)); /*先申请一块空间*/
H->Elements = malloc((MaxSize+1) * sizeof(ElementType)); /*+1是因为从下标为1开始存放元素*/
H->Size = 0;
H->Capacity = MaxSize;
H->Elements[0] = MaxData;
/*定义“哨兵”为大于堆中所有可能元素的的值,便于以后更快的操作*/
}

最大堆的插入#

image-20190828210814805

算法实现: 将新增结点插入到从其父结点到根结点的有序序列中

image-20190828211626603

哨兵的设置,使得,当比较到哨兵时,不需要进行交换。存储到下标为 1 为止。

最大堆的删除#

取出根结点(最大值)元素,同时删除堆的一个结点

image-20190829193922024

删除算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ElementType DeleteMax(MasHeap H){
int Parent, Child;
ElementTpye MaxItem, temp;
if( IsEmpty(H) ){
printf("最大堆已空");
return ;
}
MaxItem = H->Elemente[1]; /*取出根结点的最大值,最大值保存在下表为 1 的 ElementType 结构体数组中*/
temp = H->Elements[H->Size--]; /*temp 保存最后一个结点的值*/
/*Parents 指示要将 temp 放入的位置
*
*/
for(Parent = 1; Parent*2 <= H->Size; Parent == Child){
/*比较的目的,用来找以后所有左右孩子中的最大值*/
Child = Parent * 2; /*先假定左儿子最大*/
if((Child != H->Size) &&
(H->Elements[Child] < H->Elements[Child+1]))
Child++; /*Child 指向左右子结点的较大者*/
if(temp >= H->Elements[Child]) break; /*如果比左右孩子最大的还要大*/
else
H->Elements[Parent] = H->Elements[Child];
}
H->Elements[Parents] = temp;
return MaxItem;
}

最大堆的建立#

建立最大堆:将已经存在的N个元素按最大堆的要求存放在一个数组中

  • 方法一:通过插入操作,将 N 个元素一个个相继插入到一个初始为空的堆中去,其时间代价最大为 $O(NlogN)$

  • 方法二:在线性时间复杂度下建立最大堆

    • (1)将 N 个元素按输入顺序存入,先满足完全二叉树的结构特性

    • (2)调整各结点位置,以满足最大堆的有序特性。

      image-20190829204422148

哈夫曼树与哈夫曼编码#

哈夫曼树的定义

带权路径长度(WPL):设二叉树有 n 个叶子结点,每个叶子结点带有权值 $Wk$,从根结点到每个叶子结点的长度为 $l_k$ ,则每个叶子结点的带权路径长度之和就是:$$WPL=\sum{k=1}^{n}{W{k}L{k}}$$

最优二叉树或者哈夫曼树:WPL最小的二叉树

【例子】有五个叶子结点,它们的权值为{1,2,3,4,5},用此权值序列可以构造出形状不同的多个二叉树。

image-20190830155303537

哈夫曼树的构造#

  • 每次把权值最小的两颗二叉树

    image-20190830155533781

  • 如何选取两个最小的?(利用堆)(直接排序效率不如堆)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
};
HuffmanTree Huffman(MinHeap H){
/*假设 H->Size 个权值已经存在 H->Elements[]->Weight 里*/
int i; HuffmanTree T;
BuildMinHeap(H); /*将 H->Elements[] 按权值调整为最小堆*/
for(i = 1; i < H->Size; i++){/*做 H->Size-1 次合并*/
T = malloc(sizeof(struct TreeNode)); /*create a new node*/
T->Left = DeleteMin(H); /*delete a smallest node as the left node of the new node*/
T->Right = DeleteMin(H); /*delete a smallest node as the right node of the new node*/
T->Weight = T->Left->Weight+T->Right->Weight; /*calculate the new weight*/
Insert(H, T); /*insert T to smallest heap*/

}
T = DeleteMin(H);
return T;
}

整体的时间复杂度为$O(N logN)$

哈夫曼树的特点:#

  • 没有度为 1 的结点;

  • n 个叶子结点的哈夫曼树共有 2n-1 个结点

  • 哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树

  • 对于同一组权值{w1, w2, ……, wn},是否存在不同构的两颗哈夫曼树呢?

    image-20190830163219126

哈夫曼编码#

给定一段字符串,如何对自负进行编码,可以使得该字符串的编码存储空间最少?

image-20190830163752425

image-20190830163929408

image-20190830164020364

image-20190830164156757

当所有的字符都在叶结点上的时候,就不会出现前缀码是另外一个字符的前缀。

当编码中的一个结点出现在另一个结点的前面的时候—即在树的非叶结点上的时候,就会出现前缀。

image-20190830164700580

利用哈夫曼树进行编码#

image-20190830164903060

集合的表示#

image-20190830165137808

image-20190830165411043

image-20190830165551267

集合运算#

  • 查找某个元素所在的集合(用根结点表示)
1
2
3
4
5
6
7
8
9
int Find(SetType S[], ElementType X){
/*find value of X's array in the array S */
/*MaxSize is global vriable the leight of array S*/
int i;
for(i = 0; i < MaxSize && S[i].Data != X; i++);
if(i >= MaxSize ) return -1; /* return -1 when doesn't find X*/
for(; S[i].Parent >= 0; i = S[i].Parent );
return i; /*return the subscript of X in array S */
}
  • 集合的并运算

    • 分别找到 X1 和 X2 两个元素所在集合树的根结点
    • 如果它们不同根,则将其中一个根结点的福结点指针设置成另一个根结点的数组下标

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      void Union(SetType S[], ElementType X1, ElementType X2)
      {
      int Root1, Root2;
      Root1 = Find(S, X1);
      Root2 = Find(S, X2);

      if(Root1 != Root2)
      S[Root2].Parent = Root1;

      }

      image-20190830212543741

image-20190830214747498

堆中的路径#

image-20190830215721690

堆的表示及其操作#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define MAXN 1001
#define MINH -10001
int H[MAXN], size;

void Create(){
size = 0;
H[0] = MINH; /*设置岗哨*/
}

void Insert(int X)
{
/*将 X 插入 H,省略检查堆是否已经满的代码*/
int i;
for(i=++size; H[i/2] > X; i/=2)
H[i] = H[i/2];
H[i] = X;
}

int main(){
int n, m, x, i, j;
scanf("%d%d", &n, &m);
Create(); /*堆初始化*/
for(i = 0; i < n; i++){ /*以逐个插入方式建堆*/
scanf("%d", &x);
Insert(X);
}

for(i = 0; i < m; i++){
scanf("%d", &j);
printf("%d", H[j]);
while(j>1){
j/=2;
printf("%d", H[j]);
}
printf("\n");
}

return 0;
}
CATALOG
  1. 1. 树与二叉树#
  2. 2. 树(上)#
    1. 2.1. 引子#
      1. 2.1.1. 查找:根据某个给定关键字 K,从集合 R 中找出关键字与 K 相同的记录#
    2. 2.2. 树形结构#
    3. 2.3. 树的定义#
      1. 2.3.1. 树:n(n≥0)个结点构成的有限集合#
      2. 2.3.2. 树的基本术语#
      3. 2.3.3. 树的性质#
      4. 2.3.4. 树的表示#
      5. 2.3.5. 二叉树的定义#
      6. 2.3.6. 二叉树的几个重要性质#
      7. 2.3.7. 二叉树的抽象数据类型定义#
      8. 2.3.8. 二叉树的存储结构#
        1. 2.3.8.1. 顺序存储结构#
        2. 2.3.8.2. 链表存储#
      9. 2.3.9. 二叉树的遍历#
        1. 2.3.9.1. 先序遍历 -> 根左右#
        2. 2.3.9.2. 中序遍历 -> 左根右#
        3. 2.3.9.3. 后序遍历 -> 左右根#
      10. 2.3.10. 二叉树的非递归遍历#
        1. 2.3.10.1. 中序遍历非递归遍历算法#
        2. 2.3.10.2. 先序遍历的非递归算法#
        3. 2.3.10.3. 后序遍历非递归算法#
    4. 2.4. 层序遍历#
      1. 2.4.1. 队列实现:#
      2. 2.4.2. 例:遍历二叉树的应用:输出二叉树中的叶子结点#
      3. 2.4.3. 例:求二叉树的高度#
      4. 2.4.4. 例:二元运算表达树及其遍历#
      5. 2.4.5. 例:由两种遍历序列确定二叉树#
    5. 2.5. 小白专场:树的同构#
      1. 2.5.1. 二叉树的表示#
      2. 2.5.2. 程序框架搭建#
      3. 2.5.3. 如何建二叉树#
        1. 2.5.3.1. 递归法#
      4. 2.5.4. 如何判别两二叉树同构#
  3. 3. 树(中)#
    1. 3.1. 什么是二叉搜索树#
      1. 3.1.1. 二叉搜索树操作的特别函数#
        1. 3.1.1.1. 二叉搜索树的查找操作:Find#
        2. 3.1.1.2. 二叉搜索树的查找最大值和最小值递归函数#
      2. 3.1.2. 二叉搜索树的插入#
      3. 3.1.3. 二叉搜索树的删除#
        1. 3.1.3.1. 考虑三种情况:#
    2. 3.2. 平衡二叉树#
      1. 3.2.1. 平衡二叉树的调整#
      2. 3.2.2. 四种调整结构#
      3. 3.2.3. RR 旋转(右右旋转)具体例子:#
      4. 3.2.4. 判断按不同的插入序列是否可以得到相同的二叉搜索树#
      5. 3.2.5. 求解思路:#
        1. 3.2.5.1. 搜索树的表示:#
        2. 3.2.5.2. 程序框架的搭建#
      6. 3.2.6. 如何判别#
    3. 3.3. 堆#
      1. 3.3.1. 采用数组或链表实现优先队列#
      2. 3.3.2. 最大堆的操作#
      3. 3.3.3. 最大堆的插入#
      4. 3.3.4. 最大堆的删除#
      5. 3.3.5. 最大堆的建立#
    4. 3.4. 哈夫曼树与哈夫曼编码#
      1. 3.4.1. 哈夫曼树的构造#
      2. 3.4.2. 哈夫曼树的特点:#
      3. 3.4.3. 哈夫曼编码#
      4. 3.4.4. 利用哈夫曼树进行编码#
    5. 3.5. 集合的表示#
      1. 3.5.1. 集合运算#
    6. 3.6. 堆中的路径#
      1. 3.6.1. 堆的表示及其操作#