- 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);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/251220138240.html
来源: http://www.codesnippet.cn/detail/251220138240.html