0. 前言
本文不是从入门到精通式的文章。写该文的目的是理清树结构及其解题思路，所以讲解不多而概念性的东西比较多，请见谅。
本文结构：
- 概念铺垫
- 二叉树
- 各种相关算法
- 例题相关
1. 概念铺垫
- 树等价于连通无环图，由一组顶点(vertex)和边(edge)构成。其中，如图所示，A点为根顶点(root)。一般情况下，我们多称顶点为节点(node)。
图中，ABCDEFG为顶点，T1、T2等为边。（图片来自网络，侵删）
-
祖先(ancestor)、后代(descendant)、父亲(parent)、孩子(child)、子树(subtree)、叶子节点(leaf)、度(degree)：在节点
v寻根过程中经过的每一个节点都是其祖先，节点v是其后代。依旧以上图为例，节点E的祖先是B和A，E是B和A的后代，而B又是A的后代。
父亲<-->孩子是特殊的祖先<-->后代关系。若节点u是v的祖先且恰好比v高一层，则称u是v的父亲，v是u的孩子。例如：B与E即为一对父子关系。
节点u所有的后代及其之间的连接边称为子树，记作subtree(v)。例如图中的B D F就构成一棵子树。当一个节点没有后代（没有孩子）时，我们称之为叶子节点。例如，图中的D E F G都是叶子节点。
节点u的孩子总数称为u的度。例如，节点c的度为2，因为c有两个孩子F G。叶子节点的度为0。 -
深度(depth)、高度(height)：沿节点
v到r唯一通路所经过边的数目，称为节点v的深度，记作depth(v)。例如上图中，从节点E走到根节点A的边数是2，所以depth(E) = 2。设节点v深度为v_d，那么我们可以认为节点v处于在第v_d层。特别地，约定根顶点root的深度为0，即depth(root) = 0。
树T中所有节点深度最大值称作该树的高度，记作height(T)。通常约定，仅有一个节点的树高度为0，空树高度为-1。例如，图中所未二叉树高度为2。有些博客文章、教材、讲义中认为该树高度为3，也正确。因为从直观角度来说是3层树，而本文约定高度为2是为方便编程。
2. 二叉树(binary tree)
二叉树图例
定义：如上图所示，二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
性质：
- 在二叉树中，每个节点的度
；
- 同一节点的孩子可以左右区分，即具有左右次序（有序），故二叉树又可称为二叉有序树(ordered binary tree)。
2.1 二叉搜索树（Binary Search Tree, BST）
首先要明确一点的是，二叉搜索树满足所有普通二叉树的特征。但相比普通二叉树而言，二叉搜索树又有如下特征：
假定节点为k:
- 左子树存储着值小于k的节点
- 右子树存储着值大于k的节点
- 每棵子树都满足如上两条特征
References
- 邓俊辉. 数据结构: C++ 语言版[M]. 清华大学出版社, 2012.
- 二叉树--维基百科
- GeeksforGeeks二叉搜索树专题（英文版）
网友评论