树是 n 个结点的有限集。在任意一颗非空树中：（1）有且仅有一个特定的称为根的结点；（2）当 n>1 时，其余结点可分为 m (m>0) 个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一颗树，并且称为根的子树。 例如，上图中(a)是只有一个根结点的树；(b)是有13个结点的树，其中 A 是根，其余结点分成 3 个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2、T3都是根 A 的子树，且自身也是一颗树。
树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为结点的度。例如，上图中(b)，A 的度为 3，C 的度为 1，F的度为 0。
度为 0 的结点称为叶子或者终端结点。上图中(b)，结点K、L、F、G、M、I、J都是树的叶子。
度不为 0 的结点称为非终端结点或分支结点。除了根结点之外，分支结点也称为内部结点。
树的度是树内各结点的度的最大值。上图中(b)的树的度为3。
结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。例如，上图(b)中，D 为 A 的子树 T3 的根，则 D 是 A 的孩子，而 A 则是 D 的双亲，同一个双亲的孩子之间互称兄弟。例如，H、I 和 J 互为兄弟。将这些关系进一步推广，可认为 D 是 M 的祖父。
结点的祖先是从根到该结点所经分支上的所有结点。例如，M 的祖先是 A、D 和 H。以某结点为根的子树中任一结点都称为该结点的子孙。例如，B 的孙子为 E、K、L 和 F。
结点的层次从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 l 层，则其子树的根就在第 l+1 层。其双亲在同一层的结点互为堂兄弟。例如，结点 G 与 E、F、H、I、J 互为堂兄弟。
树中结点的最大层次称为树的深度或高度。上图(b)的树的深度为 4。
如果将树中结点的各子树看成从左至右是有序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林是 m(m≥0) 棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。
二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于 2 的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。所以二叉树是有序树。
二叉树可以为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由此这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有 5 种基本形态。
如果⼀棵⼆叉树只有度为0的结点和度为2的结点，并且度为0的结点在同⼀层上，则这棵⼆叉树为满⼆叉树。
这棵⼆叉树为满⼆叉树，也可以说深度为 k，有 2k-1 个节点的⼆叉树。
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下⾯⼀层的节点都集中在该层最左边的若⼲位置。若最底层为第 h 层，则该层包含 1~ 2h-1 个节点。
深度为 k 的，有 n 个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。
其实堆就是一个完全二叉树。
⼆叉搜索树是有数值的，⼆叉搜索树是⼀个有序树。
平衡⼆叉搜索树⼜被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。
在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。
利用归纳法证明此性质。
i = 1时，只有一个根结点。显然，2i-1 = 20 = 1 是对的。
现在假定对所有的 j，i ≤ j < i，命题成立，即第 j 层上至多有 2j-1 个结点。那么，可以证明 j = i 时命题也成立。
由归纳假设：第 i-1 层上至多有 2i-2 个结点。由于二叉树的每个结点的度至多为 2，故在第 i 层上的最大结点数为第 i-1 层上的最大结点数的 2 倍，即 2×2i-2 = 2i-1。
深度为 k 的二叉树至多有 2k-1 个结点，(k≥1)。
由性质 1 可见，深度为 k 的二叉树的最大结点数为
对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。
设 n1 为二叉树 T 中度为 1 的结点数。因为二叉树中所有结点的度均小于或等于 2，所以其结点总数为
再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设 B 为分支总数，则 n = B + 1。由于这些分支是由度为 1 或 2 的结点射出的，所以又有 B = n1 + 2n2。于是得
由式(6-1)和(6-2)得
具有 n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。
证明：假设深度为 k，则根据性质 2 和完全二叉树的定义有
如果对一棵有 n 个结点的完全二叉树( 其深度为⌊log2n⌋+1 )的结点按层序编号( 从第 1 层到第⌊log2n⌋+1层，每层从左到右 )，则对任一结点 i(1≤i≤n)，有
证明：
我们只要先证明(2)和(3)，便可以从(2)和(3)导出(1)。
对于 i=1，由完全二叉树的定义，其左孩子是结点 2。若 2>n，即不存在结点 2，此时结点 i 无左孩子。结点 i 的右孩子也只能是结点 3，若结点 3 不存在，即 3>n，此时结点 i 无右孩子。
对于 i>1 可分两种情况讨论：
（1）设第 j (1≤j≤⌊log2n⌋) 层的第一个结点的编号为 i (由二叉树的定义和性质 2 可知 i=2j-1)，则其左孩子必为第 j+1 层的第一个结点，其编号为 2j=2(2j-1)=2i，若 2i>n，则无左孩子；其右孩子必为第 j+1 层的第二个结点，其编号为 2i+1，若 2i+1>n，则无右孩子；
（2）假设第 j (1≤j≤⌊log2n⌋) 层上某个结点的编号为 i (2i-1≤i≤2j-1)，且 2i+1<n，则其左孩子为 2i，右孩子为 2i+1，又编号为 i+1 的结点是编号为 i 的结点的右兄弟或者堂兄弟，若它有左孩子，则编号必为 2i+1=2(i+1)，若它有右孩子，则其编号必为 2i+3=2(i+1)+1。所示为完全二叉树上结点及其左、右孩子结点之间的关系。
