Java實作二叉樹

最近在leetcode上刷樹和dfs的題，簡單題中經常遇到二叉樹這種資料結構，因為實在太菜，肉眼debug太困難，為了找錯方便我在本地建立了與leetcode上相同的二叉樹結構，提供了層序建立二叉樹和遞回建立二叉樹兩種方法，希望能對刷leetcode的新手們有幫助！

下面直接附上代碼：

TreeNode

一個基本的二叉樹結點，

package Tree;

/***
 * 二叉樹結點
 * @date 2020/12/18
 * @author xuning
 * @param <E>
 */
public class TreeNode<E> {
    E val;
    public TreeNode left = null;
    public TreeNode right = null;
    public TreeNode(){};
    TreeNode(E x) { val = x; }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

BinaryTree

package Tree;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 基本二叉樹結構
 * 當使用陣列傳入資料時，默認遞回建樹
 * 也可以建立空樹，選擇遞回或者層序建立二叉樹
 * @param <E>
 * @date 2020/12/18
 * @author xuning
 */
public class BinaryTree<E> {
    /**
     * 根結點
     */
    private TreeNode<E> root = null;

    /**
     * 建立二叉樹時，用于快取資料的堆疊空間
     */
    private LinkedList<E> stack = null;

    /**
     * 保存二叉樹資料的串列
     */
    private List<E> elements = new ArrayList<>();

    /**
     * 無參構造方法
     */
    public BinaryTree(){
    }

    /**
     * 有參構造方法，默認左遞回建立二叉樹，
     * 因此需要傳入左遞回順序的資料
     * @param data 左遞回順序的陣列資料
     */
    public BinaryTree(E[] data){
        this.stack = new LinkedList<E>(Arrays.asList(data));
        CreateBinaryTree();
    }

    /**
     * 獲取根結點
     * @return root 回傳根結點
     */
    public TreeNode<E> getRoot(){
        return this.root;
    }

    /**
     * 設定根結點
     * @param root 根結點
     */
    public void setRoot(TreeNode<E> root){
        this.root = root;
    }

    /**
     * 左遞回建立二叉樹
     * @return
     */
    private void CreateBinaryTree(){
        if(!stack.isEmpty()){
            this.root = recursiveCreateBinaryTree(root, stack);
        }else{
            this.root = null;
        }
    }

    /***
     * 左遞回建立二叉樹，需要傳入左遞回順序的二叉樹資料
     * @param data
     */
    public void recursiveCreateBinaryTree(E[] data){
        this.stack = new LinkedList<E>(Arrays.asList(data));
        if(!stack.isEmpty()){
            this.root = recursiveCreateBinaryTree(this.root, this.stack);
        }else{
            this.root = null;
        }
    }
    /**
     * 左遞回建立二叉樹, 核心演算法
     * @param node
     * @param stack
     * @return 回傳根節點
     */
    private TreeNode<E> recursiveCreateBinaryTree(TreeNode<E> node, LinkedList<E> stack){
        if(!stack.isEmpty()){
            E value = stack.pop();
            if(value == null){
                node = null;
            }else{
                node = new TreeNode<>();
                node.val = value;
                node.left = recursiveCreateBinaryTree(node.left, stack);
                node.right = recursiveCreateBinaryTree(node.right, stack);
            }
        }else{
            return null;
        }
        return node;
    }


    /**
     * 層序建立二叉樹，需要傳入層序建立的二叉樹資料
     * @param data 快取資料的陣列
     * @return
     */
    public void SequenceCreateBinaryTree(E[] data){
        this.stack = new LinkedList<E>(Arrays.asList(data));
        if(!stack.isEmpty()){
            root = SequenceCreateBinaryTree(root, stack);
        }else{
            root = new TreeNode<E>();
        }
    }

    /**
     * 層序建立二叉樹，核心演算法
     * @param rootNode 根節點
     * @return 回傳根結點
     */
    private TreeNode<E> SequenceCreateBinaryTree(TreeNode<E> rootNode, LinkedList<E> stack){
        LinkedList<TreeNode> queue = new LinkedList<>();
        if(!stack.isEmpty()){
            rootNode = new TreeNode<>();
            rootNode.val = stack.pop();
            queue.addFirst(rootNode);
        }else{
            return null;
        }

        while (!stack.isEmpty()){
            TreeNode currentNode = queue.removeLast();
            E leftValue = stack.pop();
            TreeNode<E> leftNode = null;
            if(leftValue != null){
                leftNode = new TreeNode<>();
                leftNode.val = leftValue;
                queue.addFirst(leftNode);
            }
            currentNode.left = leftNode;
            E rightValue = stack.pop();
            TreeNode<E> rightNode = null;
            if(rightValue != null){
                rightNode = new TreeNode<>();
                rightNode.val = rightValue;
                queue.addFirst(rightNode);
            }
            currentNode.right = rightNode;
        }
        return rootNode;
    }


