计算机二级C语言公共基础知识树和二叉树相关知识点思维导图

在树结构中，每一个节点只有一个前件，称为父节点；没有前件的节点只有一个，称为树的根节点，简称树的根。

在树结构中，每一个节点可以有多个后件，称为该节点的子节点。

没有后件的节点称为叶子节点。

在树结构中，一个节点所拥有的后件个数称为该节点的度，所有节点中最大的度称为树的度。

定义一棵树的根节点所在的层次为1，其他节点所在的层次等于它的父节点所在的层次加1。

树的最大层次称为树的深度。

在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树

节点A是树的根节点

节点D、H、I、F、G均为叶子节点

根节点A和节点E的度为2，节点B的度为3，节点C的度为1，叶子节点D、H、I、F、G的度为0。所以，该树的度为3

根节点A在第1层，节点B、C在第2层，节点D、E、F、G在第3层，节点H、I在第4层。该树的深度为4

节点A有2棵子树，它们分别以B、C为根节点。节点B有3棵子树，它们分别以D、E、F为根节点，其中，以D、F为根节点的子树实际上只有根节点一个节点

树中的节点数等于树中所有节点的度之和再加1

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

②每个节点最多有两棵子树（分别简称为左子树和右子树），即二叉树中不存在度大于2的节点；

③二叉树的子树有左右之分，其次序不能任意颠倒。

性质1：在二叉树的第K层上，最多有2的（K-1）次幂个节点。（K≥1）

性质2：深度为m的二叉树中，最多有2的m次幂-1个节点。

性质3：对任何一棵二叉树，度为0的节点（即叶子节点）总是比度为2的节点多一个。

性质4

满二叉树和完全二叉树是两种特殊形态的二叉树。

满二叉树

完全二叉树

①前序遍历

②中序遍历

③后序遍历