数据结构(树与二叉树基本概念)
前面的文章主要关于iOS开发的，这篇文章我们来讨论一下数据结构中十分重要的二叉树及其基本概念。
参考资料: 严蔚敏，吴伟民.数据结构(C语言版) [M]. 北京: 清华大学出版社, 2009
树的基本概念
树是 N(N>=0) 个结点的有限集合, N=0 时，称为空树，对任意的非空树应该满足: 有且仅有一个特定的称为根的结点；当 N > 1 时，其余结点可分为 m(m>0) 个互不相交的有限集合 T1,T2,T3,...,Tm, 其中每一个集合本身又是一棵树，并且称为根节点的子树。
树是一种递归的数据结构(以为其定义的递归的)；树作为一种逻辑结构，同时也是分层结构具有如下两个特点：
1. 树的根节点没有前驱结点，除了根节点之外的所有节点有且只有一个前驱结点
2. 树中的所有结点可以有零个或多个后继结点
树适合表示具有层次结构的数据。树中的某个结点最多只和上一层的一个结点有直接关系，根结点没有直接上层结点，树中每个结点与其下一层的零个或者多个结点有直接关系，因此，在 n 个结点的树中有 n-1 条边。
树的基本术语:
- 祖先结点、子孙结点；双亲结点、孩子节点；兄弟结点的概念；
- 树中一个结点的孩子结点的个数称为该结点的 度 ,树中结点的最大数称为 树的度 ,
- 度大于零的结点称为分支结点(非终端结点)，度为零的结点称为叶子结点(终端结点)
- 结点的层次(根结点为第一层，它的子结点为第二层，以此类推)
- 结点的深度(自顶向下逐层累加)
- 结点的高度(自底向上逐层累加)
- 树的高度(深度)是树中结点的最大层数
- 有序树和无序树: 树的结点的子树从左至右是有次序的，不能交换，称为有序树，反之则称之为无序树
- 路径和路径长度: 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
- 森林: 森林是 m(m>=0) 棵互不相交的树的集合。只要把树的根结点删去就成了森林，反之给 n 棵独立的树加上一个结点，并把 n 棵树作为该结点的子树，则森林就变成了树。
树的基本性质如下:
- 树中的结点数等于所有结点的度数加1
- 度为 m 的树中第 i 层上至多有 m ^ (i-1) 个结点 (i>=1),若想等则树的每一层都全部填充完毕
- 高度为 h 的 m 叉树至多有 (m^h -1)(m-1) 个结点
- 具有 n 个结点的 m 叉树的最小高度为 logm (n(m-1)+1) (向上取整)
二叉树的基本概念
二叉树的特点是每个结点至多只有两颗子树，并且，二叉树的子树有左右之分，其次序不能颠倒。二叉树也可以以递归的形式定义。
二叉树与度为2的有序树的区别: 1. 度为2的有序树至少有三个结点，而二叉树可以为空； 2. 度为2的有序树的孩子结点的左右次序是相对于另一个孩子结点而言，如果某个结点只有一个孩子结点这个孩子结点就无需区分其左右次序，而二叉树无论其孩子树是否为2，均需确定其左右次序，二叉树的结点次序不是相对于另一个孩子结点而言，而是确定的。
几种特殊的二叉树:
- 满二叉树: 高度为 h 的二叉树的结点为 2 ^ h -1 ;叶子结点都集中在最下一层，左孩子为 2i ,右孩子为 2i + 1;双亲结点为 i/2(去下整) ；
- 完全二叉树:
- 若 i <= n/2（取下整），则 i 为分支结点，否则为孩子结点。
- 若 n 为奇数，则每个分支结点都有左右孩子，反之只有左子女，
- 如果有度为1的结点，只可能有一个，且该结点只有左孩子没有右孩子
- 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）:
- 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
- 平衡二叉树:
- 树上任意结点的左子树和右子树的深度之差不超过1。
二叉树的性质:
- 非空二叉树上叶子结点数等于度为2的结点数加1，N0 = N2 + 1
总结点树为 N = N0 + N1 + N2 ,每个结点都从一个分支而来(根结点除外)，分支是由度为1，2的结点射出的， N = N1 + 2N2 + 1 ; 又因为 N = N1 + N2 + N3 ; 所以 N0 = N2 + 1 。
- 具有 N 个结点的完全二叉树的高度为 log2(N+1) 取上整
二叉树的存储结构
顺序存储结构:
- 用一组连续的存储单元依次自上而下，至左至右存储完全二叉树上的结点元素将完全二叉树上编号为 i 的结点元素存储在某个数组下标为 i-1 的分量中，顺序存储结构比较适合完全二叉树与满二叉树。
注意区别树的顺序存储结构与二叉树的顺序存储结构。 树的顺序存储结构中，数组下标代表结点编号，下标上所存的内容指示了结点之间的关系。而在二叉树顺序存储结构中，数组下标即代表了结点编号，也指示了树中各结点之间的关系。二叉树属于树，二叉树都可以用树的存储结构来存储。
链式存储结构:
- 因为顺序存储结构对空间利用率较低，因此一般二叉树都采用链式存储结构。用一个链表存储一个二叉树，二叉树中的每个结点用链表的一个链结点来存储。在二叉树中，结点结构通常包括若干数据域以及若干指针域。二叉链表至少包含 数据域，指针域(lchild和rchild)。
- 在含有n个结点的二叉链表中含有 n+1 个空链域
typedf struct BinaryTreeNode{
int data;
struct BinaryTreeNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉树的遍历
所谓二叉树遍历，是指按照某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
先序遍历(PreOrder): 访问根节点，先序遍历左子树，先序遍历右子树。
void PreOrder(BiTree T){ if(T != NULL){ // 访问根节点，之后递归访问左子树，右子树 visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } }中序遍历(InOrder): 中序遍历左子树，访问根结点，中序遍历右子树。
void InOrder(BiTree T){ if(T != NULL){ InOrder(T ->lchild); visit(T); InOrder(T ->rchild); } }后序遍历(PostOrder): 后续遍历左子树，后序遍历右子树，访问根结点。
void PostOrder(BiTree T){ if(T != 0){ PostOrder(T ->lchild); PostOrder(T ->rchild); visit(T); } }层次遍历(宽度优先遍历): 按照1，2，3，4... 的层次顺序，对二叉树中的各个结点进行访问(使用队列)
void LevelOrder(BiTree T){ InitQueue(Q); //初始化辅助队列 BiTree p; EnQueue(W,T); while(!IsEmpty(Q)){ DeQueue(T); visit(p); if(p->lchild != NULL){ EnQueue(Q,p->lchild); } if(p->rchild != NULL){ EnQueue(Q,p->rchild); } } }由遍历序列构造二叉树:
知道先序序列和中序序列可以唯一确定二叉树 知道后续遍历和中序遍历可以唯一确定二叉树 知道层次序列和中序序列也可以唯一确定二叉树
Note: 知道线序遍历和后续遍历不能唯一确定一个二叉树。
线索二叉树
二叉树的遍历是以一定的规则将二叉树中的结点排成一个线性序列，其实质就是对一个非线性结构进行线性化操作，使得每一个结点都有一个前驱和后继(第一个和最后一个除外)。
传统的链式存储结构仅能提供一种父子关系，不能直接得到结点的前驱和后继，我们利用二叉链表中的大量空链域存放指向其直接前驱和后继的指针。
引入线索二叉树是为了加快查找结点前驱和后继的速度。
N个结点的二叉树有 N+1 个空指针，因为总的空指针为 2N0 + N1 ,又因为 N0 = N2 + 1 。 所以 N0+N1+N2 = N+1
在二叉树线索化时若无左子树，另 lchild 指向其前驱结点；若无右子树时，另 rchild指向其后继结点，还需要增加两个标志域(ltag,rtag)来表明当前指针域所指向的对象是左(右)结点还是前驱(后继)；0表示左(右)孩子，1表示前驱(后继)。
二叉线索树的数据结构如下所示:
typedf struct ThreadNode{
int data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //左右线索标志
};
- 二叉线索树的构造： *
二叉树的线索化实际上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点的左右指针域是否为空，若为空，将他们改为指向前驱结点或后继结点的线索。
// 通过中序遍历对二叉树线索化的递归算法
void InThread(ThreadTree &p, ThreadTree &pre){
// 中序遍历对二叉树线索化的递归算法
if(p != NULL){
InThread(p->lchild,pre);
if(p->lchild == NULL){
p ->lchild = pre;
p ->ltag = 1;
}
if(pre != NULL && pre ->rchild == NULL){
pre ->rchild = p;
pre ->rtag = 1;
}
pre = p;
InThread(p->rchild,pre);
}
}
// 通过中序遍历建立中序线索二叉树的主过程那个算法
void CreateInThread(ThreadTree T){
ThreadTree pre = NULL;
if(T != NULL){
InThread(T,pre);
pre ->rchild = NULL;
pre ->rtag = 1;
}
}
- 线索二叉树的遍历: * (利用线索二叉树实现二叉树遍历的非递归算法，不借助栈)
中序线索二叉树中 中序序列下的第一个结点:
ThreadNode *Firstnode(ThreadNode *p){ while(p ->ltag == 0) p = p ->lchild; return p; }中序线索二叉树中结点 p 在中序序列下的后继结点:
ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag = 0) return Firstnode(p->rchild); else return p->rchild; }利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历算法
void Inorder(ThreadNode *T){ for(ThreadNode *p = Firstnode(T);p != NULL,p=Nextnode(p)) visit(p); }
树、森林
树的存储结构:顺序存储结构，链式存储结构都要求唯一反映出树中各结点之间的逻辑关系。
1. 双亲表示法: 采用一组连续的空间来存储每个结点，在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置,根结点下标为0，伪指针域为 -1 。
```
#define MAX_TREE_SIZE_100
// 树的结点定义
typedef struct{
ElemType data;
int parent;
}PTNode;
// 树的类型定义
typedef struct{
PTNode nodes [MAX_TREE_SIZE];
int n ;
}PTree;
```
该存储结构利用了每个结点只有唯一双亲结点的特性(根结点除外)，很快得到每个结点的双亲结点，但是求结点的孩子时却需要遍历整个结构。
2. 孩子表示法:
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，N 个结点有 N 个孩子链表，叶子结点的孩子链表为空。
这种存储结构比较适合寻找结点的孩子结点而寻找双亲的操作需要遍历 N 个结点中孩子链表指针域所指向的 N 个孩子链表。
3. 孩子兄弟表示法(二叉树表示法): 以二叉链表作为树的存储结构左孩子右兄弟，每个结点包含: 结点值，指向第一个孩子结点的指针，下一个兄弟结点的指针。
```
typedef struct CSNode{
ElemType data;
strcut CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
```
存储表示法比较灵活，可以方便的实现树转换为二叉树的操作，易于查找孩子的结点，若增设一个parent域指向父结点，则查找父结点也比较方便。
- 树、森林、二叉树的转化: *
二叉树和数都可以用二叉链表的存储结构，以二叉链表为媒介可以导出树与二叉树的对应关系，给定一棵树可以唯一找出一个二叉树与之对应
- 树转换为二叉树: 左孩子右兄弟
- 森林转化为二叉树: 第一棵树的根转化为二叉树的根，左子树为左子树，第二棵树转化为右子树，第三棵树转化为右子树的右子树，
- 二叉树转化为森林: 与上相反
树和森林的遍历 *
树的遍历操作
- 先根遍历: 类似二叉树的先序遍历
- 后根遍历: 类似二叉树的中序遍历
- 层次遍历:
森林的遍历操作
- 先序遍历
- 中序遍历
树的应用 —— 并查集*
Union
Find
Initial
树与二叉树的应用:
二叉排序树(BST)，二叉查找树: 若不为空，则左子树的结点值小于根结点，右结点的结点值大于根结点的结点值。
二叉排序树是一个递归的数据结构可使用递归算法对其进行各种运算。
对其进行中序遍历可以得到一个递增的有序序列。
二叉排序树的非递归查找算法
``` BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){ // 查找函数返回值指向关键字值为 key 的结点指针，若存在，返回NULL p == NULL; // p 指向被查找结点的双亲，用于插入和删除操作中 while(T != NULL && kry != T->data){ p = T; if(key<T->data) T= T->lchild; else T= T->rchild; } return T; } ```二叉排序树的插入:
``` int BST_Insert(BiTree &T,keyType k){ // 在二叉排序树中插入一个关键字为k的结点 if(T==NULL){ T = (BiTree)malloc(sizeof(BSTNode)); T ->key = k; T ->lchild = T ->rchild = NULL; return 1; }else if(k ==T->key) return BST_Insert(T->lchild,k); else return BST_Insert(T->rchild,k); } ```二叉排序树的构造:
``` void Creat_BST(BiTree &T,KeyType str[],int n){ // 用关键字数组 str[] 建立一个二叉排序树 T = NULL; int i=0; while(i<n){ BST_Insert(T,str[i]); i++; } } ```二叉排序树的删除:
删除操作按照三中情况来处理:
- 若为叶子结点则直接删除
- 若只有一棵左子树或者右子树直接代替原来的位置
- 若结点 Z 有左右两棵子树，则令 Z 的直接后继(前驱)代替 Z ，然后从二叉排序树中删去这个直接后继(直接前驱),这样就转换成上面2中情况。
二叉排序树的查找效率分析：
对于高度为H的二叉排序树其插入和删除操作的运行时间都是 O(H)。最坏情况下构造二叉排序树的输入序列是有序的，则会形成单支树排序树性能显著变坏，树的高度也增加为元素的个数 N 。
若二叉排序树为单支树则其平均查找长度和单链表相同为 O(N),若为平衡二叉树则平均查找长度为 O(log2 N)。
二叉排序树无需移动结点只需修改指针即可完成结点的插入和删除操作平均执行时间为 O(log2 N),二分查找的对象是有序顺序表，所花的代价为 O(N)。 若有序表为静态查找表宜采用顺序表作为存储结构，为动态查找表时，则应选择二叉排序树作为其逻辑结构。
平衡二叉排序树(AVL)： 左右子树高度差不超过1.
平衡二叉树的插入: 平衡二叉树插入过程的前半部分与二叉排序树相同，但是在新结点插入后，如果造成了查找路径上的某个结点不在平衡，需要做出调整:
- LL平衡旋转(右单旋转): 在结点A的左孩子(L)的左子树(L)上插入了新结点，A的平衡因子由 1 增至 2 导致以A为根的子树失去平衡
- 将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点
- B的原右子树作为A结点的左子树
- RR平衡旋转(左单旋转): 在结点A的右孩子(R)的右子树(R)上插入了新结点，A的平衡因子由 -1 增至 -2 导致以A为根的子树失去平衡
- 将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点
- B的原左子树作为A结点的右子树
- LR平衡旋转(先左后右双旋转): 在结点A的左孩子(L)的右子树(R)上插入新结点,A的平衡因子由 1 增至 2 导致以A为根的结点失去平衡
- 将A结点的左孩子的右子树向左上旋转
- 将A的左孩子向右上旋转
- RL平衡旋转(先右后左双旋转): 在结点A的右孩子(R)的左子树(L)上插入新结点,A的平衡因子由 -1 增至 -2 导致以A为根的结点失去平衡
- 将A结点的右孩子的左子树向右上旋转
- 将A的右孩子向左上旋转
平衡二叉树的查找: 类似二叉排序树含有 n 个结点的平衡二叉树最大深度为 O(log2n),因此其平均查找长度为 O(log2n)。
- 赫夫曼(Huffman)树和赫夫曼编码：
赫夫曼树的定义: 树中的结点通常被赋予一个表示某种意义的数值，称为该结点的权，从根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度，树中所有叶子结点的带权路径长度之和称为该树的带权路径长度。
在含有 n 个带权结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为赫夫曼树，也称为最优二叉树
赫夫曼树的构造: 给定 N 个权值分别为 w1,w2,w3,...,wN 的结点通过赫夫曼算法构造出最优二叉树
1. 将这 N 个结点分别作为 N 棵仅含一个结点的二叉树，构成森林 F。
2. 构造一个新的结点，并从 F 中选取两棵根结点权值最小的树作为新结点的左右子树，并将新结点的权值置为左右孩子结点权值之和。
3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
4. 重复步骤 2 和 3 ，直到 F 中只剩一棵树为止。
特点:
- 每个初始结点最终都成为叶子结点，并且权值越小的结点到根结点的路径长度越大。
- 构造过程共新建了 N-1 个结点，因此赫夫曼树中的结点总数为 2N-1 。
- 每次构造都选择 2 棵树作为新结点的孩子，一次赫夫曼树中不存在度为 1 的结点。
赫夫曼编码: 对不同的字符不等长的二进制表示称为可变长度编码，反之为固定长度编码。可变长度编码对频率高的字符赋以短编码，而对频率较低的字符赋以较长一些的编码，从而使字符平均编码长度减短，起到压缩数据的效果。赫夫曼树是一种广泛应用而且非常有效地数据压缩编码。
如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。前缀编码的解码也很简单，因为没有一个码是其他码的前缀，所以可以识别出第一个码，将他翻译为原码，在对余下的编码文件重复同样的解码操作，如 00101100 可被唯一地分析为 0、0、101、100。
利用赫夫曼树可以设计出总长度最短的二进制前缀编码。
Note: 0和1表示左子树还是右子树没有明确规定。因此左右结点的顺序是任意的所以构造出的赫夫曼树并不唯一，但是个赫夫曼树的带权路径长度相同且为最优。
几种常见的树:
B+ , B- 树:
B+树: B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。
性质：B+树是B-树的变体，也是一种多路搜索树： 1.其定义基本与B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）； 4.为所有叶子结点增加一个链指针； 5.所有关键字都在叶子结点出现；B-树:
性质：是一种多路搜索树（并不是二叉的）： 1.定义任意非叶子结点最多只有M个儿子；且M>2； 2.根结点的儿子数为[2, M]； 3.除根结点以外的非叶子结点的儿子数为[M/2, M]； 4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字） 5.非叶子结点的关键字个数=指向儿子的指针个数-1； 6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]； 7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树； 8.所有叶子结点位于同一层；