【公共基础知识】数据结构与算法(备考三)
文/南城以南hong
这是一个知识付费，知识共享的年代。我将我每天学习的内容进行总结，既是对自己的巩固，也是对你的帮助。
【公共基础知识】数据结构与算法(备考三)
考点七:树
（1）定义:树是一种简单的非线性结构，它是以分支关系定义的层次结构。
（2）关键词:
①父结点:在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点。
②子结点和叶子结点:在树结构中，每一个结点可以有多个后件，称为该结点的子结点，没有后件的结点称为叶子结点。
③度:一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。
④深度:树的最大层次称为树的度。
⑤子树:在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。
考点八:二叉树
（1）定义:二叉树是一个有限的结点集合，该集合或者为空，或者有一个根结点及其两棵互不相交的左右二叉子树所组成。
（2）性质
①一棵非空二叉树的第k层上最多有2∧（k－1）
个结点。（k≧1）
例:当k=3时，有4个结点。
②深度为m的满二叉树中有2∧m－1个结点。
当m=3时，有7个结点。
③对任意一棵二叉树而言，度为0的结点（叶子节点）总是比度为2的结点多一个。
例题:某二叉树中度为2的结点有18个。则该二叉树中有几个叶子结点。答案:19个
（3）满二叉树指除最后一层外，每一层上的所有结点都有两个子结点的二叉树。
（4）完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
（5）二叉树的存储结构（了解）:二叉树通常采用链式存储结构。用于存储二叉树中各元素的存储结点由数据域和指针域（左指针域和右指针域）组成。
（6）二叉树的遍历:（总原则:先左后右）
①前序遍历:根－左－右
②中序遍历:左－根－右
③后序遍历:左－右－根
注:在子树中也满足二叉树的遍历。
（7）补充宝宝定理:
对于完全二叉树而言
*如果它的结点个数为偶数n，则该二叉树中叶子结点的个数=非叶子结点的个数= n/2。
*如果它的结点个数为奇数m，则该二叉树中叶子结点的个数=非叶子结点的个数＋1=（m＋1）/2。
考点九:查找技术
（1）基本概念:查找，即在某种数据结构中找出满足指定条件的元素。查找的结果有两种可能:查找成功和查找不成功。
（2）顺序查找:
①定义:从线性表的第一个元素开始，将目标元素与线性表中的元素逐个进行比较，如果相等，则查找成功，返回结果。若整个线性表扫描完毕后，未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，则查找失败。
②适用范围
-若线性表中的元素是无序排序就能进行顺序查找。
-即便是有序线性表，若采用链式存储结构也只能进行顺序查找。
③在最坏的情况下，最后一个元素是目标元素，顺序查找需要比较n次。
在平均情况下，需要比较二分之n次。
（3）二分法查找
①适用条件:使用二分法查找的线性表必须满足用顺序存储结构，且线性表示有序表两个条件。
②在最坏的情况下，对于长度为n的有序线性表，二分法查找只需要比较㏒2n次。
考点十:排序技术
由于内容多而杂，且难理解，所以只需掌握如下表格（手绘，乱了点，求原谅）
【公共基础知识】数据结构与算法(备考三)
【敬请期待下次更新】
上一篇:备考二
