二叉树操作

树节点

public class TreeNode<T> {
    private T data;
    private TreeNode<T> left;
    private TreeNode<T> right;

    public T getData() {
        return data;
    }

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

    public TreeNode<T> getLeft() {
        return left;
    }

    public void setLeft(TreeNode<T> left) {
        this.left = left;
    }

    public TreeNode<T> getRight() {
        return right;
    }

    public void setRight(TreeNode<T> right) {
        this.right = right;
    }
}

逐行顺序解析二叉树

public static List<Integer> parseBinaryTree(TreeNode<Integer> treeNode) {
        Queue<TreeNode<Integer>> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();

        queue.offer(treeNode);

        while (!queue.isEmpty()) {
            TreeNode<Integer> currentTreeNode = queue.poll();
            if (currentTreeNode != null) {
                list.add(currentTreeNode.getData());
                queue.offer(currentTreeNode.getLeft());
                queue.offer(currentTreeNode.getRight());
            }
        }
        return list;
    }

前序遍历二叉树

public static List<Integer> preOrder(TreeNode<Integer> treeNode) {
        List<Integer> list = new ArrayList<>();

        if (treeNode != null) {
            list.add(treeNode.getData());
        }
        if (treeNode != null && treeNode.getLeft() != null) {
            list.addAll(preOrder(treeNode.getLeft()));
        }
        if (treeNode != null && treeNode.getRight() != null) {
            list.addAll(preOrder(treeNode.getRight()));
        }
        return list;
    }

中序遍历二叉树

public static List<Integer> inOrder(TreeNode<Integer> treeNode) {
        List<Integer> list = new ArrayList<>();

        if (treeNode != null && treeNode.getLeft() != null) {
            list.addAll(inOrder(treeNode.getLeft()));
        }
        if (treeNode != null) {
            list.add(treeNode.getData());
        }
        if (treeNode != null && treeNode.getRight() != null) {
            list.addAll(inOrder(treeNode.getRight()));
        }
        return list;
    }

后序遍历二叉树

public static List<Integer> postOrder(TreeNode<Integer> treeNode) {
        List<Integer> list = new ArrayList<>();

        if (treeNode != null && treeNode.getLeft() != null) {
            list.addAll(postOrder(treeNode.getLeft()));
        }
        if (treeNode != null && treeNode.getRight() != null) {
            list.addAll(postOrder(treeNode.getRight()));
        }
        if (treeNode != null) {
            list.add(treeNode.getData());
        }
        return list;
    }

删除指定数值的节点

public static TreeNode<Integer> deleteNode(TreeNode<Integer> treeNode, int value) {
        if (treeNode != null) {
            if (treeNode.getData() == value) {
                treeNode = null;
            } else {
                treeNode.setLeft(deleteNode(treeNode.getLeft(), value));
                treeNode.setRight(deleteNode(treeNode.getRight(), value));
            }
        }
        return treeNode;
    }

前序遍历顺序存储的完全二叉树

public static List<Integer> preOrderArray(int[] arr, int startIndex) {
        List<Integer> list = new ArrayList<>();

        if (arr == null || arr.length == 0 || startIndex >= arr.length) {
            return list;
        }
        list.add(arr[startIndex]);
        if (startIndex * 2 + 1 < arr.length) {
            list.addAll(preOrderArray(arr, startIndex * 2 + 1));
        }
        if (startIndex * 2 + 2 < arr.length) {
            list.addAll(preOrderArray(arr, startIndex * 2 + 2));
        }
        return list;
    }

把数组转化成二叉树

public static TreeNode arrayToBinaryTree(Integer[] arr, int index) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        TreeNode root = null;

        if (index < arr.length) {
            Integer value = arr[index];

            if (value == null) {
                return null;
            }

            root = new TreeNode();
            root.setData(value);
            root.setLeft(arrayToBinaryTree(arr, 2 * index + 1));
            root.setRight(arrayToBinaryTree(arr, 2 * index + 2));
            return root;
        }
        return root;
    }