二叉树实现 - Java

二叉树实现 - Java

Scroll Down

写这篇完全就是为了后面的作业用的φ(>ω<*) ,代码都有测试过,虽然目前没有发现什么bug.

代码:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * author      : lwj
 * createTime  : 2019/2/15 20:07
 * description : Reprint please indicate the source
 */
public class BinaryTree<T> {

    private Node<T> root;   //  根结点

    public BinaryTree() {
    }

    /**
     * 获取树的根结点
     *
     * @return
     */
    public Node<T> getRoot() {
        return root;
    }

    /**
     * 判断树是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 插入结点
     *
     * @param item
     * @param parentItem 父结点的值
     * @param direction  -1表示左,1表示右
     */
    public void put(T item, T parentItem, int direction) {
        Node<T> new_node = new Node<T>(item, null, null, null);
        if (root == null) {
            root = new_node;
        } else {
            Node<T> parentNode = find(parentItem);
            if (direction == -1) {
                new_node.left = parentNode.left;
                parentNode.left = new_node;
                new_node.parent = parentNode;
            }
            if (direction == 1) {
                new_node.right = parentNode.right;
                parentNode.right = new_node;
                new_node.parent = parentNode;
            }
        }
    }

    /**
     * 向指定结点插入左孩子
     *
     * @param parent
     * @param item
     */
    public void insertLeft(T parent, T item) {
        Node<T> par_node = find(parent);
        Node<T> left_node = new Node<T>(item, null, null, null);
        if (par_node.left != null) {
            left_node.left = par_node.left;
            par_node.left = left_node;
            par_node.left.parent = left_node;
            left_node.parent = par_node;
        } else {
            par_node.left = left_node;
            left_node.parent = par_node;
        }
    }

    /**
     * 向指定结点插入右孩子
     *
     * @param parent
     * @param item
     */
    public void insertRight(T parent, T item) {
        Node<T> par_node = find(parent);
        Node<T> right_node = new Node<T>(item, null, null, null);
        if (par_node.right != null) {
            right_node.right = par_node.right;
            par_node.right = right_node;
            par_node.right.parent = right_node;
            right_node.parent = par_node;
        } else {
            par_node.right = right_node;
            right_node.parent = par_node;
        }
    }

    /**
     * 查找指定结点
     *
     * @param item
     * @return
     */
    public Node<T> find(T item) {
        return this.find(root, item);
    }

    private Node<T> find(Node<T> root, T item) {
        Queue<Node<T>> queue = new LinkedList<Node<T>>();
        Node<T> q_node = null;
        queue.offer(root);
        while (!queue.isEmpty()) {
            q_node = queue.poll();
            if (q_node.item.equals(item)) {
                return q_node;
            }
            if (q_node.left != null) {
                queue.offer(q_node.left);
            }
            if (q_node.right != null) {
                queue.offer(q_node.right);
            }
        }
        return null;
    }

    /**
     * 删除结点
     *
     * @param item
     * @return
     */
    public boolean delete(T item) {
        Node<T> temp_node = find(item);
        if (temp_node == null) {
            return false;
        }
        Node<T> par = temp_node.parent;
        //如果要删除的是根结点
        if (temp_node.item == this.root.item) {
            clear();
        }
        //左子树
        else if (par.left.item.equals(temp_node.item)) {
            par.left = null;
        }
        //右子树
        else {
            par.right = null;
        }
        return true;
    }

    /**
     * 清空树
     */
    public void clear() {
        this.root = null;
    }

    /**
     * 获得二叉树的高
     *
     * @return
     */
    public int getHeight() {
        return getHeight(this.root);
    }

    private int getHeight(Node<T> root) {
        if (root == null) {
            return 0;
        } else {
            int leftH = getHeight(root.left);
            int rightH = getHeight(root.right);
            return (leftH > rightH ? leftH : rightH) + 1;
        }
    }

    /**
     * 求根结点到指定结点的路径
     *
     * @param item
     */
    public void rootToNode(T item) {
        Node<T> p_node = find(item);
        if (p_node != null) {
            this.rootToNode(p_node);
        }
    }

    private void rootToNode(Node<T> x) {
        if (x.parent != null) {
            rootToNode(x.parent);
            System.out.print("->" + x.item);
        } else {
            System.out.print(x.item);
        }
    }

    /**
     * 获取左子树
     *
     * @param item
     * @return
     */
    public Node<T> getLeft(T item) {
        Node<T> p_node = find(item);
        return p_node == null ? null : p_node.left;
    }

    /**
     * 获取右子树
     *
     * @param item
     * @return
     */
    public Node<T> getRight(T item) {
        Node<T> p_node = find(item);
        return p_node == null ? null : p_node.right;
    }

