一、前言
树是数据结构中一种非常重要的非线性存储结构.
二、树的基本概念
1.树（tree） 是包含 n(n≥0) 个结点，当 n=0 时，称为空树，非空树中（n-1）条边的有穷集。
2.在非空树中：
- 每个元素称为结点（node）
- 有一个特定的节点被称为根结点或树根（root）
除根结点之外的其余数据元素被分为个互不相交的集合，其中每一个集合本身也是一棵树，被称作原树的子树（subtree）
3.树的一些术语：
- 孩子结点或子结点 ： 一个结点含有的子树的根结点称为该结点的子结点；
- 节点的度： 一个节点含有的子结点的个数称为该结点的度；
- 叶子结点： 度为0的结点称为叶子结点；
- 非叶子结点或分支结点： 度不为0的结点；
- 双亲节点或父节点： 若一个节点含有子结点，则这个结点称为其子结点的父结点；
- 兄弟节点： 具有相同父结点的结点互称为兄弟结点；
- 树的度： 一棵树中，最大的结点的度称为树的度；
- 节点的层次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
- 树的高度或深度： 树中结点的最大层次；
- 堂兄弟节点： 双亲在同一层的结点互为堂兄弟；
- 节点的祖先： 从根到该结点所经分支上的所有结点；
- 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙；
- 森林： 由棵互不相交的树的集合称为森林。
- 有序树： 树中各棵子树的排列顺序是有先后次序，则称该树为有序树。（默认都是有序树）
（参考 百度百科）
三、二叉树的基本概念及性质
1. 二叉树
二叉树是树型结构的一个重要类型。
（1）定义： 二叉树 ( binary tree) 是指树中结点的度不大于2的有序树。（有序是指二叉树左子树和右子树是由顺序的，次序不能任意颠倒。）
（2）性质：
- 在二叉树的第i层上至多有 2^（i-1) 个结点 （i >= 1)
- 深度为k的二叉树至多有 2^k -1个结点 （k >=1)
- 对任何一颗二叉树 T，如果其叶子结点数为n0 ， 度为2的结点数为n2，则n0 = n2 + 1
4.具有n个结点的完全二叉树的深度为
5.如果对一棵有n个结点的完全二叉树（其深度为
)的结点按层序编号 从第一层到最后一层，每层从左到右），对于一结点i （ 1=< i <= n ) 有：
- 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1 ，则其双亲是结点 ?i / 2?
- 如果 2i > n,则结点 i 无左孩子，否则其左孩子是结点2i
- 如果2i+1 > n ,则结点 i 无右孩子；否则其有孩子是结点 2i+1
（性质 3 说明：一棵二叉树除了叶子结点外 剩下的就是度为1或 2 的结点了，n1为度为1的结点个数，则树T结点总数为 n = n0 + n1 + n2 ，再看树的连线数，根结点只有分支出去，没有分支进入所以 分支线总数为 结点总数 减去1 ，度为2的有两条分支线，度为1的有一条分支线，所以 n - 1 = n1 + 2n2，结合前面的等式推出 n0 = n2 + 1）
2. 满二叉树
（1）定义： 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树就叫满二叉树。
（2）性质：
假设满二叉树的高度为h（h >= 1)
- 第i层的结点数量为 2^(i-1)
- 叶子结点数量为 2 ^ (h-1)
- 总结点数量 n = 2^h -1 h =log2(n+1)
- 在同样高度的二叉树中，满二叉树的叶子结点数量最多、总结点数量最多
3. 完全二叉树
（1）定义： 对一棵具有n个结点的二叉树层序编号，如果编号为i（1=< i <= n)的结点与同样深度的满二叉树中编号为i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
（图1 为完全二叉树）
（ 图 2 为完全二叉树）
（图3 不是完全二叉树）
（2）性质：
-
度为1的结点只有一个或者一个没有，且若有度为1的结点一定为左结点
-
同样结点数量的二叉树，完全二叉树的高度最小
-
假设完全二叉树的高度为h （h >= 1)
至少有 2 ^ (h -1)个结点 ，至多有 2 ^ h - 1个结点 -
假设总结点数量为 n ，
如果n为偶数，则叶子结点数量为n0 = n / 2
如果 n 为奇数 n0 =( n+1）/ 2
（由性质1 和 二叉树结点关系式不难推出）
四、总结
1.树是n个结点的有限集，二叉树是树的一个重要分支。 二叉树相对来说是一种比较简单的树形结构，二叉树容易表示和操作，因此二叉树的应用十分广泛。
2.树作为一种重要且应用广泛的存储结构，其知识体系是十分庞大的，本文仅简单介绍常用的树相关的概念和知识点，若有疑问，欢迎指正。
（二叉树相关的算法有很多，在另一篇文章中将会介绍二叉树的四种遍历、二叉树的深度、判断是否为完全二叉树等相关算法。）