计算机考试知识点树与二叉树思维导图
本思维导图主要总结国家计算机等级考试公共基础知识部分知识点树与二叉树
树图思维导图提供 计算机考试知识点树与二叉树思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点树与二叉树思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：89e750457ffb0ef3a49b53c871096874
思维导图大纲
计算机考试知识点树与二叉树思维导图模板大纲
1．树的基本概念
树是一种比较简单的非线型结构。
在树中所有的数据元素之间具有明显的层次关系。之所以将这种数据结构命名为“树”，是因为其结构看上去像一棵倒长着的树。
在树的图形表示中，上端的结点是前件，下端的结点是后件。
2．二叉树及基本性质
（1）二叉树
二叉树是一种特殊的树，是一种很有用的非线型结构。
所有树结构上的术语都可以用在二叉树上。
二叉树具有以下两个特征：
① 非空二叉树只有一个根结点；
② 每个结点最多有两棵子树，且分别称为该结点的左子树和右子树。在二叉树中，每个结点的度最大为 2，所有的左子树和右子树也均是二叉树。同时，在二叉树中所有的结点可以没有左子树，也可以没有右子树。即没有左子树又没有右子树的结点是叶子结点。
（2）满二叉树
所谓满二叉树是指：除最后一层外，每一层上的所有结点都有两个子结点。
这就是说，在满二叉树中，每一层上的结点数都达到最大值
（3）完全二叉树
所谓的完全二叉树是指：除最后一层外， 每一层上的结点数均达到最大值，最后一层上只缺少右边的若干个结点。
完全二叉树就是去掉最后一层若干个右边结点的满二叉树。
（4）二叉树的基本性质
①二叉树的基本性质。
二叉树具有以下几个基本性质：
性质 1：
性质 2：
性质 3：
在任意一棵二叉树中，叶子结点（即度为0 的结点），总比度为 2 的结点多一个。
性质 4：
②完全二叉树的两项特性。
完全二叉树还具有以下两项特性：
性质 5：
具有 n 个结点的完全二叉树，其深度为[log2n]+1。
性质 6：
设完全二叉树共有 n 个结点。如果从根结点开始， 按层序（每一层从左到右）用自然数“1，2，，，n”给结点进行编号。
3．二叉树的遍历
二叉树的遍历是指按照一定的顺序访问二叉树中的结点，每个结点只被访问一次。
为了保证所有结点被不重不漏地访问，必须按照一定的顺序进行。
（1）前序遍历（DLR）
首先访问根结点，然后遍历左子树，最后遍历右子树；在遍历左、右子树时，也按上述的顺序执行。
可见前序遍历二叉树是一个递归的过程。
对于二叉树的前序遍历，具有的规则：对于空的二叉树，不进行操作返回空值。
对于非空的二叉树的遍历按顺序执行：
①访问根结点；
②前序遍历左子树；
③前序遍历右子树。
（2）中序遍历（LDR）
首先遍历左子树，然后访问根结点，最后遍历右子树；在遍历左、右子树时，也按上述的顺序执行。
可见中序遍历二叉树也是一个递归的过程。
对于二叉树的中序遍历，具有的规则：
①对于空的二叉树，不进行操作返回空值。
②对于非空的二叉树的遍历按顺序执行：中序遍历左子树；访问根结点；中序遍历右子树。
（3）后序遍历（LRD）
首先遍历左子树，然后遍历右子树，最后访问根结点；在遍历左、右子树时，也按上述的顺序执行。
可见后序遍历二叉树同样也是一个递归的过程。
对于二叉树的后序遍历，具有的规则：
①对于空的二叉树，不进行操作返回空值。
②对于非空的二叉树的遍历按顺序执行：后序遍历左子树；后序遍历右子树；访问根结点
相关思维导图模板
树图思维导图提供 计算机考试知识点文件的读写思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点文件的读写思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3addfcccb8839b09c49d9cf6c7c011d1
树图思维导图提供 计算机考试知识点文件指针思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试知识点文件指针思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3b7318d886411679e5e0eb18447fbd02
沪公网安备 31011502019485号
上海工商