java二叉树算法,二叉树常用算法实现详解

KLQ 2020-07-14 15:13:31 java常见问答 4261

你知道java二叉树算法都有哪些吗?下面就给大家整理了一下二叉树常用算法实现的内容,一起来详细的看一下吧!

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 < TreeNode > 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 < TreeNode > 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 < TreeNode > stack1 = new Stack < > ();
        Stack < Integer > 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 < Integer > posOrder2(TreeNode node)
    {
        ArrayList < Integer > list = new ArrayList < > ();
        if (node != null)
        {
            Stack < TreeNode > 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 < depth; i++)
        {
            //根据第几层得到所处第几层的所有元素
            leveOrder(node, i);
        }
    }
    /**
     * 层序遍历(非递归)
     * @param node
     */
    public void levelOrder1(TreeNode node)
    {
        if (node == null) return;
        Queue < TreeNode > queue = new LinkedList < > ();
        queue.add(node);
        TreeNode node1;
        while (!queue.isEmpty())
        {
            node1 = queue.poll();
            System.out.println(node1.data);
            if (node1.leftNode != null) queue.offer(node1.leftNode);
            if (node1.RightNode != null) queue.offer(node1.RightNode);
        }
    }
    /**
     * 得到第几层的所有元素
     * @param node
     * @param level
     */
    public void leveOrder(TreeNode node, int level)
    {
        if (node == null || level < 1) return;
        if (level == 1)
        {
            System.out.println(node.data);
            return;
        }
        leveOrder(node.leftNode, level - 1);
        leveOrder(node.RightNode, level - 1);
    }
    /**
     * 二叉树的深度
     * @param node
     * @return
     */
    public int depth(TreeNode node)
    {
        if (node == null) return 0;
        int l = depth(node.leftNode);
        int r = depth(node.RightNode);
        if (l > r) return l + 1;
        else return r + 1;
    }
    /**
     * 通过层序遍历构建二叉树
     * @param str 层序遍历的任意参数
     * @return 二叉树
     */
    TreeNode buildTreeByLevelOrder(String str)
    {
        String[] nodeArr = str.split(",");
        List < TreeNode > nodelist = new LinkedList < > ();
        for (String s: nodeArr)
        {
            nodelist.add(new TreeNode(Integer.valueOf(s)));
        }
        System.out.println(nodelist.size());
        for (int index = 0; index < nodelist.size() / 2 - 1; index++)
        {
            //编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号,所以还要+1
            //这里父节点有1(2,3),2(4,5),3(6,7),4(8,9) 但是最后一个父节点有可能没有右子节点 需要单独处理
            nodelist.get(index)
                .leftNode = (nodelist.get(index * 2 + 1));
            nodelist.get(index)
                .RightNode = (nodelist.get(index * 2 + 2));
        }
        //单独处理最后一个父节点 因为它有可能没有右子节点
        int index = nodelist.size() / 2 - 1;
        nodelist.get(index)
            .leftNode = (nodelist.get(index * 2 + 1)); //先设置左子节点
        if (nodelist.size() % 2 == 1)
        { //如果有奇数个节点,最后一个父节点才有右子节点
            nodelist.get(index)
                .RightNode = (nodelist.get(index * 2 + 2));
        }
        return nodelist.get(0);
    }
    /**
     * 根据前序遍历还原二叉树
     * (在前序序列化的时候,如果遇到为null的节点,则在字符串后面添加“#,”
     当反序列化时,会进行判断,当前的位置是否为"#",如果为#则不会创建子节点)
     */
    int index = -1;
    TreeNode Deserialize(String str)
    {
        if (str.length() == 0)
            return null;
        index++;
        int len = str.length();
        if (index >= len)
        {
            return null;
        }
        String[] strr = str.split(",");
        TreeNode node = null;
        if (!strr[index].equals("#"))
        {
            node = new TreeNode(Integer.valueOf(strr[index]));
            node.leftNode = Deserialize(str);
            node.RightNode = Deserialize(str);
        }
        return node;
    }
    /**
     * 反转二叉树
     * 或者
     * 建立一颗二叉树的镜像(如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。)
     * @param root
     */
    public void Mirror(TreeNode root)
    {
        if (root == null)
        {
            return;
        }
        if ((root.leftNode == null) && (root.RightNode == null))
        {
            return;
        }
        TreeNode temp = root.leftNode;
        root.leftNode = root.RightNode;
        root.RightNode = temp;
        Mirror(root.leftNode);
        Mirror(root.RightNode);
    }
    /**
     * 克隆一颗二叉树
     * @param root
     * @return
     */
    public static TreeNode cloneTree(TreeNode root)
    {
        TreeNode node = null;
        if (root == null) return null;
        node = new TreeNode(root.data);
        node.leftNode = cloneTree(root.leftNode);
        node.RightNode = cloneTree(root.RightNode);
        return node;
    }
    /**
     * 判断两颗二叉树是否相同
     * @param root1
     * @param root2
     * @return
     */
    public boolean sameTree2(TreeNode root1, TreeNode root2)
    {
        //树的结构不一样
        if ((root1 == null && root2 != null) || (root1 != null && root2 == null))
            return false;
        //两棵树最终递归到终点时
        if (root1 == null && root2 == null)
            return true;
        if (Integer.valueOf(root1.data)
            .compareTo(Integer.valueOf(root2.data)) != 0)
            return false;
        else
            return sameTree2(root1.leftNode, root2.leftNode) && sameTree2(root1.RightNode, root2.RightNode);
    }
}

以上的算法总结来源于剑指offer以及一些日常积累。

以上内容源于网络,仅供参考,希望可以对大家有帮助。

更多和java二叉树算法有关的内容,请继续关注奇Q工具网的常见问题栏目来了解吧。

推荐阅读:

非递归中序遍历二叉树java实现

求二叉树深度的递归算法java

二叉树节点数该怎么计算?有几种算法?