mysql 递归查找父节点_树、二叉树、二叉查找树（二叉搜索树）

1 树

1.1 定义

结合图看，可以比较直观地发现，树(Tree)是元素的集合，每棵树由多个节点(node)组成，用以储存元素。某些节点之间存在着一定的关系，用连线表示，连线称为边(edge)或者链接。边的上端点成为父节点，下端称为子节点。

每个节点可以有多个子节点，而该节点则是相应子节点的父节点。但是每个节点只能有一个父节点(只有一个例外，也就是根节点，它没有父节点)，如图中第一棵树的 S 节点即为根节点。而没有子节点的节点则称为叶子节点或叶节点，如上图中第一棵树的 A、R、X 节点。E、X 的父节点是一个节点，所以它们被称为兄弟节点。

通过上面的观察和分析，这里给出一种相对严格的树的定义。

树是元素的集合

该集合可以为空。此时树中没有元素，称之为空树(empty tree)。

如果该集合不为空，那么该集合至少含有一个根节点以及 0 个或多个子树。根节点与它的子树的根节点用一个边(edge)或链接相连。

1.2 特征(三个特殊概念)

关于树，有三个比较相似，容易搞混的概念：高度(Height)、深度(Depth)、层(Level)。它们的定义如下。

节点的高度 = 节点到叶子结点的最长路径(边数)

节点的深度 = 根节点到这个节点所经历的边的个数

节点的层数 = 节点的深度 + 1

树的高度 = 根节点的高度

单看定义有点抽象，结合图来看会比较好理解。我们可以结合生活中对高度、深度的概念来看，这样理解起来就很方便了。比如，对于高度，生活中我们往往是自下而上来度量，比如第 5 楼、第 10 楼，起点都是地面。对于树这种数据结构中的高度也是一样的类比，从最底层开始进行计数，并且计数的起点是 0。

深度这个概念在生活中则是自上而下度量的，比如形容水深，是从水平面开始度量的。对于树这种数据结构而言也是如此，从根节点开始度量，计数起点从 0 开始(有些书中是从 1 开始，应该都可以，看你怎么定义和使用了，问题不大)。

层数跟深度的计算类似，不过计数的起点是 1，也就是说跟节点位于第一层。

2 二叉树

2.1 定义

二叉树是一种特殊的数据结构，顾名思义，二叉树只有两个叉，也就是两个子节点