Java 数据结构之二叉树

二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

二叉树的实现之前、中、后序遍历

代码实现：

public class BinaryTree {
          
   

    private TreeNode root;//根节点

    public BinaryTree() {
          
   
        root = null;
    }

    public void preOrder(TreeNode root) {
          
   
        /********** Begin *********/
        if (root != null){
          
   
            System.out.println(root.item);
            if (root.leftChild != null) preOrder(root.leftChild);
            if (root.rightChild != null) preOrder(root.rightChild);
        }else {
          
   
            throw new RuntimeException("该数为空数");
        }
        /********** End *********/
    }
    
	public void inOrder(TreeNode root) {
          
   
        /********** Begin *********/
        if (root != null){
          
   
            if (root.leftChild != null) inOrder(root.leftChild);
            System.out.println(root.item);
            if (root.rightChild != null) inOrder(root.rightChild);
        }else {
          
   
            throw new RuntimeException("该数为空数");
        }
        /********** End *********/
    }
   
    public void postOrder(TreeNode root) {
          
   
        /********** Begin *********/
        if (root != null){
          
   
            if (root.leftChild != null) postOrder(root.leftChild);
            if (root.rightChild != null) postOrder(root.rightChild);
            System.out.println(root.item);
        }else {
          
   
            throw new RuntimeException("该数为空数");
        }
        /********** End *********/
    }

    /**
     *以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
          
   
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
          
   
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
          
   
                root = node;
            } else {
          
   
                int j = k / 2;
                if (k % 2 == 0) {
          
   
                    tmp[j].leftChild = node;
                } else {
          
   
                    tmp[j].rightChild = node;
                }
            }
        }

        return root;
    }

    public static class TreeNode {
          
   
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;

        public TreeNode(int item) {
          
   
            this(null, null, item);
        }

        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
          
   
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }

}