二叉树

[图论]中的定义二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根节点的度不大于2。有了根节点之后，每个顶点定义了唯一的父节点，和最多2个子节点。然而，没有足够的信息来区分左节点和右节点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。二叉树(BinaryTree)的类型二叉树是一个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为n0，分支度为2的总数为n2，则n0=n2+1。一棵深度为k，且有2k−−-->1{\displaystyle2^{\begin{aligned}k\end{aligned}}-1}个节点的二叉树，称为满二叉树（FullBinaryTree）。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉...