java数据结构教程六-二叉搜索树

创建树的节点类public class TreeNode { T data; TreeNode left; TreeNode right; public TreeNode(T data) { this.data = data; left = right = null; }}

创建二叉搜索树的类BinarySearchTree，在这里使用了>，是为了能够进行比较public class BinarySearchTree> { TreeNode root; public BinarySearchTree() { this.root = null; } /** * 插入一个元素值； * @param data */ public void insert(T data){ root = insert(data, root); } protected TreeNode insert(T data,TreeNode node){ if(node == null) node = new TreeNode(data); else if(data.compareTo(node.data)<0){ node.left = insert(data,node.left); }else{ node.right = insert(data,node.right); } return node; } public void createTree(T[] datas){ for(int i=0;i node){ if(node == null) return; System.out.print(node.data+' '); preOrder(node.left); preOrder(node.right); } /** * findMin 递归解法 */ public T findMin(){ TreeNode node = findMin(root); return node.data; } protected TreeNode findMin(TreeNode node){ if(node.left==null) return node; return findMin(node.left); } /** * findMax 递归解，非递归解 */ public T findMax(){ TreeNode node = findMax(root); return node.data; } protected TreeNode findMax(TreeNode node){ if(node.right==null) return node; return findMax(node.right); } /** * removeMin */ protected TreeNode removeMin(TreeNode node){ if(node==null) throw new RuntimeException('空树'); else if(node.left!=null){ node.left = removeMin(node.left); return node; }else{ return node.right; } } protected TreeNode remove(T data,TreeNode node){ if(data.compareTo(node.data)<0){ node.left = remove(data, node.left); }else if(data.compareTo(node.data)<0){ node.right = remove(data, node.right); }else if(node.left!=null&&node.right!=null){ //有两个孩子，删除此节点比较麻烦 node.data = findMin(node).data; node.right = removeMin(node.right); }else node = (node.left!=null)?node.left:node.right; return node; }}

编写测试用例public class BinarySearchTreeTest { @Test public void testInsert() { BinarySearchTree binarySearchTree = new BinarySearchTree<>(); Integer[] datas = {2,8,7,4,9,9,3,1,6,7,5}; binarySearchTree.createTree(datas); binarySearchTree.preOrder(); } @Test public void testFindMin() { BinarySearchTree binarySearchTree = new BinarySearchTree<>(); Integer[] datas = {2,8,7,4,9,3,1,6,7,5}; binarySearchTree.createTree(datas); System.out.println('最小值'+binarySearchTree.findMin()); } @Test public void testFindMax() { BinarySearchTree binarySearchTree = new BinarySearchTree<>(); Integer[] datas = {2,8,7,4,9,9,3,1,6,7,5}; binarySearchTree.createTree(datas); System.out.println('最大值'+binarySearchTree.findMax()); }}