[数据结构与算法]Java实现二叉树

二叉树:

package Tree;

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

public class BinTree {

    private class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode()
        {
            data = 0;
            left = null;
            right = null;
        }

        public TreeNode(int e)
        {
            data = e;
            left = null;
            right = null;
        }
    }

    private TreeNode binRoot;

    public BinTree()
    {
        binRoot = null;
    }

    public TreeNode getRoot()
    {
        return binRoot;
    }

    public boolean pre_in_orderBuildTree(int[] preOrder,int[] inOrder)
    {
        int len = preOrder.length;
        if (len==0) return false;
        binRoot =  pre_in_orderDfsTree(preOrder,inOrder,0,len-1,0,len-1);
        return true;
    }

    public boolean in_post_orderBuildTree(int[] inOrder,int[] postOrder)
    {
        int len = inOrder.length;
        if (len==0) return false;
        binRoot =  in_post_orderDfsTree(inOrder,postOrder,0,len-1,0,len-1);
        return true;
    }

    private TreeNode pre_in_orderDfsTree(int[] preOrder,int[] inOrder,int l1,int h1,int l2,int h2)
    {
        if (l1 > h1) return null;
        int val = preOrder[l1];
        TreeNode root = new TreeNode(val);
        if (l1==h1) return root;

        int mid = 0;
        while(inOrder[l2+mid]!=val) mid++;

        root.left = pre_in_orderDfsTree(preOrder,inOrder,l1+1,l1+mid,l2,l2+mid-1);
        root.right = pre_in_orderDfsTree(preOrder,inOrder,l1+mid+1,h1,l2+mid+1,h2);

        return root;
    }


    private TreeNode in_post_orderDfsTree(int[] inOrder,int[] postOrder,int l1,int h1,int l2,int h2)
    {
        if (l1 > h1) return null;
        int val = postOrder[h2];
        TreeNode root = new TreeNode(val);
        if (l1==h1) return root;

        int mid = 0;
        while(inOrder[l1+mid]!=val) mid++;

        root.left = in_post_orderDfsTree(inOrder,postOrder,l1,l1+mid-1,l2,l2+mid-1);
        root.right = in_post_orderDfsTree(inOrder,postOrder,l1+mid+1,h1,l2+mid,h2-1);

        return root;
    }


    public void preOrderTree()
    {
        ArrayList<Integer> arrays = new ArrayList<>();
        preOrderDfsTree(binRoot,arrays);
        System.out.println(arrays);
    }



    private void preOrderDfsTree(TreeNode root, ArrayList<Integer> arrays)
    {
       if (root!=null)
       {
           arrays.add(root.data);
           preOrderDfsTree(root.left,arrays);
           preOrderDfsTree(root.right,arrays);
       }
    }


    public void inOrderTree()
    {
        ArrayList<Integer> arrays = new ArrayList<>();
        inOrderDfsTree(binRoot,arrays);
        System.out.println(arrays);
    }



    private void inOrderDfsTree(TreeNode root, ArrayList<Integer> arrays)
    {
        if (root!=null)
        {
            inOrderDfsTree(root.left,arrays);
            arrays.add(root.data);
            inOrderDfsTree(root.right,arrays);
        }
    }


    public void postOrderTree()
    {
        ArrayList<Integer> arrays = new ArrayList<>();
       postOrderDfsTree(binRoot,arrays);
        System.out.println(arrays);
    }



    private void postOrderDfsTree(TreeNode root, ArrayList<Integer> arrays)
    {
        if (root!=null)
        {
            postOrderDfsTree(root.left,arrays);
            postOrderDfsTree(root.right,arrays);
            arrays.add(root.data);
        }
    }


    public void inOrderTree_Stack()
    {
        TreeNode p = binRoot;
        ArrayList<Integer> arrays = new ArrayList<>();
        if (p==null)
        {
            System.out.println(arrays);
            return ;
        }
        Stack<TreeNode> s = new Stack<>();
        while(p!=null || !s.empty())
        {
            while(p!=null)
            {
                s.add(p);
                p = p.left;
            }

            if (!s.empty())
            {
                p = s.pop();
                arrays.add(p.data);
                p = p.right;
            }
        }
        System.out.println(arrays);
    }

    public void preOrderTree_Stack()
    {
        Stack<TreeNode> s = new Stack<>();
        ArrayList<Integer> arrays = new ArrayList<>();
        TreeNode p = binRoot;
        if (p==null)
        {
            System.out.println(arrays);
            return ;
        }
        while(p!=null || !s.empty())
        {
            while(p!=null) {
                s.add(p);
                arrays.add(p.data);
                p = p.left;
            }

            if (!s.empty())
            {
                p = s.pop();
                p = p.right;
            }
        }
        System.out.println(arrays);
    }


    public void  postOrderTree_Stack()
    {
       TreeNode p = binRoot;
       ArrayList<Integer> arrays = new ArrayList<>();
       Stack<TreeNode> s = new Stack<>();
       if (p==null)
       {
           System.out.println(arrays);
           return ;
       }
       s.add(p);
       while(!s.empty())
       {
           p = s.pop();
           if (p!=null)
           {
               s.push(p);
               s.push(null);
               if (p.right!=null) s.push(p.right);
               if (p.left!=null) s.push(p.left);
           }
           else
           {
               p = s.pop();
               arrays.add(p.data);
           }
       }
       System.out.println(arrays);
    }


    public void levelOrderTree()
    {
        Queue<TreeNode> q = new LinkedList<>();
        ArrayList<Integer> arrays = new ArrayList<>();
        TreeNode p = binRoot;
        if(p==null)
        {
        	System.out.println(arrays);
        	return ;
        }
        q.add(p);
        while(!q.isEmpty())
        {
            p = q.poll();
            arrays.add(p.data);
            if (p.left!=null) q.add(p.left);
            if (p.right!=null) q.add(p.right);
        }

        System.out.println(arrays);
    }

}

测试类:

package Tree;

public class TestBinTree {
    public static void main(String[] args)
    {
        BinTree bt = new BinTree();
        int[] pre = {3,9,20,15,7};
        int[] in = {9,3,15,20,7};
        int[] post = {9,15,7,20,3};
         bt.pre_in_orderBuildTree(pre,in);
        BinTree bt2 = new BinTree();
        bt2.in_post_orderBuildTree(in,post);
        bt.preOrderTree();
        bt.preOrderTree_Stack();
        bt.inOrderTree();
        bt.inOrderTree_Stack();
        bt.postOrderTree();
        bt.postOrderTree_Stack();
        bt.levelOrderTree();

    }
}