树中的度为0的节点成为叶子节点
树中度不为0的节点是非叶子节点
节点p的层次路径上的所有节点(p除外)称为p的祖先(ancester)
二叉树相关定义
1. 二叉树
二叉树是由那个节点组成的有限集合, 当n>1时, 其余节点分成两个互不相交的子集T1,T2, 其他任何树都可以很容易的转化为二叉树结构, 二叉树可以如下表示
2.满二叉树
满二叉树 : 满二叉树, 指的是对于它来说,每一个节点, 要么度为0, 要么度为2, 也就是说要么没有孩子节点, 要么同时有左右孩子, 从外观上看是一个三角形
3.完全二叉树
完全二叉树 : 在n-1层前必须是满二叉树, 从上到下, 从左到右必须和1到n一一对应, 最后一层可以是只存在左孩子节点