每个节点中应该有两个属性:左节点、右节点。
package structure;
public class Tree {
private Node root;
/**
* 节点
*/
class Node{
public long value;
public Node leftChild;
public Node rightChild;
public Node(long value){
this.value = value;
}
}
/**
* 插入节点
* @param value
*/
public void insert(long value){
Node node = new Node(value);
if(root == null){
root = node;
return;
}
// 当前节点引用。插入思路:即和当前节点比较,大于当前节点的值走右边;小于当前节点的值走走边;改变current指向
Node current = root;
do{
if(current.value > value){
if(current.leftChild == null){
current.leftChild = node;
return;
}
current = current.leftChild;
}else{
if(current.rightChild == null){
current.rightChild = node;
return;
}
current = current.rightChild;
}
}while (true);
}
/**
* 删除节点
* @param value
*/
public Node remove(long value){
Node current = root;
// 要删除节点的父节点
Node parent = current;
boolean isLeft = true;
// 查到到需要删除的节点
while(current.value != value){
parent = current;
// 找不到返回 false
if(current == null){
return null;
}
if(current.value > value){
current = current.leftChild;
isLeft = true;
}else{
current = current.rightChild;
isLeft = false;
}
}
// 1、如果删除的节点是叶子节点
if(current.leftChild == null && current.rightChild == null){
if(current == root){
root = null;
}
if(isLeft){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
// 引用类型,直接将它置为 null 就可以了
current = null;
}
// 2、左子树不为null,右子树为null
else if(current.rightChild == null){
if(current == root){
root = current.leftChild;
}
if(isLeft){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
}
// 3、左子树为null,右子树不为null
else if(current.leftChild == null){
if(current == root){
root = current.rightChild;
}
if(isLeft){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
}
// 4、左子树和右子树都不为空,需要查找中继后续,即右子树中最小的那个节点
else {
Node successor = getSuccessor(current);
if(current == root){
root = successor;
}
if(isLeft){
parent.leftChild = successor;
}else{
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return current;
}
/**
* 获取中继后序节点
* @param deleteNode
* @return
*/
private Node getSuccessor(Node deleteNode){
Node successor = deleteNode;
// 中继后序节点的父节点
Node successorParent = successor;
Node current = deleteNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
// 当右子树只有一个节点的时候,此时 successor == deleteNode.rightChild,不需要执行下面的逻辑
if(successor != deleteNode.rightChild){
// 中继后续节点有可能有rightChild, 但不可能有leftChild
successorParent.leftChild = successor.rightChild;
successor.rightChild = deleteNode.rightChild;
}
return successor;
}
/**
* 查找节点
* @param value
* @return
*/
public Node find(long value){
Node current = root;
while (current.value != value){
if(current == null){
return null;
}
if(current.value > value ){
current = current.leftChild;
}else{
current = current.rightChild;
}
}
return current;
}
/**
* 前序遍历:根 --》 左 --》 右
* @param localNode
*/
public void frontOrder(Node localNode){
if(localNode != null){
// 访问根节点
System.out.println(localNode.value);
// 遍历左子树
frontOrder(localNode.leftChild);
// 遍历右子树
frontOrder(localNode.rightChild);
}
}
/**
* 中序遍历:左 --》 根 --》 右
* @param localNode
*/
public void inOrder(Node localNode){
if(localNode != null){
// 遍历左子树
inOrder(localNode.leftChild);
// 访问根节点
System.out.println(localNode.value);
// 遍历右子树
inOrder(localNode.rightChild);
}
}
/**
* 中序遍历:左 --》 右 --》 根
* @param localNode
*/
public void afterOrder(Node localNode){
if(localNode != null){
// 遍历左子树
afterOrder(localNode.leftChild);
// 遍历右子树
afterOrder(localNode.rightChild);
// 访问根节点
System.out.println(localNode.value);
}
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(2);
tree.insert(1);
tree.insert(7);
tree.insert(5);
tree.insert(4);
tree.insert(6);
tree.insert(10);
tree.insert(8);
tree.insert(11);
tree.insert(9);
// 查找
Node node = tree.find(6);
System.out.println("----------------------------------查找节点------------------------------------");
System.out.println(node.value);
// 前序遍历
System.out.println("----------------------------------前序遍历------------------------------------");
tree.frontOrder(tree.root);
// 中序遍历
System.out.println("----------------------------------中序遍历------------------------------------");
tree.inOrder(tree.root);
// 后序遍历
System.out.println("----------------------------------后序遍历------------------------------------");
tree.afterOrder(tree.root);
// 删除节点
System.out.println("----------------------------------删除节点------------------------------------");
tree.remove(7);
tree.inOrder(tree.root);
}
}