计算机三级数据库知识点总结——树VIP免费

树1、对非空二叉树遍历的三个步骤：访问根节点先序遍历左子树先序遍历右子树。前序是按的顺序得到的序列，对称序是按，后序是按。特例：根节点为A、只有左子树B，对称序为BA、前序为AB；上述序列A的右子树为C，C的左子树为D，后一个序列对称序为BADC、前序为ABCD。2、如果对一棵有n个节点的完全二叉树的节点按层序编号，则对任意结点i（）有：如果i=1，结点i是二叉树的根；如果i>1,则双亲PARENT（i）是结点i/2。如果2i>n，则结点i无左孩子；否则其左孩子结点为2i。如果2i+1>n，则结点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、二叉排序树（BinarySortTree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不为空，则左子树上所有结点的值均小于它的根节点的值；（2）若右子树不为空，则右子树上所有结点的值均大于它的根节点的值；（3）左、右子树也分别为二叉排序树。20、小根堆的定义：K[i]<=K[2i]且K[i]<=K[2i+1]。N个关键字序列K1、K2……Kn成为堆。堆实际上是满足如下性质的完全二叉树：树中任一非叶节点的关键字均不大于（不小于）其左右孩子（若存在）结点的关键字。即堆实际上是一棵完全二叉树结点的层次序列。21、二叉树第n层的结点数为2^（n-1)；根为1层时。22、如果一棵二叉树最多只有最下面的两层结点，度数可以小于2，且最下面一层的节点都...