package com.data.java.towtree;
import java.io.IOException;
/**
* 二叉树
* @Title: uminton
*/
class Node{
public int iData; //数据用作关键值
public double dData; //其他数据
public Node leftChild; //左子节点
public Node rightChild; //右子节点
public Node() {
}
public Node(int iData, double dData) {
this.iData = iData;
this.dData = dData;
}
public void displayNode(){
System.out.print("{");
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("} ");
}
}
public class Tree {
private Node root; //根节点
public Node getRoot() {
return root;
}
/**
* 查找一个数据
* @param key
* @return
*/
public Node find(int key){
Node current = root; //把跟节点设置为当前节点
while (current.iData != key){ //循环查找
if(key < current.iData){ //如果小于就去当前树的左边子节点
current = current.leftChild; //把子节点赋给当前节点
}else { //如果大于就去当前树的右边子节点
current = current.rightChild;//把子节点赋给当前节点
}
if(current == null){ //到达序列的末端没有找到节点，表明他不存在，返回空
return current;
}
}
return current; //循环条件相等，循环结束，找到结果。
}
/**
* 添加一个数据
* @param id
* @param dd
*/
public void insert(int id, double dd) {
Node newNode = new Node(id, dd); //先创建一个新节点
if(root == null){ //如果跟节点为空，表示树，没有数据，直接赋值给根节点
root = newNode;
}else {
Node current = root; //根节点赋值给当前节点，用于查找
Node parent; //父节点，用来存储遇到的最后一个不是null的节点，因为curent在查找的过程中会变成null，
// 才能发现发现查找过得上一个节点没有子节点
while (true){ //循环查找
parent = current; //用来存储遇到的最后一个不是null的节点
if (id < current.iData){ //如果小于就去当前树的左边子节点
current = current.leftChild;
if(current == null){ //到达序列的末端没有找到节点，表明他不存在
parent.leftChild = newNode; //把新的节点赋值给父节点的左子节点
return; //直接返回，结束循环
}
}else {
current = current.rightChild;
if(current == null){
parent.rightChild = newNode;
return;
}
}
}
}
}
/**
* 删除一个数据
* @param key
* @return
*
* 删除节点要考虑的三种情况
* 1，该节点是叶节点
* 2，该节点有一个子节点
* 3，该节点有二个子节点
*/
public boolean delete(int key){
Node current = root;
Node parent = root;
boolean isLeftChild = true; //记录是左节点还是右节点
while(current.iData != key){ //循环为了找到要删除的节点，循环条件如果相等就是找到了，退出循环
parent = current; //保存要删除的父节点
if(key < current.iData){
isLeftChild = true;
current = current.leftChild;
}else {
isLeftChild = false;
current = current.rightChild;
}
if(current == null){ //查找到末端，都没有找到，返回false
return false;
}
}
/**************************情况1开始*********************************/
if(current.leftChild == null && current.rightChild == null) { //判断是否没有子节点，也就是该节点是叶节点
if (current == root) { //如果是根节点，直接赋值为null
root = null;
} else if (isLeftChild) { //判断是否是左节点
parent.leftChild = null; //用上面保存的父节点找子节点，直接赋值为null
} else {
parent.rightChild = null;
}
/**************************情况1结束*********************************/
/**************************情况2开始*********************************/
}else if (current.rightChild == null){ //判断左边等null或右边等于null
if(current == root){ //如果是根节点，直接赋值为null
root = current.leftChild;
}else if (isLeftChild){ //判断是否是左节点
parent.leftChild = current.leftChild;//用上面保存的父节点找子节点，直接赋值为null
}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;
}
/**************************情况2结束*********************************/
/**************************情况3开始*********************************/
}else { //上面都不成立，表明该节点有两个子节点。
Node successor = getSuccessor(current); //取得后继者
if(current == root){ //如果是根节点，直接赋值为后继者
root = successor;
}else if (isLeftChild){ //判断是否是左节点
parent.leftChild = successor; //用上面保存的父节点找子节点，直接赋值为后继者
}else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
/**************************情况3结束*********************************/
return true;
}
/**
* 中序遍历树
* @param localRoot
*/
public void inOrder(Node localRoot){
if(localRoot != null){
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData);
inOrder(localRoot.rightChild);
}
}
/**
* 查找最小值
* @return
*/
public Node minNumber(){
Node current = root;
Node last = null;
while (current != null){
last = current;
current = current.leftChild;
}
return last;
}
/**
* 获取删除节点的后继者
* @param delNode
* @return
* 算法：程序找到要删除的节点的右子节点，（它的关键字值一定比要删除的节点的值大）然后转到右子节点的左子节点（若果有的话）
* 然后到这个左子节点的左子节点，以此类推，这个路径的最后一个左子节点就是要删除节点的后继者
* 若果删除节点右子节点没有左子节点，它就是后继者
*/
private Node getSuccessor(Node delNode) {
Node successorParent = delNode;
Node successor = 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;
}
}
class TreeApp{
public static void main(String[] args) throws IOException {
Tree treTree = new Tree();
treTree.insert(38,1.5);
treTree.insert(65,1.5);
treTree.insert(40,1.5);
treTree.insert(50,1.5);
treTree.insert(55,1.5);
treTree.insert(30,1.5);
treTree.insert(90,1.5);
treTree.insert(25,1.6);
treTree.insert(70,1.7);
treTree.insert(20,1.7);
treTree.insert(80,1.7);
treTree.delete(65);
}
}
最后删除有点复杂，没怎么搞懂见谅。