“树”：一种非线性的存储结构，具有“一对多”关系的元素的集合

n(n >= 0)个结点的有限集合，n=0时是一棵空树，对于一棵非空树具有以下特性

• 有且仅有一个根节点(ROOT)
• 当n>1时，其余的结点可分为m(m>0)个互不相交的有限集，其中每个集合本身也是一棵树，称为根的子树

“树” 基本术语

• 结点： 树结构存储的每一个数据元素称为结点 度： 一个结点拥有的子树数(degree) 一棵树中的最大的度数为该树的度
• 叶子结点： 度数为0的结点(终端结点) 开始结点： 根结点 分支结点： 度数不为0的结点(非终端结点) 层次： 从根开始算起，根为第一层，其余结点的层次等于其双亲结点的层数+1
• 深度(高度)：树种结点的最大层次 有序树： 树中结点的各子树从左至右依次有序且不能交换

二叉树

每个结点至多只有两棵子树，或者是空集，或者一个根结点及两颗互不相交的分别作为这个根的左子树，右子树组成

二叉树性质

1. 二叉树中，第 i 层最多有2^i-1个结点。
2. 如果二叉树的深度为 K，那么此二叉树最多有2\^K-1个结点。
3. 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1。

完全二叉树特有的性质

n个结点的完全二叉树的深度为log₂b+1