    /**
     * 统计叶子结点的个数
     *
     * @return
     */
    public int statisticsLeafNodeCount() {
        return this.statisticsLeafNodeCount(root);
    }

    private int statisticsLeafNodeCount(Node<T> x) {
        int count = 0;
        if (x == null) {
            return 0;
        } else if (x.left == null && x.right == null) {
            return 1;
        } else {
            count = statisticsLeafNodeCount(x.left) + statisticsLeafNodeCount(x.right);
        }
        return count;
    }

    /**
     * 判断是否是叶子结点
     *
     * @param item
     * @return
     */
    public boolean isLeafNode(T item) {
        Node<T> p_node = find(item);
        if (p_node.left == null && p_node.right == null) {
            return true;
        }
        return false;
    }

    /**
     * 获取所有结点个数
     *
     * @return
     */
    public int statisticsNodeCount() {
        Node<T> p_node = root;
        return this.statisticsNodeCount(p_node);
    }

    private int statisticsNodeCount(Node<T> x) {
        if (x == null) {
            return 0;
        } else {
            return statisticsNodeCount(x.left) + statisticsNodeCount(x.right) + 1;
        }
    }

    /**
     * 将广义表转换为二叉树
     *
     * @param gLists
     */
    public void createBinTreeByGLists(String gLists) {
        this.root = (Node<T>) this.createByGList(gLists);
    }

    private Node<Character> createByGList(String gLists) {
        Node<Character> root_node = null;
        Node<Character> curr_node = null;
        Stack<Node<Character>> stack = new Stack<Node<Character>>();
        int flag = 0;
        final int left = 1;
        final int right = 2;
        for (int i = 0; i < gLists.length(); i++) {
            char ch = gLists.charAt(i);
            switch (ch) {
                case '(':
                    flag = left;
                    stack.push(curr_node);
                    break;
                case ',':
                    flag = right;
                    break;
                case ')':
                    stack.pop();
                    break;
                case '^':
                    break;
                default:
                    curr_node = new Node<Character>(ch, null, null, null);
                    if (root_node == null) {
                        root_node = curr_node;
                    } else {
                        if (flag == 1) {
                            stack.peek().left = curr_node;
                        } else {
                            stack.peek().right = curr_node;
                        }
                    }
            }
        }
        return root_node;
    }

    /**
     * 将二叉树表示为广义表
     */
    public void toGeeneralizedList() {
        this.toGeeneralizedList(root);
    }

    private void toGeeneralizedList(Node<T> root) {
        System.out.print(root.item);
        if (root.left != null) {
            System.out.print("(");
            toGeeneralizedList(root.left);
            if (root.right == null) {
                System.out.print(",^)");
            }
        }
        if (root.right != null) {
            if (root.left == null) {
                System.out.print("(^");
            }
            System.out.print(",");
            toGeeneralizedList(root.right);
            System.out.print(")");
        }
    }

    /**
     * 判断是否为完全二叉树
     *
     * @return
     */
    public boolean isCompleteTree() {
        return this.isCompleteTree(root);
    }

