四、具体代码实现
在进行相关操作之前, 先定义一个支持泛型的节点类, 用于存储二分搜索树每个节点的信息, 这个类作为二分搜索树的一个内部类, 二分搜索树的类声明以及Node节点类声明如下:
public class BST<E extends Comparable<E>> { private class Node{ public E e; public Node left,right; public Node(E e){ this.e = e; left = null; right = null; } } //节点 private Node root; // 树容量 private int size; public BST(){ root = null; size = 0; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } }
4.1 添加元素
二分搜索树添加元素的非递归写法，和链表很像，由于二分搜索树本身的递归特性, 所以可以很方便的使用递归实现向二分搜索树中添加元素,
代码：
//向二分搜索树添加新的元素e public void add(E e){ root = add(root,e); } //向以Node为根的二分搜索树中插入元素 E，递归算法 //返回插入新节点后二分搜索树的根 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; }
4.2 查找元素
由于二分搜索树没有下标, 所以针对二分搜索树的查找操作, 我们需要定义一个 contains() 方法, 查看二分搜索树是否包含某个元素, 返回一个布尔型变量
代码：
//看二分是搜索树中是否包含元素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 //e.compareTo(node.e) > 0 return contains(node.right,e); }
4.3 遍历操作
一、 什么是遍历操作
- 遍历操作就是把所有的节点都访问一遍
- 访问的原因和业务相关
- 遍历分类
前序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之前, 遍历顺序 : 当前节点->左孩子->右孩子
中序遍历 : 对当前节点的遍历在对左右孩子节点的遍历中间, 遍历顺序 : 左孩子->当前节点->右孩子
后序遍历 : 对当前节点的遍历在对左右孩子节点的遍历之后, 遍历顺序 : 左孩子->右孩子->当前节点
二、 前序遍历
//二分搜索树前序遍历 public void preOrder(){ preOrder(root); } //前序遍历以Node为根的二分搜索树，递归算法 private void preOrder(Node node){ if(node == null) return; System.out.println(node.e); preOrder(node.left); preOrder(node.right); } public void preOrderNR(){ Stack<Node> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node cur = stack.pop(); System.out.println(cur.e); if(cur.right != null) stack.push(cur.right); if(cur.left != null) stack.push(cur.left); } }
三、 中序遍历
//二分搜索树的中序遍历 public void inOrder(){ inOrder(root); } //中序遍历以Node为根的二分搜索树，递归算法 private void inOrder(Node node){ if(node ==null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); }
四、 后序遍历
//二分搜索树的后序遍历 public void postOrder(){ inOrder(root); } public void levelOrder(){ Queue<Node> q = new LinkedList<Node>(); q.add(root); while (!q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left != null) q.add(cur.left); if(cur.right != null) q.add(cur.right); } } //后序遍历以Node为根的二分搜索树，递归算法 private void postOrder(Node node){ if(node ==null) return; inOrder(node.left); inOrder(node.right); System.out.println(node.e); }
五、 理解前中后
