Java实现二叉树的创建以及二叉树的三种遍历方式

以一个整数数组为例,创建一个完全二叉树，并采用递归方式遍历二叉树

二叉树结点（Node）

public class Node {
    private int data;
    private Node leftNode;
    private Node rightNode;

    public Node(int newdata) {
        this.data = newdata;
        this.leftNode = null;
        this.rightNode = null;
    }
    
    ... get 和 set...
}

创建二叉树以及三种遍历方式的方法

接口 (TreeNode)


import java.util.List;

public interface TreeNode {
    /**
     *  创建一个二叉树
    **/
    List<Node> createBinTree(int[] arr);
    /**
    *  前序遍历
    *  若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树
    **/
    void preOrderTraverse(Node node);

    /**
     *  中序遍历
     *  若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根节点），中序遍历左子树，
     *  然后是访问根节点，最后是中序遍历右子树
     **/
    void inorderTraversal(Node node);

    /**
     *  后序遍历
     *  若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子数，最后是访问根节点
     **/
    void postorderTraversal(Node node);

}

其实现类

import java.util.ArrayList;
import java.util.List;

public class TreeNodeImplents implements  TreeNode {

    @Override
    public List<Node> createBinTree(int[] arr) {
        List<Node> nodeList = new ArrayList<>();
        // 将数值转化为结点
        for (int i = 0; i <arr.length ; i++) {
            nodeList.add(new Node(arr[i]));
        }
        // 对lastparent-1个结点建立二叉树关系
        for (int parentIndex = 0; parentIndex <arr.length/2-1 ; parentIndex++) {
            //左子树
            nodeList.get(parentIndex).setLeftNode(nodeList.get(parentIndex * 2+1));
            //右子树
            nodeList.get(parentIndex).setRightNode(nodeList.get(parentIndex *2 +2));
        }
        // 最后一个父节点，可能只有左子树，拿出单独处理
        int lastParentIndex = arr.length / 2 -1;
        //添加最后一个父节点的左子树
        nodeList.get(lastParentIndex).setLeftNode(nodeList.get(lastParentIndex * 2 +1));
        // 假如最后一个父节点存在右子树，则添加该父节点的右子树
        if (arr.length % 2==1){
            nodeList.get(lastParentIndex).setRightNode(nodeList.get(lastParentIndex * 2 + 2));
        }
        return nodeList;
    }

    @Override
    public void preOrderTraverse(Node node) {
        if (node == null) return;
        System.out.print(node.getData() + " ");
        preOrderTraverse(node.getLeftNode());
        preOrderTraverse(node.getRightNode());
    }

    @Override
    public void inorderTraversal(Node node) {
        if (node == null)return;
        inorderTraversal(node.getLeftNode());
        System.out.print(node.getData() + " ");
        inorderTraversal(node.getRightNode());
    }

    @Override
    public void postorderTraversal(Node node) {
        if (node == null)return;
        postorderTraversal(node.getLeftNode());
        postorderTraversal(node.getRightNode());
        System.out.print(node.getData() + " ");
    }
}

测试类

public class BinTreeDemo {

   public static void main(String[] args) {
       int [] arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
       TreeNode treeNode = new TreeNodeImplents();
       List<Node> binTree = treeNode.createBinTree(arr);
//     前序遍历
       System.out.println("前序遍历");
       treeNode.preOrderTraverse(binTree.get(0));
       System.out.println();
//     中序遍历为
       System.out.println("中序遍历为");
       treeNode.inorderTraversal(binTree.get(0));
       System.out.println();
//     后序遍历
       System.out.println("后序遍历");
       treeNode.postorderTraversal(binTree.get(0));
   }
}