在中，二叉树是每个节点最多有两个子树的。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现和。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有![2^{i-1}]()
个结点；深度为k的二叉树至多有![2^k-1]()
个结点；对任何一棵二叉树T，如果其终端结点数为![n_0]()
，度为2的结点数为![n_2]()
，则![n_0=n_2+1]()
。
树和二叉树的三个主要差别：
-
树的结点个数至少为1，而二叉树的结点个数可以为0；
-
树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
-
树的结点无左、右之分，而二叉树的结点有左、右之分。
<完全二叉树和满二叉树>
-
满二叉树：一棵深度为k，且有
![2^k-1]()
个节点称之为满二叉树
-
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树
相关链接是：%E4%BA%8C%E5%8F%89%E6%A0%91
阅读(1557) | 评论(0) | 转发(0) |
