定义
自由树
自由树是一个连通的、无环的无向图。一个可能不连通的的无向无环图为森林。
有根树和有序树
有根树是一棵自由树，其顶点中存在一个与其它顶点不同的顶点，称其为树的根，一棵有根树的顶点常常称为树的结点。
在一棵有根树T中，从根结点r到结点x的唯一简单路径上的任意结点y为x的一个祖先结点，x称为y的后代结点，每一个结点既是自己的祖先也是自己的后代，如果y是x的祖先，并且y不是x，那么称y为x的真祖先,x为y的真后代。如果y是x的真祖先，并且与x直接相连，则称y为x的父母结点，x为y的孩子结点。根是树中唯一没有父结点的结点，如果两个结点的父结点是同一个，则称它们为兄弟结点。一个没有子结点的结点称为叶子结点或外部结点，而非叶结点是内部结点。
树T中一个结点x的子结点数称为结点x的度，从根结点r到结点x的一条简单路径的长度称为x在T中的深度，根结点的深度为0。树的一个层包含了同一深度的所有结点。结点在树中的高度是指从该结点到叶结点最长的一条简单路径的边数。树的高度也就是树中结点的最大深度。
有序树是一棵有根树，其中每个结点的子结点是有序的。
二叉树与位置树
采用递归的方式定义二叉树，一个二叉树T是定义在有限结点集合上的结构，它不包含任何结点或者包含三个不相交的结点集合：一个根结点，一棵称为左子树的二叉树，以及一棵称为右子树的二叉树。
不包含任何结点的二叉树称为空树或零树，有时用符号NIL表示。在上述递归定义中，如果左子树非空则它的根称为整棵树的根的左孩子，类似，右子树的根称为整棵树根的右孩子。如果子树是零树，则称该孩子是缺失的或者丢失的。
位置树是保留了结点位置信息的树，有序树属于位置树。二叉树是结点的度最大为2的有序树，但有序树在子结点仅有一个（即度为1）时可以对子结点进行区分，而二叉树必须区分是左孩子还是右孩子。因此可以使用一个有序树的内部结点来表示二叉树的位置信息，通过将树中每个缺失的孩子使用一个无孩子的结点代替，得到一棵满二叉树，每个结点是叶结点或者度为2，那么就不存在度为1的结点，那么结点的孩子的顺序就保留了位置信息。
这种位置信息的区分可以扩展到k叉树，即每个结点度最大为k的位置树。完全k叉树是所有叶结点深度相同，且所有内部结点度为k的k叉树。如果树的高度为h，则叶结点数目为$h^k$个。
二叉搜索树
搜索树数据结构支持许多动态集合操作，包括搜索，最大值，最小值，查找前驱与后继，插入，删除等操作，即适合作为字典也可以作为一个优先队列。
二叉搜索树是以一棵二叉树来组织的，可以采用链表数据结构来表示，每个结点是一个对象，除了key和卫星数据，每个结点还包含属性left,right和p，分别指向结点的左孩子，右孩子和父母结点。如果某个子结点或者父结点不存在则相应的属性值为NIL。
二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：
设x是二叉搜索树的一个结点，如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。
遍历
遍历顺序：
- 中序遍历：子树根位于左子树和右子树之间
- 先序遍历：子树根位于左子树和右子树之前
- 后序遍历：子树根位于左子树和右子树之后
查询
除了search操作，还支持minimum，maximum，successor，predecessor查询，对于高度为h的二叉树，每个操作可以在O(h)时间内完成。
插入与删除
插入与删除操作会引起二叉搜索树的动态集合变化。必须要修改数据结构来反映这个变化，但修改要保持二叉搜索树的性质成立。
插入
设要将一个新的值v插入到树T，从根结点r开始进行比较，如果$v \le r.key$，那么v需要插入到r的左子树中，这个问题便成了将v插入到以r.left为根的左子树的问题，如果$v \ge r.key$，那么v需要插入到r的右子树中，此外还需要考虑比较相等情况下的处理。
但这个问题可以一般化为将v插入到T的一个子树的问题，在插入时进行比较的过程中，对于一个比较结点x如果$v \le x.key$或者$v \ge x.key$，则继续分别在x的左右子树寻找插入的位置，直到比较结点为空，那么这个空位置即为要寻找的插入位置。
对于比较相等的情况，将其插入到比较结点的左子树或者右子树都是可行的，此时位置查找方式与上述小于或大于的情况一样，另一种做法可以直接使v成为比较结点左子树或右子树的根。但这样需要采用两种方式来修改数据结构，因此一般采用一致的插入到空位置方法。
删除
设要从树T中删除一个结点z，分下面三种情况进行考虑：
- z没有孩子结点：直接删除
- z有一个孩子结点：用z的孩子替换z
- z有两个孩子结点：寻找z的后继y，让y占据z的位置
对于第3种情况，y在z的右子树中，并且y没有左孩子，找到y后，需要将y移出原来的位置并进行拼接，然后替换z，考虑两种情况：
- y是z的右孩子，保留y的右孩子并替换z
- y不是z的右孩子，首先用y的右孩子替换y，然后用y替换z