import java.util.NoSuchElementException;
import java.util.Stack;
public class BinarySearchTree {
private Node root;
public void put(int item) {
if (root == null) {
root = new Node(item);
} else {
Node node = new Node(item);
Node parent = searchNoChildNode(item);
node.parent = parent;
if (item > parent.item) {
parent.rightChild = node;
} else if (item < parent.item) {
parent.leftChild = node;
}
// System.out.println("node=" + node);
// System.out.println("parent=" + parent);
}
}
/**
* 寻找适合的没有子节点的node
*
* @param item
* @return
*/
private Node searchNoChildNode(int item) {
Node node = root;
while (node != null) {
if (item < node.item) {
if (node.leftChild == null)
return node;
node = node.leftChild;
} else {
if (node.rightChild == null)
return node;
node = node.rightChild;
}
}
return node;
}
/**
* 中序：左中右 思路：压入当前节点，判断左孩子是否为空， 若为空，则弹出该节点，并打印，并以右孩子为当前节点，重复操作；
* 若不为空，则以左孩子做当前节点，重复操作
*
* 重复操作的意思是呢。。。就是压入堆栈，判断左孩子是否为空。。。
*/
public void middleOrder() {
Stack<Node> stack = new Stack<>();
Node node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.leftChild;
} else {
node = stack.pop();
System.out.print(node.item + " ");
node = node.rightChild;
}
}
System.out.println();
}
/**
* 移除一个数
*
* @param data
*/
public void remove(int item) {
Node node = searchNode(item);
System.out.println("删除节点：" + node);
if (node == null)
throw new NoSuchElementException();// 没有当前节点
Node parent = node.parent;
if (node.leftChild == null && node.rightChild == null) {// 没有子节点，直接删除就行了
if (parent == null) {// 没有父节点,说明是root节点
root = null;// 直接将root置空
} else {
node.parent = null;
if (parent.leftChild == node) {// 如果是父节点的左子节点，则设置父节点左子节点为空
parent.leftChild = null;
} else {// 反之，设置右子节点为空
parent.rightChild = null;
}
}
} else if (node.leftChild != null && node.rightChild == null) {// 有左子节点，没有右子节点
if (parent == null) {// root节点
root = node.leftChild;// 将root节点设置为其左子节点
} else {
node.parent = null;
if (parent.leftChild == node) {// 如果是父节点的左子节点，则把自己的左子节点设置给父左子节点
parent.leftChild = node.leftChild;
} else {// 反之，设置给父右子节点
parent.rightChild = node.leftChild;
}
node.leftChild.parent = parent;
}
} else if (node.leftChild == null && node.rightChild != null) {// 没有左子节点，有右子节点
if (parent == null) {
root = node.rightChild;
} else {
node.parent = null;
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
node.rightChild.parent = parent;
}
} else if (node.leftChild != null && node.rightChild != null) {// 有左子节点，也有右子节点
Node mostLeftNode = searchMostLeftNode(node.rightChild);// 搜索右子节点的最左子节点
Node mostLeftNodeP = mostLeftNode.parent;// 最左子节点的父节点
if (parent == null) {// 是root节点
root = mostLeftNode;// 将root节点设置为右子节点的最左子节点
} else {
// 最左子节点替代删除节点
if (parent.leftChild == node) {
parent.leftChild = mostLeftNode;
} else {
parent.rightChild = mostLeftNode;
}
}
// 先处理最左子节点目前的父节点和右子节点的赋值
// 最左子节点的父节点的左子节点，设置为最左子节点的右子节点，因为最左子节点没有左子节点
mostLeftNodeP.leftChild = mostLeftNode.rightChild;
if (mostLeftNode.rightChild != null) {
mostLeftNode.rightChild.parent = mostLeftNodeP;
}
// 再给最左子节点的父节点和左右子节点赋上新值
// 最左子节点替代了了删除节点，所以其父节点，孩子节点，都要等于删除节点的父节点，孩子节点
mostLeftNode.parent = parent;
mostLeftNode.leftChild = node.leftChild;
mostLeftNode.rightChild = node.rightChild;
// 删除节点的两个子节点的父节点，也要相应的设置为最左子节点
node.leftChild.parent = mostLeftNode;
node.rightChild.parent = mostLeftNode;
}
}
/**
* 搜索该节点的最左子节点
*
* @param node
* @return
*/
private Node searchMostLeftNode(Node node) {
Node leftNode = node;
while (leftNode != null) {
if (leftNode.leftChild == null)
return leftNode;
leftNode = leftNode.leftChild;
}
return leftNode;
}
/**
* 查询指定节点
*
* @param item
* @return
*/
public Node searchNode(int item) {
Node node = root;
while (node != null) {
if (item > node.item) {
node = node.rightChild;
} else if (item < node.item) {
node = node.leftChild;
} else {
return node;
}
}
return null;
}
private class Node {
private int item;
private Node parent;
private Node leftChild;
private Node rightChild;
public Node(int item) {
this.item = item;
}
@Override
public String toString() {
String p = null;
if (parent != null) {
p = String.valueOf(parent.item);
}
String l = null;
if (leftChild != null) {
l = String.valueOf(leftChild.item);
}
String r = null;
if (rightChild != null) {
r = String.valueOf(rightChild.item);
}
return "Node [item=" + item + ", parent=" + p + ", leftChild=" + l + ", rightChild=" + r + "]";
}
}
public static void main(String[] args) {
int[] items = { 20, 31, 10, 12, 54, 23, 11, 5, 100, 43, 26 };
BinarySearchTree tree = new BinarySearchTree();
for (int i : items) {
tree.put(i);
}
System.out.println("初始节点");
tree.middleOrder();
Node n = tree.searchNode(54);
System.out.println("查找节点：" + n);
tree.remove(20);
tree.middleOrder();
tree.remove(5);
tree.middleOrder();
tree.remove(100);
tree.middleOrder();
tree.remove(43);
tree.middleOrder();
tree.remove(23);
tree.middleOrder();
System.out.println("插入节点:25");
tree.put(25);
tree.middleOrder();
}
}
网友评论