我们简明扼要的整理下二叉树，以及二分搜索树的特征及代码实现
二叉树
我们分析下，二叉树的节点元素 ,除了要存储数据，还有两个引用分别指向其他节点
class Node { E e; Node left ; // 左孩子 Node right ; // 右孩子 }
特征
- 和链表一样，是动态数据结构
- 每个节点最多只能分出来两棵树 (同样类比多叉树)
- 二叉树具有唯一的根节点
按照上图， 16就是 28根节点的左孩子， 30 就是28的右孩子 。 依次类推 13是16的左孩子， 22是16的右孩子。 29是30的左孩子， 42是30的右孩子。 - 二叉树每个节点最多有两个孩子
叶子节点是没有任何孩子的节点。 上图是一个完整的二叉树 ，实际应用中并不都是这种情况。 - 二叉树每个节点最多有一个父亲节点，只有根节点没有父亲节点。
- 二叉树具有天然的递归结构
每个节点的左子树也是二叉树
每个节点的右子树也是二叉树
- 二叉树不一定是“满”的
二分搜索树 Binary Search Tree
特征
- 二分搜索树是二叉树，二叉树的特征全部适用于二分搜索树
- 二分搜索树的每个节点的值
大于其左子树的所有节点的值
小于其右子树的所有节点的值
- 每一棵子树也是二分搜索树
比如下面的二分搜索树
限制（存储的元素必须具有可比性）
为什么要这么设计呢？
其实是为了特定的场景，我们使用二分搜索树查询数据的话，这两个数可以比较的话，那么就可以明确的知道这个数据在左边还是在右边了，查询效率高。
所以什么样的数据存到二分搜索树中才能搜索呢？ —> 存储的元素必须具有可比较性
整型自然不必说了，可以比较大小，如果我们存储的是个对象，那这个对象一定要能比较 。 举个例子存储的对象为Car , 要么这个Car 可以按照价格比较，要么可以按照重量比较，总之能比较就可以。
在Java中这个对象要继承Comparable接口
Code
添加数据
/** * * * @ClassName: BinarySearchTree * * @Description: 二分搜索树 --> 元素必须可以比较 * * @author: Mr.Yang * * @date: 2020年2月8日 下午12:59:02 * * @param <E> */ public class BinarySearchTree<E extends Comparable<E>> { /** * * @ClassName: Node * * @Description: 数据节点类 * * @date: 2020年2月8日 下午12:58:44 */ private class Node { private E e;// 数据 private Node left; // 左孩子 private Node right;// 右孩子 public Node(E e) { this.e = e; this.left = null; this.right = null; } } private Node root;// 根节点 private int size; // 当前数据量 /** * * * @Title:BinarySearchTree * * @Description:默认构造函数 */ public BinarySearchTree() { this.root = null; this.size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } /** * * * @Title: add * * @Description: 向二分搜索树中添加新的元素e * * @param e * * @return: void */ public void add(E e) { // 根节点的非空判断 if (root == null) { root = new Node(e); size++; } else add(root, e); } /** * * * @Title: add * * @Description: 向以node为根的二分搜索树中插入元素e，递归算法 * * @param node * @param e * * @return: void */ private void add(Node node, E e) { if (e.equals(node.e)) return; else if (e.compareTo(node.e) < 0 && node.left == null) { // 插入到左子树 node.left = new Node(e); size++; return; } else if (e.compareTo(node.e) > 0 && node.right == null) {// 插入到右子树 node.right = new Node(e); size++; return; } // 递归调用 if (e.compareTo(node.e) < 0) add(node.left, e); else // e.compareTo(node.e) > 0 add(node.right, e); } }
添加数据V2.0
上面的添加方法，OK ，没问题。 但代码量还是有点长
- 我们对Root节点做了特殊的非空判断处理，逻辑上不统一
- 每次插入都有判断节点必须为null的判断
- e.compareTo(node.e)进行了两次的操作才能插入
- 终止条件臃肿
- 空本身就是一颗二叉树，所以遇到空的情况直接插入即可
e.compareTo(node.e) >(<) 0 && node.right(left) == null 其实并没有递归到底。
/** * * * @Title: add public 属性供外部调用 * * @Description: 向二分搜索树中添加新的元素e * * @param e * * @return: void */ public void add(E e) { root = add(root, e); } /** * * * @Title: add 内部调用 私有 递归函数 * * @Description: 返回插入新节点后的二分搜索树的根 * * @param node * @param e * * @return: void */ private Node add(Node node, E e) { if (node == null) { size++; return new Node(e); } // 相等，不做任何操作 if (e.compareTo(node.e) < 0) { node.left = add(node.left, e); } else if (e.compareTo(node.e) > 0) { node.right = add(node.right, e); } return node; }
查找 数据
/** * * * @Title: contains 供外部调用 * * @Description: 判断元素e是否存二分搜索树中 * * @param e * * @return: boolean */ public boolean contains(E e) { return contains(root, e); } /** * * * @Title: contains 内部调用 * * @Description: 判断e是否存在于以node为根的二分搜索树中 递归算法 * * @param node * @param e * * @return: boolean */ private boolean contains(Node node, E e) { if (node == null) { // node为空 返回false return false; } if (e.compareTo(node.e) == 0) { // 相等 返回true return true; } else if (e.compareTo(node.e) < 0) { // 小, 继续递归左子树 return contains(node.left, e); } else { // e.compareTo(node.e) > 0 大, 继续递归右子树 return contains(node.right, e); } }
