下面是我自己写的查找二叉树的结构：
希望对各位有所帮助，如果有错误的地方或更好的建议，请不吝赐教，谢谢
- 构建查找二叉树
- 查找二叉树添加节点方法
- 在某树找到距离该数据最近的节点
- 查找二叉树节点
- 得到最小数据节点方法
- 移除节点方法
- 递归查询二叉树中序遍历（从小到大排列）
/**
*
* 2017年8月11日 上午10:18:08
*
*/
public class SearchBinaryTree> {
public TreeEntry root;
/**
* 构建查找二叉树
* @param a
*/
public void newSearchBinaryTree(T... a) {
for (T t : a) {
put(t);
}
}
/**
* 查找二叉树添加节点方法
* @param data 数据
* @return 数据的节点
*/
public TreeEntry put(T data) {
// 如果根节点为空，
if (root == null) {
// 则将该节点设置为根节点
root = new TreeEntry<>(data);
return null;
}
// 找到最近的节点作为父节点
TreeEntry parent = getRecentlyNode(data, root);
if (parent.data.equals(data)) {
return parent;
}
// 为当前数据创建新节点
TreeEntry node = new TreeEntry<>(data);
// 如果当前数据小于父节点数据
if (data.compareTo(parent.data) == -1) {
// 将当前节点设置为父节点的左孩子节点
parent.leftChild = node;
// 如果当前数据大于父节点数据
} else if (data.compareTo(parent.data) == 1) {
// 将当前节点设置为父节点的右孩子节点
parent.rightChild = node;
}
// 将父节点设置为当前数据的父节点
node.parent = parent;
// 返回当前节点
return node;
}
/**
* 在该树中找到距离该数据最近的节点
* @param data 数据
* @param tree 树
* @return 节点
*/
public TreeEntry getRecentlyNode(T data, TreeEntry tree) {
// 设置节点变量，与父节点变量
TreeEntry node, parent = null;
// 将根节点设置为当前节点
node = tree;
// 当前节点不为空时继续循环
while (node != null) {
// 将当前节点设置为父节点，准备递归子树
// 为添加新节点做缓存
parent = node;
// 如果新数据小于当前节点数据
if (data.compareTo(node.data) == -1) {
// 将当前节点设置为左孩子节点，进行递归左子树
node = node.leftChild;
// 如果新数据大于当前节点数据
} else if (data.compareTo(node.data) == 1) {
// 将当前节点设置为右孩子节点，进行递归右子树
node = node.rightChild;
// 如果新数据等于当前节点数据
} else {
// 返回当前节点
return node;
}
}
return parent;
}
/**
* 非递归查找
* @param data 数据
* @return 节点
*/
public TreeEntry nonRecSearch(T data) {
if (root == null) {
return null;
}
TreeEntry node = root;
while (node != null) {
// 如果新数据小于当前节点数据
if (data.compareTo(node.data) == -1) {
// 将当前节点设置为左孩子节点，进行递归左子树
node = node.leftChild;
// 如果新数据大于当前节点数据
} else if (data.compareTo(node.data) == 1) {
// 将当前节点设置为右孩子节点，进行递归右子树
node = node.rightChild;
// 如果新数据等于当前节点数据
} else {
// 返回当前节点
return node;
}
}
return null;
}
/**
* 递归查询节点方法
* @param data
* @return
*/
public TreeEntry recSearch(T data) {
return recSearch(data, root);
}
/**
* 二叉树递归查询节点方法
* @param data 数据
* @param tree 树
* @return 节点
*/
private TreeEntry recSearch(T data, TreeEntry tree) {
// 如果该树根节点为空，则返回空
if (tree == null) {
return null;
}
// 判断数据与根节点数据的大小
switch (data.compareTo(tree.data)) {
// 数据>根节点数据
case 1:
// 递归根节点的右子树
return recSearch(data, tree.rightChild);
// 数据<根节点数据
case -1:
// 递归根节点的左子树
return recSearch(data, tree.leftChild);
// 相等
case 0:
// 返回根节点
return tree;
// 没找到返回空
default:
return null;
}
}
/**
* 节点覆盖方法
* @param node 原节点
* @param newNode 新节点
*/
private void replaceNode(TreeEntry node, TreeEntry newNode) {
// 获取原节点的父节点
TreeEntry parent = node.parent;
// 如果原节点为父节点的左孩子
if (node.equals(parent.leftChild)) {
// 将新节点作为父节点的左孩子
parent.leftChild = newNode;
// 否则原节点为父节点的右孩子
} else {
// 将新节点作为父节点的右孩子
parent.rightChild = newNode;
}
}
/**
* 最小节点方法
* @return 最小节点
*/
public TreeEntry getMin() {
return findMin(root);
}
/**
* 树中最小节点方法
* @param tree 树
* @return 最小节点
*/
private TreeEntry findMin(TreeEntry tree) {
// 如果该节点为空，则返回空
if (tree == null) {
return null;
}
// 如果该节点有左子树
if (tree.leftChild != null) {
// 递归左子树
return findMin(tree.leftChild);
// 否则没有左子树，返回该节点
} else {
return tree;
}
}
/**
* 移除节点
* @param data 数据
* @return 节点
*/
public TreeEntry remove(T data) {
return remove(data, root);
}
/**
* 树中移除节点方法
* @param data 数据
* @return 节点
*/
public TreeEntry remove(T data, TreeEntry tree) {
// 在树中搜索该节点
TreeEntry node = recSearch(data, tree);
// 如果没有找到该节点返回空
if (node == null) {
return null;
}
// 获取该节点的父节点
TreeEntry parent = node.parent;
// 获取该节点的左孩子节点
TreeEntry leftChild = node.leftChild;
// 获取该节点的右孩子节点
TreeEntry rightChild = node.rightChild;
// 如果两个节点都不为空
if (leftChild != null && rightChild != null) {
// 获取该节点的右子树中最小的，并取出其中数据
T min = findMin(rightChild).data;
// 在右子树中移除该最小节点
if (remove(min, rightChild) == null) {
throw new RuntimeException("删除错误");
}
// 见最小元素构建为新节点
TreeEntry newNode = new TreeEntry<>(min);
// 将原节点的引用复制到新节点上
newNode.parent = parent;
newNode.leftChild = leftChild;
newNode.rightChild = rightChild;
leftChild.parent = newNode;
rightChild.parent = newNode;
// 如果原节点为根节点
if (node == root) {
// 将新节点作为根节点
root = newNode;
// 否则用心节点覆盖到老节点
} else {
replaceNode(node, newNode);
}
} else {
// 如果该节点为根节点
if (node == root) {
// 如果根节点为叶子节点
if (leftChild == null && rightChild == null) {
// 将根节点设置为空
root = null;
// 如果左孩子节点为空
} else if (leftChild == null) {
// 使用右孩子节点覆盖根节点
root = rightChild;
// 该节点父节点为空
rightChild.parent = null;
// 如果该节点得右孩子节点为空
} else {
// 使用左孩子节点覆盖根节点
root = leftChild;
// 该节点的父节点为空
leftChild.parent = null;
}
// 如果该节点不为根节点
} else {
// 如果该节点为叶子节点
if (leftChild == null && rightChild == null) {
// 使用空覆盖该节点的孩子节点
replaceNode(node, null);
// 如果该节点的左孩子节点为空
} else if (leftChild == null) {
// 用右孩子节点覆盖原节点
replaceNode(node, rightChild);
// 如果该节点的右孩子节点为空
} else {
// 用左孩子节点覆盖原节点
replaceNode(node, leftChild);
}
}
}
return node;
}
public void midOrder() {
midOrder(root);
}
/**
* 递归二叉树中序遍历方法
* @param tree
*/
private void midOrder(TreeEntry tree) {
// 如果节点为空，则返回
if (tree == null) {
return;
} else {
// 中序遍历的顺序为，左根右
// 中序遍历左子树
midOrder(tree.leftChild);
// 输出根节点
System.out.println(tree.data);
// 中序遍历右子树
midOrder(tree.rightChild);
}
}
public class TreeEntry {
private int index;
private T data;
private TreeEntry parent;
private TreeEntry leftChild;
private TreeEntry rightChild;
public TreeEntry(int index) {
super();
this.index = index;
}
public TreeEntry(T data) {
super();
this.data = data;
}
public TreeEntry(int index, T data) {
super();
this.index = index;
this.data = data;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public TreeEntry getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeEntry leftChild) {
this.leftChild = leftChild;
}
public TreeEntry getRightChild() {
return rightChild;
}
public void setRightChild(TreeEntry rightChild) {
this.rightChild = rightChild;
}
public TreeEntry getParent() {
return parent;
}
public void setParent(TreeEntry parent) {
this.parent = parent;
}
@Override
public String toString() {
return data.toString();
}
}
}
