image
import javax.swing.tree.TreeNode;
import java.util.NoSuchElementException;
/**
* 二分查找树
*/
public class SearchBinaryTree<T extends Comparable> {
TreeNode root;//根结点
public SearchBinaryTree() {
}
/**
* 添加一个结点
* <p>
* 首先通过比较大小找到需要添加的结点的父节点parent,
* 然后根据结点值与parent值大小,将该结点添加到parent的leftChild或者rightChild
*
* @param data 输入要添加的值
* @return 返回添加的结点本身
*/
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;
}
}
/**
* 查询树中对应的结点
* <p>
* data与根结点比较大小,比根结点大说明在根节点的右边,继续data与根节点的rightChild比大小,以此类推,直到找到与data相等的
* 比根节点小在根节点的左边,继续data与根节点的leftChild比大小,以此类推,直到找到与data相等的
* 与根结点相等则返回根结点
*
* @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;
}
/**
* 删除结点
*
* @param node 要删除的结点
* @return
*/
public TreeNode delete(TreeNode node) {
if (node == null) {
throw new NoSuchElementException();
} else {
TreeNode parent = node.parent;
//1.删除叶子结点
if (node.leftChild == null && node.rightChild == null) {
//只有一个结点
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) {
//只有左孩子
/**
* 删除根结点
*/
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) {
//只有右孩子
/**
* 删除根结点
*/
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 {
//有左右两个孩子
/**
* node的右子树的左子树为空,直接补上右子树
*/
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 {
/**
* 否则就要补上右子树的左子树上最小的一个
*/
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补上去
if (parent == null) {
root = leftNode;
} else {
if (parent.leftChild == node) {
parent.leftChild = leftNode;
} else {
parent.rightChild = leftNode;
}
node.parent = null;
}
}
}
}
return null;
}
/**
* 获取最小左孩子
*
* @param root 根结点
* @return
*/
private TreeNode getMinLeftChild(TreeNode root) {
if (root == null) {
return null;
}
while (root.leftChild != null) {
root = root.leftChild;
}
return root;
}
/**
* 节点类
*/
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);
}
}
}
网友评论