    private boolean isCompleteTree(Node<T> root) {
        Node<T> p_node = null;
        Queue<Node<T>> queue = new LinkedList<Node<T>>();
        queue.offer(root);
        while ((p_node = queue.poll()) != null) {
            queue.offer(p_node.left);
            queue.offer(p_node.right);
        }
        while (!queue.isEmpty()) {
            p_node = queue.poll();
            if (p_node != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 根据后序和中序遍历建立二叉树
     *
     * @param post 后续遍历集合
     * @param in   中序遍历集合
     * @return 树的根结点
     */
    private Node<T> buildTree(T[] post, T[] in) {
        int len = in.length;
        return dfs(0, len - 1, 0, len - 1, post, in);
    }

    /**
     * 递归构建树
     *
     * @param inl
     * @param inr
     * @param postl
     * @param postr
     * @param post
     * @param in
     * @return
     */
    private Node<T> dfs(int inl, int inr, int postl, int postr, T[] post, T[] in) {
        if (inl > inr || postl > postr) {
            return null;
        }

        T val = post[postr];
        int k = 0;
        for (int i = inl; i < inr + 1; i++) {
            if (in[i] == val) {
                k = i;
                break;
            }
        }

        Node<T> root = new Node<T>(val, null, null, null);
        // 第 4 个参数是计算出来的,依据:两边区间长度相等
        root.left = dfs(inl, k - 1, postl, k - 1 - inl + postl, post, in);
        // 第 3 个参数是计算出来的,依据:两边区间长度相等
        root.right = dfs(k + 1, inr, postr + k - inr, postr - 1, post, in);
        return root;
    }

    /**
     * 前序遍历
     */
    public void preOrderTraverse() {
        this.preOrderTraverse(root);
    }

    private void preOrderTraverse(Node<T> root) {
        if (root != null) {
            System.out.print(root.item);
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
        }
    }

    /**
     * 前序遍历非递归
     */
    public void preOrderByStack() {
        this.preOrderByStack(root);
    }

    private void preOrderByStack(Node<T> root) {
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Node<T> temp = root;
        while(temp != null || !stack.empty()){
            if(temp != null){
                System.out.print(temp.item);
                stack.push(temp);
                temp = temp.left;
            }else {
                temp = stack.pop();
                temp = temp.right;
            }
        }
    }

    /**
     * 中序遍历
     */
    public void inOrderTraverse() {
        this.inOrderTraverse(root);
    }

    private void inOrderTraverse(Node<T> root) {
        if (root != null) {
            inOrderTraverse(root.left);
            System.out.print(root.item);
            inOrderTraverse(root.right);
        }
    }

    /**
     * 中序遍历非递归
     */
    public void inOrderByStack(){
        this.inOrderStack(root);
    }

    private void inOrderStack(Node<T> root){
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Node<T> temp= root;
        while(temp != null || !stack.empty()){
            if(temp != null){
                stack.push(temp);
                temp = temp.left;
            }else {
                temp = stack.pop();
                System.out.print(temp.item);
                temp = temp.right;
            }
        }
    }

    /**
     * 后序遍历
     */
    private void postOrderTraverse() {
        this.postOrderTraverse(root);
    }

    public void postOrderTraverse(Node<T> root) {
        if (root != null) {
            postOrderTraverse(root.left);
            postOrderTraverse(root.right);
            System.out.print(root.item);
        }
    }

    /**
     * 后序遍历非递归
     */
    public void postOrderByStack(){
        this.postOrderByStack(root);
    }

    private void postOrderByStack(Node<T> root){
        Stack<Node<T>> stack  = new Stack<Node<T>>();
        Node<T> temp = root;
        Node<T> lastNode = root;
        while(temp != null || !stack.empty()){
            while(temp != null){
                stack.push(temp);
                temp = temp.left;
            }
            temp = stack.peek();
            if(temp.right == null || temp.right == lastNode){
                System.out.print(temp.item);
                stack.pop();
                lastNode = temp;
                temp = null;
            }else {
                temp = temp.right;
            }
        }
    }

    /**
     * 层序遍历二叉树
     */
    public void levelOrderTraverse() {
        this.levelOrderTraverse(root);
    }

    private void levelOrderTraverse(Node<T> root) {
        Node<T> temp = null;
        Queue<Node<T>> queue = new LinkedList<Node<T>>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            temp = queue.poll();
            System.out.print(temp.item);
            if (null != temp.left)
                queue.offer(temp.left);
            if (null != temp.right) {
                queue.offer(temp.right);
            }
        }
        System.out.println();
    }

    /**
     * 树的结点类
     *
     * @param <T>
     */
    private class Node<T> {
        Node<T> left;
        Node<T> right;
        Node<T> parent;
        T item;

        public Node(T item, Node<T> left, Node<T> right, Node<T> parent) {
            this.left = left;
            this.right = right;
            this.parent = parent;
            this.item = item;
        }
    }

    public static void main(String[] args) {
//        String str = "ABC.D.E..FG...H";
//        char[] arr = str.toCharArray();
//        BinaryTree<Character> binaryTree = new BinaryTree<Character>();
//        for (int i = 0; i < arr.length; i++) {
//            if (arr[i] != '.') {
//                if (i % 2 == 0) {
//                    binaryTree.put(arr[i], arr[(i - 1) / 2], 1);
//                } else {
//                    binaryTree.put(arr[i], arr[(i - 1) / 2], -1);
//                }
//            }
//        }
//        binaryTree.rootToNode('L');
//        System.out.println(binaryTree.statisticsLeafNodeCount());
//        System.out.println(binaryTree.getHeight());
//        System.out.println(binaryTree.statisticsNodeCount());
//        System.out.println(binaryTree.isCompleteTree());
//        String str = "A(B(D(^,G),^),C(E,F))";
//        BinaryTree<Character> binaryTree = new BinaryTree<Character>();
//        binaryTree.createBinTreeByGLists(str);
//        binaryTree.inOrderTraverse();

//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        Character[] post = new Character[n];
//        Character[] in = new Character[n];
//        for (int i = 0; i < n; i++) {
//            post[i] = String.valueOf(sc.nextInt()).charAt(0);
//        }
//        for (int i = 0; i < n; i++) {
//            in[i] = String.valueOf(sc.nextInt()).charAt(0);
//        }
//        System.out.print("Preorder:");
//        BinaryTree<Character> binaryTree = new BinaryTree<>();
//        binaryTree.preOrderTraverse(binaryTree.buildTree(post, in));
//        System.out.println();
    }
}
支付宝 微信