package com.ys.tree;
 
public class Node {
    private Object data;    //節(jié)點(diǎn)數(shù)據(jù)
    private Node leftChild; //左子節(jié)點(diǎn)的引用
    private Node rightChild; //右子節(jié)點(diǎn)的引用
    //打印節(jié)點(diǎn)內(nèi)容
    public void display(){
        System.out.println(data);
    }
 
}

package com.ys.tree;
 
public interface Tree {
    //查找節(jié)點(diǎn)
    public Node find(Object key);
    //插入新節(jié)點(diǎn)
    public boolean insert(Object key);
    //刪除節(jié)點(diǎn)
    public boolean delete(Object key);
    //Other Method......
}

//查找節(jié)點(diǎn)
public Node find(int key) {
    Node current = root;
    while(current != null){
        if(current.data > key){//當(dāng)前值比查找值大，搜索左子樹
            current = current.leftChild;
        }else if(current.data < key){//當(dāng)前值比查找值小，搜索右子樹
            current = current.rightChild;
        }else{
            return current;
        }
    }
    return null;//遍歷完整個(gè)樹沒找到，返回null
}
　　用變量

//插入節(jié)點(diǎn)
public boolean insert(int data) {
    Node newNode = new Node(data);
    if(root == null){//當(dāng)前樹為空樹，沒有任何節(jié)點(diǎn)
        root = newNode;
        return true;
    }else{
        Node current = root;
        Node parentNode = null;
        while(current != null){
            parentNode = current;
            if(current.data > data){//當(dāng)前值比插入值大，搜索左子節(jié)點(diǎn)
                current = current.leftChild;
                if(current == null){//左子節(jié)點(diǎn)為空，直接將新值插入到該節(jié)點(diǎn)
                    parentNode.leftChild = newNode;
                    return true;
                }
            }else{
                current = current.rightChild;
                if(current == null){//右子節(jié)點(diǎn)為空，直接將新值插入到該節(jié)點(diǎn)
                    parentNode.rightChild = newNode;
                    return true;
                }
            }
        }
    }
    return false;
}

//中序遍歷
public void infixOrder(Node current){
    if(current != null){
        infixOrder(current.leftChild);
        System.out.print(current.data+" ");
        infixOrder(current.rightChild);
    }
}
 
//前序遍歷
public void preOrder(Node current){
    if(current != null){
        System.out.print(current.data+" ");
        preOrder(current.leftChild);
        preOrder(current.rightChild);
    }
}
 
//后序遍歷
public void postOrder(Node current){
    if(current != null){
        postOrder(current.leftChild);
        postOrder(current.rightChild);
        System.out.print(current.data+" ");
    }
}

//找到最大值
public Node findMax(){
    Node current = root;
    Node maxNode = current;
    while(current != null){
        maxNode = current;
        current = current.rightChild;
    }
    return maxNode;
}
//找到最小值
public Node findMin(){
    Node current = root;
    Node minNode = current;
    while(current != null){
        minNode = current;
        current = current.leftChild;
    }
    return minNode;
}

@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;
        }
    }
    //如果當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)
    if(current.leftChild == null && current.rightChild == null){
        if(current == root){
            root = null;
        }else if(isLeftChild){
            parent.leftChild = null;
        }else{
            parent.rightChild = null;
        }
        return true;
    }
    return false;
}

//當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)
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{
    //current.leftChild != null && current.rightChild == null
    if(current == root){
        root = current.leftChild;
    }else if(isLeftChild){
        parent.leftChild = current.leftChild;
    }else{
        parent.rightChild = current.leftChild;
    }
    return true;
}

package com.ys.tree;
 
public class Node {
    int data;   //節(jié)點(diǎn)數(shù)據(jù)
    Node leftChild; //左子節(jié)點(diǎn)的引用
    Node rightChild; //右子節(jié)點(diǎn)的引用
    boolean isDelete;//表示節(jié)點(diǎn)是否被刪除
     
    public Node(int data){
        this.data = data;
    }
    //打印節(jié)點(diǎn)內(nèi)容
    public void display(){
        System.out.println(data);
    }
 
}

package com.ys.tree;
 
