删除二叉树结点
删除结点是二叉树操作中最复杂的。在删除之前首先要查找要删除的结点。找到结点后，这个要删除的结点可能会有三种情况需要考虑。
1. 该节点是叶子结点，没有子结点
要删除叶子结点，只需要改变该节点的父结点的引用值，将指向该节点的引用值设置为null就可以了。
2. 该节点有一个子结点
改变父结点的引用，将其直接指向要删除结点的子结点。
3. 该节点有两个子结点
要删除有两个子结点的结点，就需要使用它的中序后继来替代该节点。
二叉树结点
/*
* 二叉树结点
*/
public class Node {
//数据项
public long data;
public String sData;
//左子结点
public Node leftChild;
//右子结点
public Node rightChild;
/*
* 构造函数
*/
public Node(long data,String sData){
this.data=data;
this.sData=sData;
}
}
二叉树类
* 二叉树类
*/
/*
* 为什么要使用树
*
* 有序数组插入数据项和删除数据项太慢
* 链表查找数据太慢
* 在树中能非常快速的查找数据项、删除数据项和插入数据项
*/
public class Tree {
//根结点
public Node root;
/*
* 插入结点
*/
public void insert(long value,String sValue){
//封装结点
Node newNode=new Node(value,sValue);
//引用当前结点
Node current=root;
//引用父结点
Node parent;
//如果root为null，也就是第一插入的时候
if(root==null){
root=newNode;
return;
}else{
while(true){
//父结点指向当前结点
parent=current;
//如果当前指向的结点数据比插入的要大，则向左走
if(current.data>value){
current=current.leftChild;
if(current==null){
parent.leftChild=newNode;
return;
}
}else{
current=current.rightChild;
if(current==null){
parent.rightChild=newNode;
return;
}
}
}
}
}
/*
* 查找结点
*/
public Node find(long value){
//引用当前结点，从跟结点开始
Node current=root;
//循环，只要查找值不等于当前结点的数据项
while(current.data!=value){
//进行比较，比较查找值和当前结点的大小
if(current.data>value){
current=current.leftChild;
}else{
current=current.rightChild;
}
//如果找不到
if(current==null){
return null;
}
}
return current;
}
/*
* 删除结点
*
* 1 该节点是叶子节点，没有子节点
* 要删除叶结点，只需要改变该节点的父结点的引用值，将指向该节点的引用设置为null就可以了
*
* 2 该节点有一个子节点
* 改变父结点的引用，将其直接指向要删除结点的子节点
*
* 3 该节点有两个子节点
* 要删除有两个子节点的结点，就需要使用它的中序后继来代替该节点
*
*/
public boolean delete(long value){
//引用当前结点，从根节点开始
Node current=root;
//引用当前结点的父结点
Node parent=root;
//是否为左结点
boolean isLeftChild=true;
while(current.data!=value){
parent=current;
//进行比较，比较查找值和当前结点的大小
if(current.data>value){
current=current.leftChild;
isLeftChild=true;
}else{
current=current.rightChild;
isLeftChild=false;
}
//如果找不到
if(current==null){
return false;
}
}
//删除叶子结点，也即该节点没有子结点
if(current.leftChild==null&¤t.rightChild==null){
if(current==root){
root=null;
}
//如果它是父结点的左子结点
else if(isLeftChild){
parent.leftChild=null;
}else{
parent.rightChild=null;
}
}else if(current.rightChild==null){
if(current==root){
root=current.leftChild;
}
else if(isLeftChild){
parent.leftChild=current.leftChild;
}else{
parent.rightChild=current.leftChild;
}
}else if(current.leftChild==null){
if(current==root){
root=current.rightChild;
}
else if(isLeftChild){
parent.leftChild=current.rightChild;
}else{
parent.rightChild=current.rightChild;
}
}else{
Node successor=getSuccessor(current);
if(current==root){
root=successor;
}else if(isLeftChild){
parent.leftChild=successor;
}else{
parent.rightChild=successor;
}
successor.leftChild=current.leftChild;
}
return true;
}
public Node getSuccessor(Node delNode){
Node successor=delNode;
Node successorParent=delNode;
Node current=delNode.rightChild;
while(current!=null){
successorParent=successor;
successor=current;
current=current.leftChild;
}
if(successor!=delNode.rightChild){
successorParent.leftChild=successor.rightChild;
successor.rightChild=delNode.rightChild;
}
return successor;
}
/*
* 前序遍历
*/
public void frontOrder(Node localNode){
if(localNode!=null){
//访问根结点
System.out.println(localNode.data+","+localNode.sData);
//前序遍历左子树
frontOrder(localNode.leftChild);
//前序遍历右子树
frontOrder(localNode.rightChild);
}
}
/*
* 中序遍历
*/
public void inOrder(Node localNode){
if(localNode!=null){
//中序遍历左子树
inOrder(localNode.leftChild);
//访问根结点
System.out.println(localNode.data+","+localNode.sData);
//中序遍历右子树
inOrder(localNode.rightChild);
}
}
/*
* 后序遍历
*/
public void afterOrder(Node localNode){
if(localNode!=null){
//后序遍历左子树
afterOrder(localNode.leftChild);
//后序遍历右子树
afterOrder(localNode.rightChild);
//访问根结点
System.out.println(localNode.data+","+localNode.sData);
}
}
}
测试：
public class TestTree {
public static void main(String[] args) {
// TODO Auto-generated method stub
Tree tree=new Tree();
tree.insert(10,"James");
tree.insert(20,"Yao");
tree.insert(15,"Kobi");
tree.insert(3,"Mac");
tree.insert(4,"Zhangsan");
tree.insert(90, "Lisi");
// System.out.println(tree.root.data);
// System.out.println(tree.root.rightChild.data);
// System.out.println(tree.root.rightChild.leftChild.data);
// System.out.println(tree.root.leftChild.data);
//
// Node node =tree.find(3);
// System.out.println(node.data+","+node.sData);
//前、中、后序遍历
// tree.frontOrder(tree.root);
// tree.inOrder(tree.root);
// tree.afterOrder(tree.root);
//删除叶子结点
tree.delete(10);
tree.inOrder(tree.root);
}
}