二叉查找树代码实现 java
2019.4.18更新
递归求深度
//递归求深度
public int getDepth(){
return getDepth(root);
}
public int getDepth(TreeNode node){
if(node == null){
return -1;
}
int leftDepth = getDepth(node.leftChild);
int rightDepth = getDepth(node.rightChild);
return leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
}
remove方法
//删除节点
public boolean remove(char c){
if(contains(c)){
root = remove(root, c);//通过函数重载来进行递归
return true;
}
return false;
}
private TreeNode remove(TreeNode node, char c){
//先进行比较找到该节点的位置
int cmp = c - node.data;
if(cmp < 0){
node.leftChild = remove(node.leftChild, c);
}else if(cmp > 0){
node.rightChild = remove(node.rightChild, c);
}else{
if(node.leftChild == null && node.rightChild == null){ //没有子树直接删除该节点
node = null;
}else if(node.leftChild != null && node.rightChild != null){ //有两个子树的情况
//找到右子树的最小节点
TreeNode minOfRight = min(node.rightChild);
//将该节点的右子树上的值赋值给该节点
node.data = minOfRight.data;
//继续通过递归调用删除这个右子树节点，因为上一步赋值过去就相当于把原先节点删除了，这时有两个右子树节点，所以得删除下面一个
node.rightChild = remove(node.rightChild, minOfRight.data);
//找到左子树的最大节点
/*TreeNode maxOfLeft = max(node.leftChild);
node.data = maxOfLeft.data;
node.leftChild = remove(node.leftChild, maxOfLeft.data);*/
}else{
node = node.rightChild != null?node.leftChild:node.rightChild;
}
}
return node;
}
建树方法：用递归实现
//建树，上面的方法都是在树上操作的，建树时还没有树这个数据结构。所以应该是static方法
//参数类型是给两个字符串，返回类型是二叉查找树
public static BinarySearchTree buildTree(String preOrder, String inOrder){
//首先是数据验证，这里太麻烦，假定给定的两个字符串格式正确
//把字符串转换成字符数组
char[] preArr = preOrder.toCharArray();
char[] inArr = inOrder.toCharArray();
//构建二叉查找树和根节点
BinarySearchTree tree = new BinarySearchTree();
tree.root = build(preArr, inArr); //创建节点操作
tree.size = preArr.size();//添加长度
return tree;
//tree.root = new TreeNode(preArr[0]); //根节点是先序遍历第一个元素
//递归构建左子树
/*int index = 0;
while(inArr[index] != preArr[0]){
index ++;
}
char[] preOfLeft = Arrays.copyOfRange(preArr, 1, index+1); //// 包左不包右 把一棵树复制到另一棵树中去
char[] preOfRight = Arrays.copyOfRange(preArr, index + 1, preArr.length);
char[] inOfLeft = Arrays.copyOfRange(inArr, 0, index);
char[] inOfRight = Arrays.copyOfRange(inArr, index, inArr.length);*/
}
private static TreeNode build(char[] preArr, char[] inArr){
if(preArr == null || preArr.length == 0){ //如果先序遍历字符串数组是空的，返回null
return null;
}
TreeNode node = new TreeNode(preArr[0]); //创建根节点
int index = 0;
while (inArr[index] != preArr[0]){ //找到根节点在中序遍历中的位置
index ++;
}
char[] preOfLeft = Arrays.copyOfRange(preArr, 1, index + 1); // 包左不包右 创建先序遍历的左子树的字符数组
char[] preOfRight = Arrays.copyOfRange(preArr, index + 1, preArr.length); //创建先序遍历的右子树的字符数组
char[] inOfLeft = Arrays.copyOfRange(inArr, 0, index); //创建中序遍历的左子树的字符数组
char[] inOfRight = Arrays.copyOfRange(inArr, index + 1, inArr.length); //创建中序遍历的右子树的字符数组
// 递归构建左子树
node.leftChild = build(preOfLeft, inOfLeft);
// 递归构建右子树
node.rightChild = build(preOfRight, inOfRight);
return node;
}
package com.wangdao.tree;
import com.cskaoyan.exception.EmptyTreeException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* @author Yuechao Yang
* @version 2019-04-17-16:25
*
*/
public class BinarySearchTree {
//fields
private TreeNode root;
private int size;
//methods
public void add(char ch){
//递归实现
//root = add(root, ch);
//非递归实现 用循环去做
if(root == null){
root = new TreeNode(ch);
size++;
return;
}
TreeNode node = root;
while (node!= null){
int cmp = ch - node.data; //先进行比较大小
if(cmp < 0){ //如果小于node
if(node.rightChild == null){ //如果node没有左子树，创建一个
node.leftChild = new TreeNode(ch);
size++;
return;
}
node = node.leftChild; //移到左子树
}else if(cmp > 0){ //如果大于node
if(node.rightChild == null){ //如果node没有右子树，创建一个
node.rightChild = new TreeNode(ch);
size++; //长度加一
return;
}
node = node.rightChild; //移到右子树
}else{ //相等直接返回
return;
}
}
}
//这里是add方法的重载，递归实现添加 实现重载的方法应该是私有的，无参是public，有参是私有，两个结合才能实现递归
private TreeNode add(TreeNode node, char ch){
if(node == null){
node = new TreeNode(ch); //新建节点不用输入这么多实参，只用ch就可以了。默认左右子树是null
size++; //这里才是新创建一个节点，下面递归调用没有创建节点
return node;
}
int cmp = ch - node.data; //这里用减号，是比较Unicode码值的大小
if(cmp < 0){
node.leftChild = add(node.leftChild, ch);
}else if(cmp > 0){
node.rightChild = add(node.rightChild, ch);
}
return node; //这里的node返回的是上一层的调用者，要记住递归的调用是很多层的，不是直接传递给无参方法中的root
//传递给root是root的下一层，这里的node说不定是很多层的
}
//判空
public boolean isEmpty(){
return size == 0;
}
//树的元素个数
public int size(){
return size;
}
//访问节点
public void visit(TreeNode node){
System.out.println("data = " + node.data);
}
public void preOrderRecursion(){
//先序遍历（递归）
//preOrderRecursion(root);
//先序遍历（用栈实现）栈是线程安全的，效率不高
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return;
}
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
if(node.rightChild != null){
stack.push(node.rightChild);
}
if(node.leftChild != null){
stack.push(node.leftChild);
}
visit(node);
}
System.out.println();
}
private void preOrderRecursion(TreeNode node){
if(node == null){
return;
}
visit(node);
preOrderRecursion(node.leftChild);
preOrderRecursion(node.rightChild);
}
//中序遍历(递归)
public void inOrderRecursion(){
inOrderRecursion(root);
System.out.println();
}
private void inOrderRecursion(TreeNode node){
if(node == null){
return;
}
inOrderRecursion(node.leftChild);
visit(node);
inOrderRecursion(node.rightChild);
}
//后序遍历（递归）
public void postOrderRecursion(){
postOrderRecursion(root);
System.out.println();
}
private void postOrderRecursion(TreeNode node){
if(node == null){
return;
}
postOrderRecursion(node.leftChild);
postOrderRecursion(node.rightChild);
visit(node);
}
//层次遍历
//借助队列实现
public void levelOrder(){
if(root == null){
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode node;
while((node = queue.poll()) != null){
if(node.leftChild != null){
queue.offer(node.leftChild);
}
if(node.rightChild != null){
queue.offer(node.rightChild);
}
visit(node);
}
}
//获取最小值
public char min(){
//非递归
/*if(root == null){
throw new EmptyTreeException();
}
TreeNode node = root;
while(node.rightChild != null){
node = node.leftChild;
}
return node.data;*/
//递归
if(root == null){
throw new EmptyTreeException();
}
return min(root).data;
}
private TreeNode min(TreeNode node){
if(node.leftChild != null){
return min(node.leftChild);
}
return node;
}
//获取最大值
public char max(){
//非递归遍历
/*if(root == null){
throw new EmptyTreeException();
}
TreeNode node = root;
while(node.rightChild != null){
node = node.rightChild;
}
return node.data;*/
//递归遍历
if(root == null){
throw new EmptyTreeException();
}
return max(root).data;
}
private TreeNode max(TreeNode node){
if(node.rightChild != null){
return max(node.rightChild);
}
return node;
}
//检查是否包含
public boolean contains(char c){
//递归方法
//return contains(root, c);
//非递归方法
TreeNode node = root;
while(node != null){
int cmp = c - node.data;
if(cmp < 0){
node = node.leftChild;
}else if(cmp > 0){
node = node.rightChild;
}else {
return true;
}
}
return false;
}
private boolean contains(TreeNode node, char c) {
if(node == null){
return false;
}
int cmp = c - node.data;
if(cmp < 0){
return contains(node.leftChild, c);
}else if(cmp > 0){
return contains(node.rightChild, c);
}
return true;
}
//节点
private static class TreeNode{
//fields
private TreeNode leftChild;
private char data;
private TreeNode rightChild;
//constructors
public TreeNode() {
}
public TreeNode(char ch) {
this.data = ch;
}
/*public TreeNode(TreeNode leftChild, char ch, TreeNode rightChild) { //可以不用声明
this.leftChild = leftChild;
this.data = ch;
this.rightChild = rightChild;
}*/
}
}
自定义异常类如下：
package com.wangdao.exception;
/**
* @author Yuechao Yang
* @version 2019-04-17-23:23
*/
public class EmptyTreeException extends RuntimeException {
public EmptyTreeException() {
}
public EmptyTreeException(String message) {
super(message);
}
}
其中栈用来非递归实现先序遍历的思路下图所示：
队列非递归实现层次遍历思路如下图所示：
还有remove方法以后有时间补上