public interface Tree {
    //查找節(jié)點(diǎn)
    public Node find(int key);
    //插入新節(jié)點(diǎn)
    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();
     
    //刪除節(jié)點(diǎn)
    public boolean delete(int key);
     
    //Other Method......
}

package com.ys.tree;
 
public class BinaryTree implements Tree {
    //表示根節(jié)點(diǎn)
    private Node root;
 
    //查找節(jié)點(diǎn)
    public Node find(int key) {
        Node current = root;
        while(current != null){
            if(current.data > key){//當(dāng)前值比查找值大，搜索左子樹
                current = current.leftChild;
            }else if(current.data < key){//當(dāng)前值比查找值小，搜索右子樹
                current = current.rightChild;
            }else{
                return current;
            }
        }
        return null;//遍歷完整個(gè)樹沒找到，返回null
    }
 
    //插入節(jié)點(diǎn)
    public boolean insert(int data) {
        Node newNode = new Node(data);
        if(root == null){//當(dāng)前樹為空樹，沒有任何節(jié)點(diǎn)
            root = newNode;
            return true;
        }else{
            Node current = root;
            Node parentNode = null;
            while(current != null){
                parentNode = current;
                if(current.data > data){//當(dāng)前值比插入值大，搜索左子節(jié)點(diǎn)
                    current = current.leftChild;
                    if(current == null){//左子節(jié)點(diǎn)為空，直接將新值插入到該節(jié)點(diǎn)
                        parentNode.leftChild = newNode;
                        return true;
                    }
                }else{
                    current = current.rightChild;
                    if(current == null){//右子節(jié)點(diǎn)為空，直接將新值插入到該節(jié)點(diǎn)
                        parentNode.rightChild = newNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }
     
    //中序遍歷
    public void infixOrder(Node current){
        if(current != null){
            infixOrder(current.leftChild);
            System.out.print(current.data+" ");
            infixOrder(current.rightChild);
        }
    }
     
    //前序遍歷
    public void preOrder(Node current){
        if(current != null){
            System.out.print(current.data+" ");
            infixOrder(current.leftChild);
            infixOrder(current.rightChild);
        }
    }
     
    //后序遍歷
    public void postOrder(Node current){
        if(current != null){
            infixOrder(current.leftChild);
            infixOrder(current.rightChild);
            System.out.print(current.data+" ");
        }
    }
    //找到最大值
    public Node findMax(){
        Node current = root;
        Node maxNode = current;
        while(current != null){
            maxNode = current;
            current = current.rightChild;
        }
        return maxNode;
    }
    //找到最小值
    public Node findMin(){
        Node current = root;
        Node minNode = current;
        while(current != null){
            minNode = current;
            current = current.leftChild;
        }
        return minNode;
    }
     
    @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;
            }
        }
        //如果當(dāng)前節(jié)點(diǎn)沒有子節(jié)點(diǎn)
        if(current.leftChild == null && current.rightChild == null){
            if(current == root){
                root = null;
            }else if(isLeftChild){
                parent.leftChild = null;
            }else{
                parent.rightChild = null;
            }
            return true;
             
            //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，右子節(jié)點(diǎn)
        }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;
            //當(dāng)前節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，左子節(jié)點(diǎn)
        }else if(current.leftChild != null && current.rightChild == null){
            if(current == root){
                root = current.leftChild;
            }else if(isLeftChild){
                parent.leftChild = current.leftChild;
            }else{
                parent.rightChild = current.leftChild;
            }
            return true;
        }else{
            //當(dāng)前節(jié)點(diǎn)存在兩個(gè)子節(jié)點(diǎn)
            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 Node getSuccessor(Node delNode){
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightChild;
        while(current != null){
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        //后繼節(jié)點(diǎn)不是刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)，將后繼節(jié)點(diǎn)替換刪除節(jié)點(diǎn)
        if(successor != delNode.rightChild){
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
         
        return successor;
    }
     
    public static void main(String[] args) {
        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);//刪除沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
        bt.delete(30);//刪除有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        bt.delete(80);//刪除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        System.out.println(bt.findMax().data);
        System.out.println(bt.findMin().data);
        System.out.println(bt.find(100));
        System.out.println(bt.find(200));
         
    }
 
}