    /**
     * 先序遍歷
     */
    public void preorder(){
        System.out.print("先序遍歷：");
        this.preorder(root);
    }

    /**
     * 先序遍歷
     * @param node
     */
    private void preorder(TreeNode<E> node){
        if(node == null){
            return;
        }
        System.out.print(node.val+" ");
        this.preorder(node.left);
        this.preorder(node.right);
    }

    /**
     * 后序遍歷
     */
    public void postorder(){
        System.out.print("后序遍歷：");
        this.postorder(root);
    }

    /**
     * 后序遍歷
     * @param node
     */
    private void postorder(TreeNode<E> node){
        if(node == null){
            return;
        }
        this.postorder(node.right);
        this.postorder(node.left);
        System.out.print(node.val + " ");
    }

    /**
     * 中序遍歷
     */
    public void inorder(){
        System.out.print("中序遍歷：");
        this.inorder(this.root);
    }

    /**
     * 中序遍歷
     * @param node
     */
    private void inorder(TreeNode<E> node){
        if(node == null){
            return;
        }
        this.inorder(node.left);
        System.out.print(node.val + " ");
        this.inorder(node.right);
    }

    /**
     * 獲取二叉樹資料元素
     * @return List 回傳具有二叉樹資料元素的串列
     */
    public List<E> getElements(){
        getElementList(root);
        return elements;
    }

    /**
     * 采用先序遍歷的方式，獲取二叉樹資料元素
     * @param root 回傳以左遞回順序的二叉樹資料元素
     */
    private void getElementList(TreeNode<E> root){
        if(root == null){
            this.elements.add(null);
            return;
        }
        this.elements.add(root.val);
        getElementList(root.left);
        getElementList(root.right);
    }


    /**
     * 獲取二叉樹的最大深度
     * @return 二叉樹深度
     */
    public int maxDepth(){
        return maxDepth(this.root);
    }

    /***
     * 獲取該二叉樹的深度
     * @param root
     * @return 回傳二叉樹深度
     */
    private int maxDepth(TreeNode root) {
        // 如果到達葉子節點回傳0；
        if(root == null) {return 0;}
        // 左遞回查找左子樹深度
        int left = maxDepth(root.left);
        // 右遞回查找右子樹深度
        int right = maxDepth(root.right);
        // 回傳最大深度并加1
        return Math.max(left, right) + 1;
    }

    @Override
    public String toString() {
        return "BinaryTree{" +
                "root=" + root +
                '}';
    }
}

測驗樣例

import Tree.BinaryTree;
import Tree.TreeNode;
import list.ListNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 遞回建樹資料
        Integer[] data = {1,2,4,null,null,null,3,null,null};
        // 層序建立二叉樹資料
        Integer[] data1 = {1,2,3,null,null,null,null};
        // 遞回建立二叉樹
        TestOneBinaryTree(data);
        // 層序建立二叉樹
        TestTwoBinaryTree(data1);
        // 遞回建立二叉樹
        TestThreeBinaryTree(data);
        BinaryTree<Integer> binaryTree = new BinaryTree<>(data);
        System.out.println(binaryTree);
    }

    public static void TestOneBinaryTree(Integer[] data){
        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>(data);
        binaryTree.preorder();
        System.out.println();
        binaryTree.inorder();
        System.out.println();
        binaryTree.postorder();
        System.out.println("\n二叉樹資料：");
        List<Integer> elements = binaryTree.getElements();
        System.out.println(elements);
        int depth = binaryTree.maxDepth();
        System.out.println("該二叉樹最大深度："+depth);
    }

    public static void TestTwoBinaryTree(Integer[] data){
        System.out.println();
        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
        // 呼叫層序建立二叉樹方法
        binaryTree.SequenceCreateBinaryTree(data);
        binaryTree.preorder();
        System.out.println();
        binaryTree.inorder();
        System.out.println();
        binaryTree.postorder();
        System.out.println("\n二叉樹資料：");
        List<Integer> elements = binaryTree.getElements();
        System.out.println(elements);
        int depth = binaryTree.maxDepth();
        System.out.println("該二叉樹最大深度："+depth);
    }

    public static void TestThreeBinaryTree(Integer[] data){
        System.out.println();
        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
        // 呼叫層序建立二叉樹方法
        binaryTree.recursiveCreateBinaryTree(data);
        binaryTree.preorder();
        System.out.println();
        binaryTree.inorder();
        System.out.println();
        binaryTree.postorder();
        System.out.println("\n二叉樹資料：");
        List<Integer> elements = binaryTree.getElements();
        System.out.println(elements);
        int depth = binaryTree.maxDepth();
        System.out.println("該二叉樹最大深度："+depth);
    }



}

運行截圖：