排序二叉树 JAVA 版实现
*/
private TreeNode<E> add0(TreeNode<E> root, E e) {
final TreeNode<E> curNode = root;
int cmp = compare(e, curNode.value);
if(cmp < 0 ) { //表示待插入的节点值，比当前节点值小
if(curNode.left == null) {
//创建当前节点的左节点
TreeNode<E> newNode = new TreeNode<E>(e, curNode);
curNode.left = newNode;
return newNode;
} else {
return add0(curNode.left, e);//遍历左子树
}
} else { // 大于等于 0，右子树
if(curNode.right == null ) {
//创建当前节点的右节点
TreeNode<E> newNode = new TreeNode<E>(e, curNode);
curNode.right = newNode;
return newNode;
} else {
return add0(curNode.right, e);//遍历右子树
}
}
}
/**
比较两个元素的大小
@param e1
@param e2
@return
*/
@SuppressWarnings("unchecked")
private int compare(E e1, E e2) {
return comparator == null ? ((Comparable<E>) e1 ).compareTo(e2) : comparator.compare(e1, e2);
}
/**
删除元素
@param e
@return 如果返回 ture,表示删除成功,如果返回 false,表示删除失败，没有找到元素
*/
public boolean remove(E e) {
if( e == null ) return false;
TreeNode<E> cur = root;
int cmp;
while (cur != null ) {
if(e.equals(cur.value)) {
break;
}
cmp = compare(e, root.value);
if(cmp < 0 ) { //表示待删除的节点值，比当前节点值小
cur = cur.left;
} else {
cur = cur.right;
}
}
if(cur != null ) { //找到了元素，需要删除该元素
TreeNode<E> cLeft = cur.left;
TreeNode<E> cRight = cur.right;
if(cLeft != null ) { //如果被删除节点的左子树不为空，则将左子树放入当前节点的位置
remove0(cLeft, cur);
if(cLeft.right != null && cur.right != null) { //需要移动相应节点
TreeNode<E> wNode = cLeft.right;
cLeft.right = cur.right;
wNode.parent = null;
TreeNode<E> newNode = add0(cLeft, wNode.value);
newNode.left = wNode.left;
newNode.right = wNode.right;
wNode = null;
}
} else {
remove0(cRight, cur);
}
//将当前节点释放，，help GC
cur.value = null;
cur.right = null;
cur.left = null;
cur.parent = null;
cur = null;
return true;
}
return false;
}
private void remove0(TreeNode<E> newNode, TreeNode<E> cur) {
TreeNode<E> parent = cur.parent;
newNode.parent = parent;
if(cur.parent.left == cur) {
cur.parent.left = newNode;
} else {
cur.parent.right = newNode;
}
}
/**
中序遍历
*/
public void middleOrderTraversal() {
System.out.println("----------中序遍历开始---------\n");
if (root == null) {
System.out.print("二叉树");
System.out.println("----------中序遍历结束---------\n");
return;
}
middleOrderTraversal0(root);
System.out.println("\n----------中序遍历结束---------\n");
}
/**
中序遍历
*/
private void midd
leOrderTraversal0(TreeNode<E> root) {
if (root == null)
return;
final TreeNode<E> cur = root;
if (cur.left != null) {
middleOrderTraversal0(cur.left);
System.out.print(toObjectString(cur.value) + ",");
middleOrderTraversal0(cur.right);
} else if (cur.right != null) {
System.out.print(cur.value + ",");
middleOrderTraversal0(cur.right);
} else {
// 此时输出节点
System.out.print(cur.value + ",");
}
}
public TreeNode<E> getRoot() {
return root;
}
public void setRoot(TreeNode<E> root) {
this.root = root;
}
private String toObjectString(E value) {
return value == null ? "" : value.toString();
}
/**
二叉数
@author Administrator
@param <E>
*/
@SuppressWarnings("unused")
private final static class TreeNode<E> implements Serializable {
private static final long serialVersionUID = 6540618639489225256L;
public E value;
public TreeNode<E> left;
public TreeNode<E> right;
public TreeNode<E> parent;
public TreeNode(E value, TreeNode<E> parent) {
super();
this.value = value;
this.parent = parent;
}
public TreeNode(E value, TreeNode<E> left, TreeNode<E> right, TreeNode<E> parent) {
super();
this.value = value;
this.left = left;
this.right = right;
this.parent = parent;
}
@Override
public String toString() {
if(value != null)
return value.toString();
return super.toString();
}
}
/** *******************测试 start ***************************/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("测试开始");
// BinaryTree<Integer> t = new BinaryTree<Integer>();
// t.setRoot(t.initTree());
// t.middleOrderTraversal();
//先研究一下 Comparator o1 > o2 的排序逻辑
//testSort();
/* * 10
*/
// add 方法测试
BinaryTree<Integer> t = new BinaryTree<Integer>();
// t.add(new Integer(10));
// t.add(new Integer(18));
// t.add(new Integer(3));
// t.add(new Integer(2));
// t.add(new Integer(4));
// t.add(new Integer(8));
// t.add(new Integer(9));
// t.add(new Integer(9));
// t.add(new Integer(21));
// t.add(new Integer(13));
t.add(new Integer(10));
t.add(new Integer(18));
t.add(new Integer(3));
t.add(new Integer(9));
t.add(new Integer(8));
t.add(new Integer(2));
t.add(new Integer(21));
t.add(new Integer(4));
t.add(new Integer(9));
t.add(new Integer(13));
t.add(new Integer(11));
t.add(new Integer(15));
//查看数结构，中序遍历
t.middleOrderTraversal();
//测试删除
System.out.println("删除节点 18");
t.remove(new Integer(18));
System.err.println("删除节点 18 号的排序二叉树");
t.middleOrderTraversal();
System.out.println("测试结束");
}
/**
当用升序排序时，则 o1 > o2 时要返回大于 0 的数
*/
public static void testSort() {
List<Integer> a = new ArrayList<Integer>();
a.add(1);
a.add(8);
a.add(9);
a.add(3);
a.add(5);
Collections.sort(a, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.intValue() > o2.intValue() ? 1 : -1;
}
});
System.out.println(a);
}
/**
用来测试的，后续会完善 加入元素
@return
*/
@Deprecated
public TreeNode<Integer> initTree() {
TreeNode<Integer> _root = new TreeNode<Integer>(new Integer(10), null); // 根节点
还未添加个人签名 2021.11.08 加入
还未添加个人简介
评论