二级共公基础知识教程

1.6树和二叉树

一，树的基本概念

在树形结构中，每个节点只有一个前件，称为父节点，只有一个没有前件的节点，称为树的根节点。
在树形结构中，每个节点可以有多个后代，都称为该节点的子节点。没有后继节点的节点称为叶节点。
在树形结构中，一个节点所拥有的后继数称为该节点的度。
叶节点的度数为0。
树的层次结构称为树的深度。
在算术表达式中，有运算符和操作数。一个运算符可以有多个操作数。例，正(+)等只有一个操作数，称为单目算子；两个操作数称为双目运算符和三元运算符。
用树来表示算术表达式的原理是这样的:
表达式中的每一个运算符对应树中的一个节点，称为运算符节点。
运算符的每个操作数都是树中运算符节点的子树(树中的顺序是从左到右)。
操作数中的单个变量都是叶节点。

二、二叉树及其基本性质

1.什么是二叉树
二叉树是一种非常有用的非线性结构。二叉树有以下两个特征:
非空二叉树只有一个根节点；
每个节点最多有两个子树，称为节点的左子树和右子树。
从上述特征可以看出，在一棵二叉树中，每个节点的度都是2，即所有子树(左子树或右子树)也都是二叉树，树结构中每个节点的度可以是任意的。另外，二叉树中每个节点的子树明显分为左子树和右子树。可以没有，或者根本没有。
二叉树的基本性质
性质1:在二叉树的第K层上，最多有(K≥1)个节点。
性质二:一棵集中度为m的二叉树最多有2m-1个节点。
深度为m的二叉树表示二叉树共有m层。
性质3:在任何二叉树中，度为0的节点(即叶节点)总是比度为2的节点多一个。
性质4:n个节点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取的整数部分。
满二叉树和完全二叉树
满二叉树和完全二叉树是二叉树的两种特殊形式。
满二叉树
所谓满二叉树，就是指这样的二叉树；除了最后一层，每层上的所有节点都有两个子节点。也就是说，在全二叉树中，每一层的节点数达到值，即全二叉树的第k层有2K-1个节点，深度为m的全二叉树有2m-1个节点
完全二叉树
所谓完全二叉树，是指除最后一层外，每一层的节点数都达到值的二叉树；在最后一层，只有右边的几个节点缺失。
列具体来说，如果二叉树的节点从根节点开始从上到下从左到右用自然数编号，那么一棵深度为m、节点数为n的二叉树称为完全二叉树当且仅当每个节点对应于深度为m的完全二叉树中编号为1到n的节点..
对于一棵完整的二叉树，叶节点只能出现在层次结构的两层上；对于任何节点，如果其右分支下的后代的级别是P，则其左分支下的后代的级别不是P就是p+1。
从全二叉树和完全二叉树的特点可以看出，全二叉树也是完全二叉树，而完全二叉树一般不是全二叉树。
完全二叉树还具有以下两个性质:
性质5:具有n个节点的完全二叉树的深度为[log2n]+1。
性质6:设一棵完整的二叉树有n个节点。如果节点从根节点开始依次用自然数1，2，…，n编号(每层从左到右)，对于编号为k (k=1，2，…n)的节点得出如下结论:
如果k=1，则该节点是根节点，它没有父节点；如果k>1，则该节点的父节点号为INT(k/2)。
如果2k≤n，编号为k的节点的左子节点号为2k；否则，该节点没有左子节点(显然也没有右子节点)。
如果2k+1≤n，编号为K的节点的右子节点号为2k+1；否则，该节点没有正确的子节点。

三、二叉树的存储结构

二叉树的遍历
二叉树的遍历是指不重复访问二叉树的所有节点。
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。
1。前序遍历(DLR)
所谓前序遍历是指先访问根节点，然后遍历左子树，最后遍历右子树。而且在遍历左右子树时，仍然是先访问根节点，然后遍历左子树，最后遍历右子树。f，c，a，d，b，e，g，h，P
2、中序遍历
所谓中序遍历是指在访问根节点、遍历左子树、遍历右子树三个步骤中，先遍历左子树，再遍历根节点，最后遍历右子树；而且在遍历左右子树时，仍然是先遍历左子树，然后访问根节点，最后遍历右子树。a、C、B、D、F、E、H、G、P
3、后序遍历
所谓中序遍历，是指在访问根节点、遍历左子树、遍历右子树三个步骤中，先遍历左子树，再遍历右子树，最后遍历根节点；而且在遍历左右子树时，还是先遍历左子树，再遍历右子树，最后访问根节点。阿、B、D、C、H、P、G、E、F

1.7搜索技术

一.顺序查询

顺序搜索也叫顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下:从线性表中的第一个元素开始，依次将线性表中的元素与被检查的元素进行比较，如果相等，则表示找到了(即查找成功)；如果将线性表中的所有元素与被检查的元素进行比较，但不相等，则说明线性表中找不到元素(即搜索失败)。
顺序搜索的效率很低。以下两种情况只能按顺序查找:
如果线性表是无序的(即表中元素的排列是无序的)，那么无论是顺序存储结构还是链式存储结构都只能按顺序查找。
即使是有序线性表，如果采用链式存储结构，也只能按顺序查找。

第二，二分法搜索

二分搜索法仅适用于存储的有序表。这里的有序表是指元素按非降序排列(即从小到大，但允许相邻元素的值相等)的线性表。
如果有序线性表的长度为n，检查的元素为x，则拆分搜索的方法如下:
将x与线性表中的中间项进行比较:
如果中间项的值等于x，则搜索结束；
如果x小于中间项的值，用同样的方法在线性表的前半部分(即中间项之前的部分)查找；
如果x大于中间项的值，则以同样的方式在线性表的后半部分(即中间项之后的部分)进行搜索。
这个过程一直持续到查找成功或者子表长度为0(表示线性表中没有这个元素)。
显然，只有在有序线性表按顺序存储的情况下，才能使用二分搜索法，二分搜索法的效率远高于顺序搜索。可以证明，在最坏的情况下，二分搜索法只需要比较log2n次，而顺序搜索需要比较n次。