二叉树和二叉搜索树Java代码示例

原理

后续原理，先上代码

代码

树节点

package per.lihao.tree;

/**
 * @author : LiHao
 * @date : 2018/12/4 9:59
 */
public class TreeNode {
    /**
     * 关键字
     */
    private int data;

    /**
     * 左子树节点
     */
    private TreeNode lnode;

    /**
     * 右子树节点
     */
    private TreeNode rnode;

    /**
     * 父节点
     */
    private TreeNode parent;

    private boolean stackFirst = false;

    public TreeNode getParent() {
        return parent;
    }

    public void setParent(TreeNode parent) {
        this.parent = parent;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public TreeNode getLnode() {
        return lnode;
    }

    public void setLnode(TreeNode lnode) {
        this.lnode = lnode;
    }

    public TreeNode getRnode() {
        return rnode;
    }

    public void setRnode(TreeNode rnode) {
        this.rnode = rnode;
    }

    public boolean isStackFirst() {
        return stackFirst;
    }

    public void setStackFirst(boolean stackFirst) {
        this.stackFirst = stackFirst;
    }

    public TreeNode(){}

    public TreeNode(int k){
        data = k;
    }
}

二叉树

package per.lihao.tree;

import java.util.Stack;

/**
 * 二叉树
 * @author : LiHao
 * @date : 2018/12/26 10:41
 */
public class BinaryTree {
    /**
     * 根节点
     */
    protected TreeNode root;

    public BinaryTree(){}
    /**
     * 构造函数
     * @param node
     */
    public BinaryTree(TreeNode node){
        root = node;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 递归
     * 中序遍历根节点
     */
    public void inOrderTraversalRecursion(){
        inOrderTraversalRecursion(root);
        System.out.println();
    }

    /**
     * 递归
     * 中序遍历
     * @param node
     */
    protected void inOrderTraversalRecursion(TreeNode node){
        if (node==null){
            return;
        }
        inOrderTraversalRecursion(node.getLnode());
        System.out.print(node.getData()+" ");
        inOrderTraversalRecursion(node.getRnode());
    }

    /**
     * 循环
     * 中序遍历根节点
     */
    public void inOrderTraversalLoop(){
        inOrderTraversalLoop(root);
        System.out.println();
    }

    /**
     * 循环
     * 中序遍历
     * @param node
     */
    protected void inOrderTraversalLoop(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = node;
        TreeNode temp;
        // 一直往左找，同时沿线的节点放入栈，直到最左边的子节点为空
        // 出栈，并打印该节点，然后转向该节点的右子节点
        while (currentNode!=null || !stack.isEmpty()){
            while (currentNode!=null){
                stack.push(currentNode);
                currentNode = currentNode.getLnode();
            }
            if (!stack.isEmpty()){
                temp = stack.pop();
                System.out.print(temp.getData() + " ");
                currentNode = temp.getRnode();
            }
        }
    }

    /**
     * 递归
     * 前序遍历根节点
     */
    public void preOrderTraversalRecursion(){
        preOrderTraversalRecursion(root);
        System.out.println();
    }
    /**
     * 递归
     * 前序遍历
     * @param node
     */
    protected void preOrderTraversalRecursion(TreeNode node){
        if (node==null){
            return;
        }
        System.out.print(node.getData() + " ");
        preOrderTraversalRecursion(node.getLnode());
        preOrderTraversalRecursion(node.getRnode());
    }

    /**
     * 循环
     * 前序遍历根节点
     */
    public void preOrderTraversalLoop(){
        preOrderTraversalLoop(root);
        System.out.println();
    }

    /**
     * 循环
     * 前序遍历
     * @param node
     */
    protected void preOrderTraversalLoop(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = node;
        TreeNode temp;
        // 一直往左找，同时打印沿线的节点并放入栈，直到最左边的子节点为空
        // 出栈，然后转向该节点的右子节点
        while (currentNode!=null || !stack.isEmpty()){
            while (currentNode!=null){
                System.out.print(currentNode.getData() + " ");
                stack.push(currentNode);
                currentNode = currentNode.getLnode();
            }
            if (!stack.isEmpty()){
                temp = stack.pop();
                currentNode = temp.getRnode();
            }
        }
    }

    /**
     * 递归
     * 后序遍历根节点
     */
    public void postOrderTraversalRecursion(){
        postOrderTraversalRecursion(root);
        System.out.println();
    }

    /**
     * 递归
     * 后序遍历
     * @param node
     */
    protected void postOrderTraversalRecursion(TreeNode node){
        if (node==null){
            return;
        }
        postOrderTraversalRecursion(node.getLnode());
        postOrderTraversalRecursion(node.getRnode());
        System.out.print(node.getData() + " ");
    }

    /**
     * 循环
     * 后序遍历根节点
     */
    public void postOrderTraversalLoop(){
        postOrderTraversalLoop(root);
        System.out.println();
    }

    /**
     * 循环
     * 后续遍历
     * @param node
     */
    public void postOrderTraversalLoop(TreeNode node){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = node;
        TreeNode temp;
        // 先一直往左找，沿线节点放入栈，且节点处的stackfirst=false
        // 当遇到左孩子为空时，取其右孩子继续寻找，此时父节点的stackfirst=true
        // 为true时打印节点
        while (currentNode!=null || !stack.isEmpty()){
            while (currentNode!=null){
                stack.push(currentNode);
                currentNode = currentNode.getLnode();
            }
            if (!stack.isEmpty()){
                // 不取出节点，先判断其stackfirst值
                temp = stack.peek();
                if (temp.isStackFirst()){
                    temp = stack.pop();
                    System.out.print(temp.getData() + " ");
                }else {
                    temp.setStackFirst(true);
                    currentNode = temp.getRnode();
                }
            }
        }
    }

    /**
     * 生成测试树
     *         10
     *      /    \
     *    3      12
     *         /
     *       34
     *         \
     *         23
     * @return node
     */
    public static TreeNode makeTreeTest(){
        TreeNode root = new TreeNode(10);
        root.setLnode(new TreeNode(3));
        TreeNode node1 = new TreeNode(12);
        TreeNode node2 = new TreeNode(34);
        TreeNode node3 = new TreeNode(23);
        node1.setLnode(node2);
        node2.setRnode(node3);
        root.setRnode(node1);
        return root;
    }

}

二叉搜索树

package per.lihao.tree;

/**
 * 二叉搜索树/二叉排序树
 * @author : LiHao
 * @date : 2018/12/24 15:21
 */
public class BinarySearchTree extends BinaryTree {

