ps:此章节迁移有点困难，很多图片格式文件 代码实现在末尾

二叉搜索树定义：

其可以使用一个链表数据结构来表示，其中每个结点就是一个对象。除了key 和卫星数据之外，每个结点还包含属性left 、right 和p，它们分别指向结点的左孩子、右孩子和双亲。如果某个孩子结点和父结点不存在，则相应属性的值为NIL。根结点是树中唯一父指针为NIL 的结点。

对于一个结点，比它大的数放右边生成右子树，比它小的放左边生成左子树

这样棵树的性质使我们可以使用inorder tree walk（中序遍历）

it prints the key of a subtree between printing the values in its left subtree and printing those in its right subtree.

Similarly, a preorder tree walk prints the root before the values in either subtree, and a postorder tree walk prints the root after the values in its subtrees.

前序遍历

前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历

中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

查找二叉搜索树：

寻找最大最小元素->朝右/左寻找子树/元素

后继元素successor/前驱元素