文/南城以南hong

图片发自简书App

考点七:树

（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次。

考点十:排序技术

由于内容多而杂，且难理解，所以只需掌握如下表格（手绘，乱了点，求原谅）

图片发自简书App

【敬请期待下次更新】
上一篇:备考二

下一篇:备考四

声明:本人已开通维权骑士版权保护计划，转载者请务必阅读此文