算法——二叉树

/**
 * 	二叉树的结点类
 * @author wydream
 *
 */

public class Node {

	int data;//节点数据
	Node leftChild;//左子节点的引用
	Node rightChild;//右子节点的引用
	boolean isDelete;//表示节点是否被删除
	
	public Node(int data) {
		this.data=data;
	}
	
	//打印节点内容
	public void display() {
		System.out.println(data);
	}
	
}

/**
 * 	二叉树的具体方法
 * @author wydream
 *
 */

public interface Tree {

	//查找节点
    public Node find(int key);
    //插入新节点
    public boolean insert(int data);
     
    //中序遍历
    public void infixOrder(Node current);
    //前序遍历
    public void preOrder(Node current);
    //后序遍历
    public void postOrder(Node current);
     
    //查找最大值
    public Node findMax();
    //查找最小值
    public Node findMin();
     
    //删除节点
    public boolean delete(int key);	
}

import org.junit.jupiter.api.Test;

public class BinaryTree implements Tree {
	
	private Node root;//根节点

	@Override
	public Node find(int key) {
		Node current=root;
		while(current!=null) {
			if(current.data>key) {//当前值比查找值大，搜索左子树
				current=current.leftChild;
			}else if(current.data<key) {//当前值比查找值小，搜索右子树
				current=current.rightChild;
			}else {
				return current;
			}
		}
		return null;//遍历完整个树没找到，返回null
	}

	@Override
	public boolean insert(int key) {
		
		Node newNode=new Node(key);
		if(root==null) {//当前树为空树，没有任何节点
			root=newNode;
			return true;
		}else {
			Node current=root;
			Node parentNode=null;
			while(current!=null) {
				parentNode=current;
				if(current.data>key) {//当前值比插入值大，搜索左子节点
					current=current.leftChild;
					if(current==null) {//左孩子为空，则插入该节点到左孩子
						parentNode.leftChild=newNode;
						return true;
					}
				}else {//当前值比插入值小，搜索右子节点
					current=current.rightChild;
					if(current==null) {//右孩子为空，则插入该节点到右孩子
						parentNode.rightChild=newNode;
						return true;
					}
				}
			}
		}
		return false;
	}

	//删除节点
	@Override
	public boolean delete(int key) {
		Node current=root;
		Node parent=root;
		boolean isLeftChild=false;
		//查找删除值，找不到直接返回false
		while(current.data!=key) {
			parent=current;
			if(current.data>key) {
				isLeftChild=true;
				current=current.leftChild;
			}else {
				isLeftChild=false;
				current=current.rightChild;
			}
			if(current==null) {
				return false;
			}
		}
		
		//如果当前节点没有子节点
		if(current.leftChild==null&&current.rightChild==null) {
			if(current==root) {
				root=null;
			}else if(isLeftChild) {
				parent.leftChild=null;
			}else {
				parent.rightChild=null;
			}
			return true;
		}else if(current.leftChild==null&&current.rightChild!=null){//当前节点有一个子节点，右子节点
			if(current==root) {
				root=current.rightChild;
			}else if(isLeftChild) {
				parent.leftChild=current.rightChild;
			}else {
				parent.rightChild=current.rightChild;
			}
			return true;
		}else if(current.rightChild==null&&current.leftChild!=null) {//当前节点有一个子节点，左子节点
			if(current==root) {
				root=current.leftChild;
			}else if(isLeftChild) {
				parent.leftChild=current.leftChild;
			}else {
				parent.rightChild=current.leftChild;
			}
			return true;
		}else {//当前节点存在两个子节点
			Node successor = getSuccessor(current);
            if(current == root){
                root= successor;
            }else if(isLeftChild){
                parent.leftChild = successor;
            }else{
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
		}
		
		
		return false;
	}
	
	//中序遍历:左子树——》根节点——》右子树
	public void infixOrder(Node current) {
		if(current!=null) {
			infixOrder(current.leftChild);
			System.out.println(current.data);
			infixOrder(current.rightChild);
		}
	}
	
	//前序遍历:根节点——》左子树——》右子树
	public void preOrder(Node current) {
		if(current!=null) {
			System.out.println(current.data);
			preOrder(current.leftChild);
			preOrder(current.rightChild);
		}
	}
	

	//后序遍历:左子树——》右子树——》根节点
	public void postOrder(Node current) {
		if(current!=null) {
			postOrder(current.leftChild);
			postOrder(current.rightChild);
			System.out.println(current.data);
		}
	}
	
	//查找最小值
	public Node findMin() {
		Node current=root;
		Node minNode=current;
		while(current!=null) {
			minNode=current;
			current=current.leftChild;
		}
		return minNode;
	}
	
	
	//查找最大值
	public Node findMax() {
		Node current=root;
		Node maxNode=current;
		while(current!=null) {
			maxNode=current;
			current=current.rightChild;
		}
		return maxNode;
	}
	
	public Node getSuccessor(Node delNode) {
		Node successorParent=delNode;
		Node successor=delNode;
		Node current=delNode.rightChild;
		while(current!=null) {
			successorParent=successor;
			successor=current;
			current=current.leftChild;
		}
		//后继节点不是删除节点的右子节点,将后继节点替换删除节点
		if(successor!=delNode.rightChild) {
			successorParent.leftChild=successor.rightChild;
			successor.rightChild=delNode.rightChild;
		}
		return successor;
	}
	
	//测试
	@Test
	public void test() {
		BinaryTree bt = new BinaryTree();
        bt.insert(50);
        bt.insert(20);
        bt.insert(80);
        bt.insert(10);
        bt.insert(30);
        bt.insert(60);
        bt.insert(90);
        bt.insert(25);
        bt.insert(85);
        bt.insert(100);
        bt.delete(10);//删除没有子节点的节点
        bt.delete(30);//删除有一个子节点的节点
        bt.delete(80);//删除有两个子节点的节点
        System.out.println(bt.findMax().data);
        System.out.println(bt.findMin().data);
        System.out.println(bt.find(100));
        System.out.println(bt.find(200));
        System.out.println("=====中序遍历=====");
		infixOrder(bt.root);
		System.out.println("=====前序遍历=====");
		preOrder(bt.root);
		System.out.println("=====后序遍历=====");
		postOrder(bt.root);
		
	}
	
}

100
20
com.alibaba.test11.tree.Node@ed7f8b4
null
=====中序遍历=====
20
25
50
60
85
90
100
=====前序遍历=====
50
20
25
85
60
90
100
=====后序遍历=====
25
20
60
100
90
85
50