二叉搜索树概念的引出和三种遍历方式（前中后序）

二叉树是一种非线性的结构

作为二叉树，其最多只有两个子树

本篇博客介绍的二叉搜索树，是使用最多的二叉树之一

二叉搜索树的特点：

1. 二叉搜索树每个节点的值大于左子树所有节点的值，小于其右子树所有节点的值

2. 不含重复元素

3. 元素具有可比较性

/** 既然要实现“比较”的功能 

那么，应实现两个接口（“或”的关系）：

Comparable：作内部比较，方法为 compareTo

Comparator：作外部比较

---

下面将以简单的例子，来说明二叉搜索树的特性：

请以二叉搜索树的形式排列以下元素：

5、1、8、3、4、7、9

依据上面我们给出的二叉搜索树的特点，我们对以上一列元素进行排列，得出结果如图所示：

---

 

下面将介绍二叉树的三种遍历方式（前、中、后序进行遍历）

所谓二叉树的遍历，即：

按照相应的规则将二叉树中每个节点访问一次

所谓的 “序” —— 每个子树根节点的访问顺序

 

 

1.   前序

先          访问一个节点的根节点

再          访问左子树

最后      访问右子树

 

依照前序的特点进行遍历，那么输出结果应为 ——

28、16、13、22、30、29、42

 

 

2.   中序

先          访问左子树

再          访问一个节点的根节点

最后     访问右子树

 

依照中序的特点进行遍历，那么输出结果应为 ——

13、16、22、28、29、30、42

 

其实，通过输出结果来看，

我们观察到：中序的输出结果其实就是二叉搜索树排序后的结果

 

3.   后序

先          访问左子树

再          访问右子树

最后      访问一个节点的根节点

 

依照后序的特点进行遍历，那么输出结果应为 ——

13、22、16、29、42、30、28