image
import javax.swing.tree.TreeNode;
import java.util.NoSuchElementException;
/**
* 二分查找樹
*/
public class SearchBinaryTree<T extends Comparable> {
TreeNode root;//根結(jié)點(diǎn)
public SearchBinaryTree() {
}
/**
* 添加一個(gè)結(jié)點(diǎn)
* <p>
* 首先通過比較大小找到需要添加的結(jié)點(diǎn)的父節(jié)點(diǎn)parent,
* 然后根據(jù)結(jié)點(diǎn)值與parent值大小,將該結(jié)點(diǎn)添加到parent的leftChild或者rightChild
*
* @param data 輸入要添加的值
* @return 返回添加的結(jié)點(diǎn)本身
*/
public TreeNode put(T data) {
if (root == null) {
TreeNode node = new TreeNode(data);
root = node;
return node;
} else {
TreeNode parent = null;
TreeNode targetNode = root;
while (targetNode != null) {
parent = targetNode;
if (data.compareTo(targetNode.data) > 0) {
targetNode = targetNode.rightChild;
} else if (data.compareTo(targetNode.data) < 0) {
targetNode = targetNode.leftChild;
} else {
//SearchBinaryTree contains this data,do not need to put
return targetNode;
}
}
TreeNode node = new TreeNode(data);
node.parent = parent;
if (data.compareTo(parent.data) > 0) {
parent.rightChild = node;
} else {
parent.leftChild = node;
}
return node;
}
}
/**
* 查詢樹中對應(yīng)的結(jié)點(diǎn)
* <p>
* data與根結(jié)點(diǎn)比較大小,比根結(jié)點(diǎn)大說明在根節(jié)點(diǎn)的右邊,繼續(xù)data與根節(jié)點(diǎn)的rightChild比大小,以此類推,直到找到與data相等的
* 比根節(jié)點(diǎn)小在根節(jié)點(diǎn)的左邊,繼續(xù)data與根節(jié)點(diǎn)的leftChild比大小,以此類推,直到找到與data相等的
* 與根結(jié)點(diǎn)相等則返回根結(jié)點(diǎn)
*
* @param data 輸入的值
* @return
*/
public TreeNode shearchNode(T data) {
TreeNode node = root;
while (node != null) {
if (data.compareTo(node.data) == 0) {
return node;
} else if (data.compareTo(node.data) > 0) {
node = node.rightChild;
} else {
node = node.leftChild;
}
}
return null;
}
/**
* 刪除結(jié)點(diǎn)
*
* @param node 要?jiǎng)h除的結(jié)點(diǎn)
* @return
*/
public TreeNode delete(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
TreeNode parent = node.parent;
//1.刪除葉子結(jié)點(diǎn)
if (node.leftChild == null && node.rightChild == null) {
//只有一個(gè)結(jié)點(diǎn)
if (parent == null) {
root = null;
} else {
if (parent.leftChild == node) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
node.parent = null;
}
} else if (node.leftChild != null && node.rightChild == null) {
//只有左孩子
/**
* 刪除根結(jié)點(diǎn)
*/
if (parent == null) {
node.leftChild.parent = null;
node.leftChild = root;
} else {
//node在parent左邊
if (parent.leftChild == node) {
node.leftChild.parent = parent;
parent.leftChild = node.leftChild;
} else {
//node在parent右邊
node.leftChild.parent = parent;
parent.rightChild = node.leftChild;
}
node.parent = null;
}
} else if (node.rightChild != null && node.leftChild == null) {
//只有右孩子
/**
* 刪除根結(jié)點(diǎn)
*/
if (parent == null) {
node.rightChild.parent = null;
root = node.rightChild;
} else {
//node在parent右邊
if (parent.rightChild == node) {
node.rightChild.parent = parent;
parent.rightChild = node.rightChild;
} else {
//node在parent左邊
node.rightChild.parent = parent;
parent.leftChild = node.rightChild;
}
node.parent = null;
}
} else {
//有左右兩個(gè)孩子
/**
* node的右子樹的左子樹為空,直接補(bǔ)上右子樹
*/
if (node.rightChild.leftChild == null) {
node.rightChild.leftChild = node.leftChild;
if (parent == null) {
root = node.leftChild.rightChild;
} else {
if (parent.leftChild == node) {
parent.leftChild = node.leftChild.rightChild;
} else {
parent.rightChild = node.leftChild.rightChild;
}
}
} else {
/**
* 否則就要補(bǔ)上右子樹的左子樹上最小的一個(gè)
*/
TreeNode leftNode = getMinLeftChild(node.rightChild);
TreeNode leftP = leftNode.parent;
//1.leftNode的左子樹賦值為node.leftChild
leftNode.leftChild = node.leftChild;
//2.leftP.leftChild賦值為leftNode.rightChild
leftP.leftChild = leftNode.rightChild;
//3.leftNode.rightChild = node.rightChild
leftNode.rightChild = node.rightChild;
//4.leftNode補(bǔ)上去
if (parent == null) {
root = leftNode;
} else {
if (parent.leftChild == node) {
parent.leftChild = leftNode;
} else {
parent.rightChild = leftNode;
}
node.parent = null;
}
}
}
}
return null;
}
/**
* 獲取最小左孩子
*
* @param root 根結(jié)點(diǎn)
* @return
*/
private TreeNode getMinLeftChild(TreeNode root) {
if (root == null) {
return null;
}
while (root.leftChild != null) {
root = root.leftChild;
}
return root;
}
/**
* 節(jié)點(diǎn)類
*/
public static class TreeNode<T extends Comparable> {
T data;
TreeNode parent;
TreeNode leftChild;
TreeNode rightChild;
public TreeNode(T data) {
this.data = data;
this.parent = null;
this.leftChild = null;
this.rightChild = null;
}
@Override
public String toString() {
return data.toString();
}
}
/**
* 中序遍歷
*
* @param root
*/
public void midOrderTraverse(TreeNode root) {
if (root == null) {
return;
} else {
//LDR
midOrderTraverse(root.leftChild);
System.out.print(" " + root.toString());
midOrderTraverse(root.rightChild);
}
}
}
