|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B-树的定义：一棵m阶的B-树，或为空树，或为满足下列特性的m叉树。
|
|
|
|
|
|
|
|
|
|
|
|
（n,A0,K1,A1,K2，A2,…,Kn,An)
|
|
|
|
式中，Ki(i=1,2,…,n)为关键字，且Ki<Ki+1(i=1,2,…,n-1)；Ai(i=1,2,…,n)为指向子树根节点的指针，且指针Ai-1，所指子树中所有节点的关键字均小于Ki(i=1,2,…,n)，An所指子树中所有节点的关键字均大于Kn，为节点中关键字的个数。
|
|
|
|
（5）所有的叶子节点都出现在同一层次上，并且不带信息（可以看作外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空）。
|
|
|
|
B-树上进行查找的过程是：首先在根节点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
|
|
|
|
树是由一个或多个节点组成的有限集T，它满足以下两个条件：有一个特定的节点称为根节点；其余的节点分成m个互不相交的有限集T1, T2, …, Tm，其中每个集又都是一棵树，称T1, T2, …, Tm为根节点的子树。
|
|
|
|
可见树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。
|
|
|
|
|
|
|
|
|
|
|
|
若将树中节点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
树是非线性结构，存储树时，须把树中结点之间存在的关系反映在树的存储结构中。树有很多存储结构，这里仅介绍最常用的两种。
|
|
|
|
|
|
树的标准存储结构由结点的数据和指向子结点的指针数组组成；对于度为M的树，其指针数组中的元素个数为M。
|
|
|
|
|
|
由于树的带逆存储结构需要一个从子结点指向父结点的指针，因而该结构在标准存储结构的基础上，需要在树的结点中增加一个指向其双亲结点位置的指针。
|
|
|
|
树的遍历是树的基本操作之一，也是最重要的操作之一。树的遍历含义是指：按照某种要求依次访问树中的每个结点，每个结点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
|
|
|
|
（1）树的前序遍历。首先访问根结点，然后从左到右前序遍历根结点的各棵子树。树的前序遍历递归算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