    /**
     * 插入数据 自动生成树结构
     * @param k int
     */
    public void insert(int k){
        TreeNode node = new TreeNode(k);
        insertNode(node);
    }

    /**
     * 插入数据数组 自动生成树结构
     * @param ks int[]
     */
    public void insert(int[] ks){
        for (int k:ks){
            insert(k);
        }
    }

    /**
     * 插入节点对象 构造BST树
     * @param node
     */
    private void insertNode(TreeNode node){
        // 若根节点为空，则返回当前节点为根节点
        if (root==null){
            root = node;
            return;
        }
        TreeNode temp = root;
        while (true){
            if (node.getData()<=temp.getData()){
                //若有左子树，说明还需继续比较，移动到左子树的根节点
                if (temp.getLnode()!=null){
                    temp = temp.getLnode();
                }
                //若没有左子树，说明此node可以变作叶子节点
                else {
                    temp.setLnode(node);
                    node.setParent(temp);
                    return;
                }
            }else {
                //若有右子树，说明还需继续比较，移动到右子树的根节点
                if (temp.getRnode()!=null){
                    temp = temp.getRnode();
                }else {
                    temp.setRnode(node);
                    node.setParent(temp);
                    return;
                }
            }
        }
    }

    /**
     * 查询关键字节点，无则返回null
     * @param k 关键字
     * @return
     */
    public TreeNode search(int k){
        TreeNode temp = root;
        while (temp != null){
            if (temp.getData() == k){
                return temp;
            }else if (temp.getData()>=k){
                temp = temp.getLnode();
            }else{
                temp = temp.getRnode();
            }
        }
        return temp;
    }

    /**
     * 查找关键字k的前驱节点，若没有 则返回null
     * @param k
     * @return
     */
    public TreeNode searchPredecessor(int k){
        TreeNode node = search(k);
        if (node==null){
            return node;
        }
        // 若有左子树，则前驱为左子树中最右边的节点
        TreeNode temp = node.getLnode();
        while (temp!=null){
            if (temp.getRnode()!=null){
                temp = temp.getRnode();
            }else {
                return temp;
            }
        }
        // 若无左子树，则需要寻找当前节点的第一个有右孩子且左孩子中没有该节点的祖先
        if (temp==null){
            temp = node.getParent();
            while (temp!=null){
                // 左父母的左子树如果为空，则前驱就是左父母
                // 若是右父母，需要找到其右父母的左父母
                if (temp.getLnode()==null){
                    break;
                }else {
                    if (temp.getLnode().getData()==k){
                        temp = temp.getParent();
                    }else {
                        break;
                    }
                }
            }
        }
        return temp;
    }

    /**
     * 查找关键字k的后继节点，若没有 则返回null
     * @param k 关键字
     * @return
     */
    public TreeNode searchSuccessor(int k){
        // 首先查找命中的节点
        TreeNode node = search(k);
        if (node==null){
            return null;
        }
        TreeNode temp = node.getRnode();
        while (temp!=null){
            if (temp.getLnode()!=null){
                temp = temp.getLnode();
            }else {
                return temp;
            }
        }
        if (temp==null){
            temp = node.getParent();
            while (temp!=null){
                if (temp.getRnode()==null){
                    break;
                }else {
                    if (temp.getRnode().getData()==k){
                        temp = temp.getParent();
                    }else {
                        break;
                    }
                }
            }
        }
        return temp;
    }

    /**
     * 删除某节点
     * @param k
     */
    public void delete(int k){
        // 首先查找k 不存在则返回
        TreeNode node = search(k);
        if (node==null){
            return;
        }

        if (node.getLnode()!=null && node.getRnode()!=null){
            // 查询其前驱节点
            TreeNode pre = searchPredecessor(k);
            node.setData(pre.getData());
            if (pre.getParent()==node){
                if (pre.getLnode()!=null){
                    TreeNode preLnode = pre.getLnode();
                    preLnode.setParent(node);
                }
                node.setLnode(pre.getLnode());
            }else {
                TreeNode preParent = pre.getParent();
                preParent.setRnode(pre.getLnode());
                if (pre.getLnode()!=null){
                    TreeNode preLnode = pre.getLnode();
                    preLnode.setParent(preParent);
                }
            }
        }else if (node.getRnode()==null && node.getLnode()==null){
            TreeNode parent = node.getParent();
            if (node==parent.getLnode()){
                parent.setLnode(null);
            }else {
                parent.setRnode(null);
            }
            node.setParent(null);
        }else {
            TreeNode parent = node.getParent();
            TreeNode child = (node.getLnode()!=null)?node.getLnode():node.getRnode();
            if (node==parent.getLnode()){
                parent.setLnode(child);
            }else {
                parent.setRnode(child);
            }
            child.setParent(parent);
            node.setParent(null);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] a = {39,27,49,20,38,41,45,48,43};
        bst.insert(a);
        bst.inOrderTraversalLoop();
        bst.delete(49);
        bst.inOrderTraversalLoop();
    }
}