定义

即每个结点都最多只有两个子结点的树

一些术语

• 树的结点（node）：包含一个数据元素及两个指向子树的分支；
• 孩子结点（child node）：结点的子树的根称为该结点的孩子；
• 双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
• 兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
• 祖先结点: 从根到该结点的所经分支上的所有结点；
• 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
• 结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
• 树的深度：树中最大的结点层；
• 结点的度：结点子树的个数；
• 树的高度：任一棵树到任一叶子结点的最大长度，叶子结点高度为1；
• 树的度： 树中最大的结点度；
• 叶子结点：也叫终端结点，是度为 0 的结点，即最后的没有子树的结点；
• 分枝结点：度不为0的结点；

二叉树有几种类型

• 满二叉树

树上的任一结点除叶子结点外都有两棵子树

• 完全二叉树

叶子结点只会出现在最后一层或倒数第二层，结点不可能只有右子树。也就是说，完全二叉树按照从上至下从左至右，能无间隔的给结点排序。图示如下：