基础算法14-二叉搜索树

本文比较轻松简单，就是动态生成一个二叉搜索而已。

动态构建二叉搜索树

首先明确二叉搜索树基本性质，就是根节点的值一定比左孩子的值要大，一定比右孩子的值要小。(为了简单起见，假定元素都是不重复的)

如何动态生成一颗二叉搜索树呢？思路其实是很简单的，就是判断与根节点的左孩子和右孩子分别比较大小，一直到末梢就可以插入元素了。

先准备一个TreeNode：

下面就是对节点进行操作了：

我们来进行前序遍历和中序遍历以及后序遍历看看生成的二叉搜索树是否正确：

运行结果为：

前序遍历为：  6 3 2 1 5 8 7 
中序遍历为：  1 2 3 5 6 7 8 
后序遍历为：  1 2 5 3 7 8 6

经过验证发现完全是正确的。并且我们发现，中序遍历后是一个有序的序列，说明二叉搜索树中序遍历之后有序。

二叉树天生递归，关于它的很多题目用递归就可以解决，后序会有一个单独的文章专门来刷关于二叉树的题目。这里先不赘述了。