十七 二分搜索树及其递归实现
为什么要研究树结构？
树结构并不抽象，例如家谱，文件夹等等
优点： 高效
何为二叉树？
- 和链表一样，是动态数据结构，是天然递归结构(每个结点的左子树也是二叉树)，但是是非线性的
- 二叉树具有唯一根节点，每个结点最多只能分两个叉，每个结点最多有两个孩子，每个结点最多有一个父亲
- 一个孩子都没有的结点称为叶子结点
- 二叉树不一定是满的，一个结点也是二叉树，空也是
二叉搜索树：
存储的元素必须有可比较性；如果存储学生，可以按照学号等进行比较。
递归二分搜索树：
package com.lt.datastructure.BST; public class BST<E extends Comparable<E>> { private class Node{ public E e; Node left,right; public Node(E e) { this.e = e; this.left = left; this.right = right; } } private Node root; private int size; public BST(){ root = null; size = 0; } public int size() { return size; } public boolean isEmpty(){ return size==0; } /* * 二分搜索树添加元素 * 小于根结点，添加到左边，大于则添加到右边，等于根节点，则不作任何改变， 二分搜索树不包含重复元素 * */ public void add(E e){ if(root == null){ root = new Node(e); size ++; }else{ add(root,e); } } //向以root为根的二分搜索树中插入元素E，递归算法 private Node 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{ add(node.right,e); } */ //递归的出口，找到子树为null,则必然添加,完成操作 if(node == null){ size++; return new Node(e); } if(e.compareTo(node.e)<0){ //如果左子树为null,则node.left = new Node(e);如果不为空，继续递归 node.left = add(node.left,e); } else if(e.compareTo(node.e)>0){ ////如果右子树为null,则node.right = new Node(e);如果不为空，继续递归 node.right = add(node.right,e); } //其他情况，比如元素相等，则返回传进来的根节点，不做操作 return node; } //查询二分搜索树中是否包含元素e public boolean contains(E e){ return contains(root,e); } //看以node为根的二分搜索树中是否含有元素e,递归实现 private boolean contains(Node node , E e){ if(node == null){ return false; } if(e.compareTo(node.e)==0){ return true; } else if(e.compareTo(node.e)<0){ return contains(node.left,e); }else{ return contains(node.right,e); } }
测试：