树和二叉树

learning-note

字数统计: 7.3k阅读时长: 30 min

 2019/05/27   Share

树与二叉树

树（上）

引子

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

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

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

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 个数据元素的关键字满足有序(比如：小到大)

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

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)

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

树与非树

子树是不相交的
除了根结点外，每个节点有且仅有一个父节点
一棵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)$]

树的表示

儿子-兄弟表示法

二叉树的定义

特殊的二叉树

斜二叉树（相当于列表）
完美二叉树（满二叉树）
完全二叉树

二叉树的几个重要性质

一个二叉树第 i 层的最大结点数为： $2^{i-1}$ ，i≥1.
深度为 K 的二叉树有最大结点总数为： $2^{k}-1$ ，k≥1.（完美二叉树即为这样）
对任何非空二叉树（至少有一个结点的二叉树叫做非空二叉树）T，若 $n_0$ 表示叶子结点的个数、 $n_2$ 是度为 2 的非叶子结点个数，那么二者之间满足关系： $n_0 = n_2 +1$

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

二叉树的存储结构

顺序存储结构

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

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

性质：

非根结点（序号 i > 1）的父结点的序号是[i/2]；
结点（序号 i ）的左孩子的结点的序号是2i；（要2i ≤ n，否则没有左孩子）
结点（序号 i）的右孩子结点的序号是 2i+1；（要 2i+1≤n，否则没有右孩子）

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

链表存储

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

二叉树的遍历

先序遍历 -> 根左右

遍历过程：

访问根结点
先序遍历其左子树
先序遍历其右子树

void PreOrderTraversal (BinTree BT){
    if(BT){
        printf("%d", BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(Bt->Right);
    }
}

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

中序遍历 -> 左根右

遍历过程：

中序遍历其左子树
访问根结点
中序遍历其右子树

void InOrderTraversal (BinTree BT){
    if(BT){
        InOrderTreaversal(BT->Left);
        printf("%d", BT->Data);
        InOrderTraversal(Bt->Right);
    }
}

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

后序遍历 -> 左右根

遍历过程：

后序遍历其左子树
后序遍历其右子树
访问根结点

void PostOrderTraversal(BinTree Bt){
    if(BT){
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d", BT->Data);
    }
}

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

总结

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

二叉树的非递归遍历

中序遍历非递归遍历算法

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

算法：

遇到一个结点，就把它压栈，并去遍历它的左子树；
当左子树遍历结束后，从栈顶弹出这个结点并访问它；
然后按其右指针再去中序遍历该结点的右子树

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;		/*转向右子树*/
        }
    }
}

#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*/
    }
}

先序遍历的非递归算法

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;
        }
    }
}

#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，表示其从右子树返回，可访问其根结点

#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));
    }
}

层序遍历

队列实现：

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

层序基本过程：先根结点入队，然后：

从队列中取出一个元素；
访问该元素所指结点；
若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队

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);       
    }
}

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

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

void PreOrderPrintLeaves(BinTree BT){
    if(BT){
        if(!BT->Left && !BT->Right)
            prnitf("%d",BT->Data);
        PreOrderPrintLeaves(BT->Left);
        PreOrderPrintLeaves(BT->Right);
    }
}

例：求二叉树的高度

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;
}

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

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

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

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

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

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

[分析]

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

[例]

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

小白专场：树的同构

二叉树的表示

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

#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];

顺序可以不同

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

查找根结点是谁？

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

程序框架搭建

如何建二叉树

递归法

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

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

具体算法：

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);		/*递归建立右子树*/
    }
}

「幕课算法」

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;
}

完整代码

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;
}

如何判别两二叉树同构

树（中）

什么是二叉搜索树

查找问题

静态查找和动态查找
针对动态查找，数据如何组织？

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

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

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

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

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 大于根结点的键值，则需在右子树中继续搜索
- 若两者比较结果是相等，搜索完成，返回指向此结点的指针

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;					/*查找成功，返回找到的结点的地址*/
}

注：上述递归均为尾递归，效率低

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

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;	/*查找失败*/
}

二叉搜索树的查找最大值和最小值递归函数

思路：

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

最小值查找

Position FindMin(BinTree BST){
    if(!BST) return NULL;
    else if (!BST->Left)
        return BST;
    else
        return FindMin(BST->Left);
}

最大值查找

Position FindMax(BinTree BST){
    if(!BST) return NULL;
    else if (!BST->Right)
        return BST;
    else
        return FindMin(BST->Right);
}

二叉搜索树的插入

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

「算法」

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;
        
}

「例题」

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

二叉搜索树的删除

考虑三种情况：

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

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

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

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

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

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

「算法」

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;
}

平衡二叉树

“平衡因子（Balance Factor，简称BF）”：BF（T）= $h_L- h_R$ ，其中$h_L- h_R$ 分别为 T 左、右子树的高度。

平衡二叉树（Balanced Binary Tree）（AVL树）：

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

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

平衡二叉树的调整

四种调整结构

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

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

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

RR 旋转（右右旋转）具体例子：

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

求解思路：

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

分别建两棵搜索树的判别方法，进行递归判别每棵搜索树的每个节点的值是否一样
不建树的判别方法
建一棵树，在判别其他序列是否与该树一致
- 搜索树表示
- 建搜索树T
- 判别一序列是否与搜索树T一致

搜索树的表示：

typedef struct TreeNode *Tree;
struct TreeNode{
    int v;
    Tree Left, Right;
    int flag;	/*用于判别一个序列是否与树是一致的，后面如果某个节点没有被访问过，flag设为0，反之则1。flag 作为又没有被访问过的一个标记。用于帮助判别一个序列是否跟 T 是一样的。*/
};

程序框架的搭建

int main(){
    对每组数据
    * 读入 N 和 L；
    * 根据第一行序列建树T；
    * 依据树T分别判别后面的L个序列是否能与T形成同一个搜索树并输出结果
        
    return 0；
}

需要设计的主要函数：

读数据建搜索树T
判别一序列是否与 T 构成一样的搜索树

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;
}

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;
}

如何判别

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;
    }
}

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;
}

void ResetT(Tree T)		/*清除 T 中各结点的 flag 标记*/
{
    if(T->Left) ResetT(T->Left);
    if(T->Right) ResetT(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T){
    if(T->Left) FreeTree(T->Left);
    if(T->Right) FreeTree(T->Right);
    free(T);	/*释放根结点*/
}

堆

优先队列（Priority Queue）

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

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

采用二叉树存储结构

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

最大堆的操作

最大堆的创建：

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;
    /*定义“哨兵”为大于堆中所有可能元素的的值，便于以后更快的操作*/
}

最大堆的插入

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

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

最大堆的删除

取出根结点（最大值）元素，同时删除堆的一个结点

删除算法

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）调整各结点位置，以满足最大堆的有序特性。

哈夫曼树与哈夫曼编码

哈夫曼树的定义

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

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

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

哈夫曼树的构造

每次把权值最小的两颗二叉树
如何选取两个最小的？（利用堆）（直接排序效率不如堆）

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}，是否存在不同构的两颗哈夫曼树呢？

哈夫曼编码

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

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

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

利用哈夫曼树进行编码

集合的表示

集合运算

查找某个元素所在的集合（用根结点表示）

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 两个元素所在集合树的根结点

如果它们不同根，则将其中一个根结点的福结点指针设置成另一个根结点的数组下标

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;
   
}

堆中的路径

堆的表示及其操作

#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;
}

Next Post

物联网新型智慧城市的发展
Previous Post

PAT 1016 部分A+B

CATALOG

1. 树与二叉树
2. 树（上）
3. 树（中）

