java二叉树遍历算法二叉树的基本算法查找算法你知道吗

  java二叉树遍历算法实现二叉树基础算法二叉树搜索算法基础算法

  

  你知道java二叉树算法是什么吗？下面就为大家整理一下常用的二叉树算法的内容java二叉树遍历算法二叉树的基本算法查找算法你知道吗，一起来详细看看吧！

<p><pre class="brush:java;toolbar:false">public class BinaryTree
{
    private TreeNode root;
    /**
     * 插入值到二叉树中
     * @param value
     */
    public void insert(int value)
    {
        TreeNode node = new TreeNode(value);
        TreeNode curr = root;
        TreeNode parent;
        if (root == null)
        {
            root = new TreeNode(value);
            return;
        }
        while (true)
        {
            parent = curr;
            if (curr.data > value)
            {
                curr = curr.leftNode;
                if (curr == null)
                {
                    parent.leftNode = node;
                    return;
                }
            }
            else
            {
                curr = curr.RightNode;
                if (curr == null)
                {
                    parent.RightNode = node;
                    return;
                }
            }
        }
    }
    /**
     * 查找指定值的树节点
     * @param value
     * @return
     */
    public TreeNode findNode(int value)
    {
        TreeNode curr = root;
        while (curr.data != value)
        {
            if (curr.data > value)
            {
                curr = curr.leftNode;
            }
            else curr = curr.RightNode;
        }
        if (curr == null) return null;
        return new TreeNode(curr.data);
    }
    /**
     * 前序遍历（递归）
     * @param node
     */
    public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            System.out.println(node.data);
            preOrder(node.leftNode);
            preOrder(node.RightNode);
        }
    }
    /**
     * 前序遍历（非递归）
     * @param node
     */
    public void preOrder1(TreeNode node)
    {
        Stack  stack = new Stack  ();
        while (node != null || !stack.empty())
        {
            while (node != null)
            {
                System.out.println(node.data);
                stack.push(node);
                node = node.leftNode;
            }
            if (!stack.empty())
            {
                node = stack.pop();
                node = node.RightNode;
            }
        }
    }
    /**
     * 中序遍历（递归）
     * @param node
     */
    public void midOrder(TreeNode node)
    {
        if (node != null)
        {
            midOrder(node.leftNode);
            System.out.println(node.data);
            midOrder(node.RightNode);
        }
    }
    /**
     * 中序遍历（非递归）
     * @param node
     */
    public void midOrder1(TreeNode node)
    {
        Stack  stack = new Stack  ();
        while (node != null || !stack.empty())
        {
            while (node != null)
            {
                stack.push(node);
                node = node.leftNode;
            }
            if (!stack.empty())
            {
                node = stack.pop();
                System.out.println(node.data);
                node = node.RightNode;
            }
        }
    }
    /**
     * 后序遍历
     * @param node
     */
    public void posOrder(TreeNode node)
    {
        if (node != null)
        {
            posOrder(node.leftNode);
            posOrder(node.RightNode);
            System.out.println(node.data);
        }
    }
    /**
     * 后序遍历（非递归）
     * @param node
     */
    public void posOrder1(TreeNode node)
    {
        Stack  stack1 = new Stack  ();
        Stack  stack2 = new Stack  ();
        while (node != null || !stack1.empty())
        {
            while (node != null)
            {
                stack1.push(node);
                stack2.push(0);
                node = node.leftNode;
            }
            while (!stack1.empty() && stack2.peek() == 1)
            {
                stack2.pop();
                System.out.println(stack1.pop()
                    .data);
            }
            if (!stack1.empty())
            {
                stack2.pop();
                stack2.push(1);
                node = stack1.peek();
                node = node.RightNode;
            }
        }
    }
    /**
     * 后序遍历（非递归）
     * 前序遍历  根--左--右
     * 后序遍历  左--右--根
     * 借用前序遍历算法思想 修改成 根--右--左，然后反转得到  左--右--根
     * @param node
     * @return
     */
    public ArrayList  posOrder2(TreeNode node)
    {
        ArrayList  list = new ArrayList  ();
        if (node != null)
        {
            Stack  stack = new Stack  ();
            stack.push(node);
            while (!stack.empty())
            {
                TreeNode node1 = stack.pop();
                list.add(node1.data);
                if (node1.leftNode != null) stack.push(node1.leftNode);
                if (node1.RightNode != null) stack.push(node1.RightNode);
            }
            Collections.reverse(list);
        }
        return list;
    }
    /**
     * 层序遍历（递归）
     * @param node
     */
    public void levelOrder(TreeNode node)
    {
        if (node == null) return;
        //计算深度
        int depth = depth(node);
        for (int i = 0; i