java二叉树查找、遍历、添加与删除
package com.structures.tree; import java.util.ArrayList; import java.util.NoSuchElementException; import java.util.Stack; /* * Binary Search Tree */ public class Searchtree { public Integer data; public Searchtree left; public Searchtree right; public void setData(Integer data) { this.data = data; } public Searchtree(Integer number) { this.data = number; } public void setLeft(Searchtree left) { this.left = left; } public void setRight(Searchtree right) { this.right = right; } // add public void add(int number) { if (number <= this.data) add(number, this, this.left, 0); else add(number, this, this.right, 1); } private void add(int number, Searchtree father, Searchtree child, int tag) { if (child == null) { child = new Searchtree(number); if (tag == 0) father.setLeft(child); else father.setRight(child); } else { // attention: here must be child if (number <= child.data)// add to left add(number, child, child.left, 0); else // add to right add(number, child, child.right, 1); } } // find public Searchtree find(int number) { if (number < data) { return find(number, this); } else if (number > data) { return find(number, this); } else { return find(number, this); } } private Searchtree find(int number, Searchtree tree) { if (tree == null) throw new NoSuchElementException( "no such element in the binary search tree"); if (number < tree.data) { return find(number, tree.left.left); } else if (number > tree.data) { return find(number, tree.right); } else return tree; } // findPrevious private ArrayList<Searchtree> trees = new ArrayList<Searchtree>(); private Searchtree findPrevious(int number, Searchtree tree) { if (tree == null) throw new NoSuchElementException( "no such element in the binary search tree"); trees.add(tree); if (number < tree.data) { return findPrevious(number, tree.left); } else if (number > tree.data) { return findPrevious(number, tree.right); } else { Searchtree pre = trees.get(trees.size() - 2); trees = null; return pre; } } // min public Searchtree findMin(Searchtree tree) { if (tree == null) throw new NoSuchElementException( "no such element in the binary search tree"); else if (tree.left == null) return tree; else return findMin(tree.left); } // max public Searchtree findMax(Searchtree tree) { if (tree == null) throw new NoSuchElementException( "no such element in the binary search tree"); else if (tree.right == null) return tree; else return findMax(tree.right); } public Searchtree remove(int number) { return remove(number, this); } /*remove * 是最困难的,请大家参考一下,递归有点晕。大家阅读书理解吧。 * 参考代码:《数据结构与算法分析》-C语言描述 英文版 * 第102-103页 * ISBN: 9787115139849 * detail:http://book.douban.com/subject/1444648/ */ public Searchtree remove(int number, Searchtree tree) { Searchtree delete = null; if (tree == null) throw new IndexOutOfBoundsException("tree size is 0"); else if (number < tree.data) { // go left tree.left = remove(number, tree.left); } else if (number > tree.data) { // go right tree.right = remove(number, tree.right); // found element to be remove } else if (tree.left != null && tree.right != null) { // two children // replace with the smallest in right tree delete = findMin(tree.right); tree.setData(delete.data); tree.setRight(remove(tree.data, tree.right)); delete = null; } else { // one or zero child delete = tree; if (delete.left == null) { tree = tree.right; } else if (delete.right == null) { tree = tree.left; } delete = null; } return tree; } // 先序遍历 preorder traversal public void preorder() { System.out.print(data + " "); if (left != null) left.preorder(); if (right != null) right.preorder(); } // 中序遍历 inorder traversal public void inorder() { if (left != null) left.inorder(); System.out.print(data + " "); if (right != null) right.inorder(); } // 后序遍历 postorder traversal public void postorder() { if (left != null) left.postorder(); if (right != null) right.postorder(); System.out.print(data + " "); } public int getDepth(Searchtree root) { int depth; if (root == null) return 0; else { depth = 1 + Math.max(getDepth(root.left), getDepth(root.right)); return depth; } } public static void main(String[] args) { Searchtree tree = new Searchtree(5); tree.add(3); tree.add(7); tree.add(2); tree.add(4); tree.add(6); tree.add(8); tree.add(1); tree.add(1); tree.remove(1); // tree.remove(2, tree); //tree.remove(tree.data); tree.preorder(); System.out.println(); tree.inorder(); System.out.println(); System.out.println(tree.getDepth(tree)); System.out.println(tree.find(7).data); System.out.println(tree.findPrevious(8, tree).data); } }