国二计算机等级考试 树与二叉树 思维导图

树是一种简单的非线性结构，其所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点

没有前件的结点只有一个，称为树的根结点，简称。树的根每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度。（结点的分叉数） 所有结点中最大的度称为树的度；树的最大层次称为树的深度。

①叶子结点的度为0

②树的总分叉数=度*对应结点数

③树的结点个数=树的总分叉数+1

①深度：即结构图的层次，从最上面开始数，有几层就是几

②宽度：同一层模块的总个数的最大值

③最大扇入数：模块上最多的引入线条（直接调用该模块的上级模块个数）

④最大扇出数：模块下往外最多引出的线条数（直接调用下级模块的个数）

①非空二叉树只有一个根结点；

② 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

① 在二叉树的第k层上，最多有2k-1个结点。

②深度为m的二叉树最多有2m-1个结点。

③在任意一棵二叉树中，度数为0的结点（即叶子结点）总比度为2的结点多一个。

④具有n个结点的二叉树，其深度至少为 ，其中表示取的整数部分