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

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

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

二叉搜索树的特点：

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

 

最后给出代码实现（递归）

public class BinSearchTree<E extends Comparable<E>> implements BinTree<E> {
    // Node类的声明
    private class Node {
        E data;
        Node left;
        Node right;
        public Node(E data) {
            this.data = data;
        }
    }

    private Node root; // 根节点
    private int size; // 二叉树节点个数

    @Override
    public void preOrder() {
        preOrder(root);
    }
    /**
     * 以当前节点作为根节点进行 前序 遍历：根左右
     * @param node
     */
    private void preOrder(Node node) {
        if (node == null) {
            return; // 当前节点为空
        }
        System.out.println(node.data); // 当前节点不为空，直接输出
        preOrder(node.left);
        preOrder(node.right);
    }

    //****************************************************************

    @Override
    public void inOrder() {
        inOrder(root);
    }
    /**
     * 以 node为根节点进行 中序 遍历：左根右
     * @param node
     */
    private void inOrder(Node node) {
        if(node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }

    //****************************************************************

    @Override
    public void postOrder() {
        postOrder(root);
    }
    /**
     * 以 node为根节点进行 后序 遍历：左右根
     * @param node
     */
    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }
}