把写代码过程中经常用的内容记录起来，下边代码是关于java二叉树查找、遍历、添加与删除的代码。
package com.structures.tree;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Stack;
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;
}
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 {
add(number, child, child.left, 0);
else
add(number, child, child.right, 1);
}
}
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;
}
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;
}
}
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);
}
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);
}
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) {
tree.left = remove(number, tree.left);
} else if (number > tree.data) {
tree.right = remove(number, tree.right);
} else if (tree.left != null && tree.right != null) {
delete = findMin(tree.right);
tree.setData(delete.data);
tree.setRight(remove(tree.data, tree.right));
delete = null;
} else {
delete = tree;
if (delete.left == null) {
tree = tree.right;
} else if (delete.right == null) {
tree = tree.left;
}
delete = null;
}
return tree;
}
public void preorder() {
System.out.print(data + " ");
if (left != null)
left.preorder();
if (right != null)
right.preorder();
}
public void inorder() {
if (left != null)
left.inorder();
System.out.print(data + " ");
if (right != null)
right.inorder();
}
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.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);
}
}
网友评论