计算机三级数据库知识点总结——树.doc

树1、 对非空二叉树遍历的三个步骤：访问根节点先序遍历左子树先序遍历右子树。前序是按的顺序得到的序列，对称序是按，后序是按。特例：根节点为A、只有左子树B，对称序为BA、前序为AB；上述序列A的右子树为C，C的左子树为D，后一个序列对称序为BADC、前序为ABCD。2、 如果对一棵有n个节点的完全二叉树的节点按层序编号，则对任意结点i（）有：如果i=1，结点i是二叉树的根；如果i1,则双亲PARENT（i）是结点i/2。如果2in，则结点i无左孩子；否则其左孩子结点为2i。 如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1. 3、 B树只适合随机检索，不适合顺序检索。B+树更常用于顺序检索。 二者都是多路查找树，都是动态索引结构，都能有效支持随机检索。4、 栈的应用：数值转换、括号匹配检验、行编辑程序、表达式求值、树的层序遍历、二叉树对称序周游算法等。5、 栈的基本运算：push是往栈中插入一个元素、pop是从栈中删除一个元素、top是求栈顶元素的值。6、 串由0个或多个字符组成的有限序列。串中字符的数目就是串的长度。串的存储有顺序存储和链式存储两种。串的基本运算：创建串、判断串是否为空、计算串长度、串链接、求子串和串的定位。7、 栈和队列的存储方式，可以是顺序方式，也可以是链式方式。栈和队列都可为空。栈能应用于递归过程实现。8、 队列的基本操作：构造空队列、清空队列、判断队列是否为空、求队列长度、读取队列头元素的值、在队尾插入新元素、删除队头元素。9、 二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根结点及两棵不相交的，分别称作这个根的左子树和右子树的二叉树组成。最简单的二叉树是空二叉树。10、 二叉树不是树的特殊情况。树和二叉树之间最主要的区别是：二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。每一棵二叉树都能唯一的转化成它所对应的树。11、 二叉树转换为树或森林的方式是：若结点x是双亲y的左孩子，则把x的有孩子，右孩子的右孩子都与y用线连接起来，最后去掉所有双亲到右孩子的连线即可。12、 霍夫曼算法是用来求具有最小带权外部路径长度的扩充二叉树的算法。13、 霍夫曼树也称为最优二叉树，权值大的结点离根最近，没有度为1的结点（二叉树最少也有2层，根不计）。14、 二叉树的带权路径长度=每个叶节点的权值相应的路径长度。15、 一个m阶的B树满足以下条件：树中每个结点至多有m棵子树；除根结点和叶子结点外，其他每个结点至少有m/2子树；若根结点不是叶子结点，则至少有2棵子树；所有叶子结点都出现在同一层，叶子结点不包括任何关键字信息；有k个孩子的非终端结点恰好包含有k-1个关键字。不可为空。16、 AVL树（平衡二叉排序树）的性质：每个结点的左、右子树深度之差的绝对值不超过1.17、 按行优先顺序存储的二维数组地址计算公式为LOC（）=LOC（）+【（i-1）*n+j-1】*d。其中：（1）LOC（）是开始结点的存放地址（即基地址）；（2）d为每个元素所占的存储单元数；（3）数组中任一元素可通过地址公式在相同时间内存储。即顺序存储的数组是随机存取结构。 按列优先存储的二维数组地址计算公式为 LOC（）=LOC（）+【（j-1）*m+i-1】*d18、 按先根次序周游树正好等同于按前序法周游对应的二叉树，按后根次序周游树正好等同于按对称序法周游对应的二叉树。19、 二叉排序树（Binary Sort Tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不为空，则左子树上所有结点的值均小于它的根节点的值；（2）若右子树不为空，则右子树上所有结点的值均大于它的根节点的值；（3）左、右子树也分别为二叉排序树。20、 小根堆的定义：Ki=K2i且Ki=K2i+1。 N个关键字序列K1、K2Kn成为堆。堆实际上是满足如下性质的完全二叉树：树中任一非叶节点的关键字均不大于（不小于）其左右孩子（若存在）结点的关键字。即堆实际上是一棵完全二叉树结点的层次序列。21、 二叉树第n层的结点数为2（n-1)；根为1层时。22、 如果一棵二叉树最多只有最下面的两层结点，度数可以小于2，且最下面一层的节点都集中在该层最左边的若干位置，则此二叉树为完全二叉树。若要结点最少，则说明最后一层上只有1个结点，其余层是满二叉树，所以，最少有2k。23、 设根节点的层次为0，则高度为K的二叉树的最大结点值（即为满二叉树）是2k+1-1(有疑问），最小节点数为2k。24、 在有n个结点的二叉树的llink-rlink法存储表示中，必有n+1个空指针。（n个结点的树一共有2n个指针域，而树中只有n-1条边，故树中的空指针数为2n-(n-1)=n+1）25、 广义表是递归定义的，可以被其他广义表共享，当其为空表时，其长度为0.26、 三元组法和十字链表法都可以用于稀疏矩阵的存储表示。27、 三元组方法存储稀疏矩阵是将稀疏矩阵中所有非零元素列举出来，但它不反映稀疏矩阵中同行或同列元素的关系，从三元组的行数就可以知道非零元素的个数。28、 二分法查找的优点是比较次数少，查找速度快，对有n个数据元素的线性表（要求以顺序方式存储）进行二分法查找，若查找成功，给定值最多与个关键字进行比较。29、 查询处理器主要模块：查询编译器和查询执行引擎。30、 B+树的所有关键码都出现在叶结点上，上面隔层节点中的关键码均是下层结点的最大关键码的复写。霍夫曼应用实例：对于给出的一组权w=10，12，16，21，30，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度是多少？1、 每行选出最小的两个数相加10 12 16 21 30 16 21 22 30 22 30 37 37 52 892、将较小的数排在左子树,则其扩充的二叉树即为: 89 / 37 52 / / 16 21 22 30 / 10 123、由图可看出所有的权都在最外部,所以扩充二叉树的带权外部路径长度为:16*2+21*2+30*2+10*3+12*3=200.堆：小顶堆 1、 先将所有的值按顺序排成二叉树，从左至右排列；2、 看是否满足任一非叶节点的关键字均不大于其左右孩子结点的关键字；3、 不满足的进行替换，直至满足