java二叉树怎么转成数组?java怎么实现二叉树?

阳光 2021-01-14 22:09:48 java常见问答 6891

java二叉树是非常重要的,它相关的每一个知识点,java人员都要熟练的运用,这是作为Java人员的基本素质,那么java二叉树怎么转成数组?下面我们就来讲解一下。

将一个数组转换成一个二叉树的java实现,如下:

import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
/**
* 二叉树的生成
*
* @author DangerShi
*/
public class TreeBuilder
{
    class TreeNode
    {
        Object data;
        TreeNode left;
        TreeNode right;
        public TreeNode()
        {}
        public TreeNode(Object data, TreeNode left, TreeNode right)
        {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode arrayToBTree(Object[] arrs)
    {
        if (arrs == null || arrs.length == 0)
        {
            return new TreeNode();
        }
        List nodes = new ArrayList < > (arrs.length);
        for (Object obj: arrs)
        {
            TreeNode treeNode = new TreeNode();
            treeNode.data = obj;
            nodes.add(treeNode);
        }
        for (int i = 0; i < arrs.length / 2 - 1; i++)
        {
            TreeNode node = nodes.get(i);
            node.left = nodes.get(i * 2 + 1);
            node.right = nodes.get(i * 2 + 2);
        }
        // 只有当总节点数是奇数时,最后一个父节点才有右子节点
        int lastPNodeIndex = arrs.length / 2 - 1;
        TreeNode lastPNode = nodes.get(lastPNodeIndex);
        lastPNode.left = nodes.get(lastPNodeIndex * 2 + 1);
        if (arrs.length % 2 != 0)
        {
            lastPNode.right = nodes.get(lastPNodeIndex * 2 + 2);
        }
        return nodes.get(0);
    }
    @Test
    public void test()
    {
        /**
        * 1
        * 2 3
        * 4 5 6 7
        */
        TreeNode treeNode = arrayToBTree(new Object[]
        { 1, 2 , 3, 4, 5, 6, 7});
    }
}

java怎么实现二叉树?

二叉树是一个递归的数据结构,每个节点最多有两个子节点。

通常二叉树是二分查找树,每个节点它的值大于或者等于在它左子树节点上的值,小于或者等于在它右子树节点上的值。如下图

java二叉树怎么转成数组?java怎么实现二叉树?.png

为了实现二叉树,我们使用一个Node类来表示节点,节点存储int类型的值,还有对子节点的引用。

package com.java.node.BinaryTree;
public class Node
{
    int data;
    Node left;
    Node right;
    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

然后添加树的root节点

package com.java.node.BinaryTree;
public class BinaryTree
{
    Node root;
}

通常的操作

添加节点

首先我们必须找到新节点的位置,是为了保持树排序。我们必须从root节点开始,必须遵循下面的规则:

如果新节点小于当前的值,我们将会进入左子树。

如果新节点大于当前的节点。我们将会进入右子树。

当当前的节点是null时,我们已经到达叶子节点,我们可以添加新节点到这个位置。

我们将会创建递归方法做添加节点操作

private Node addNode(Node current, int value)
{
    if (current == null)
    {
        return new Node(value);
    }
    if (value < current.data)
    {
        current.left = addNode(current.left, value);
    }
    else if (value > current.data)
    {
        current.right = addNode(current.right, value);
    }
    else
    {
        return current;
    }
    return current;
}
public void addNode(int value)
{
    root = addNode(root, value);
}

可以使用方法创建一个二叉树了

public BinaryTree createBinaryTree()
{
    BinaryTree bt = new BinaryTree();
    bt.addNode(6);
    bt.addNode(4);
    bt.addNode(8);
    bt.addNode(10);
    return bt;
}

查找一个节点

private boolean containNode(Node current, int value)
{
    if (current == null)
    {
        return false;
    }
    if (value == current.data)
    {
        return true;
    }
    return value < current.data ? containNode(current.left, value) : containNode(current.right, value);
}
public boolean containNode(int value)
{
    return containNode(root, value);
}

删除一个节点

private Node deleteNode(Node current, int value)
{
    if (current == null)
    {
        return null;
    }
    if (value == current.data)
    {
        if (current.left == null && current.right == null)
        {
            return null;
        }
        if (current.left == null)
        {
            return current.right;
        }
        if (current.right == null)
        {
            return current.left;
        }
        int smallestValue = findSmallestValue(current.right);
        current.data = smallestValue;
        current.right = deleteNode(current.right, smallestValue);
        return current;
    }
    if (value < current.data)
    {
        current.left = deleteNode(current.left, value);
        return current;
    }
    current.right = deleteNode(current.right, value);
    return current;
}
private int findSmallestValue(Node root)
{
    return root.left == null ? root.data : findSmallestValue(root.right);
}

从文章中,我们可以看出java二叉树的知识还是非常重要的,有难点也有易点,要想熟练运用,还是要下功夫才行哦!最后大家如果想要了解更多java常见问题知识,敬请关注奇Q工具网。

推荐阅读:

java二叉树的遍历算法代码是什么?

java有多少个函数?什么是java函数?

学java需要什么软件?java常用软件介绍