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

阳光 2021-01-12 17:09:01 java常见问答 5933

java最重要的就是会写代码并且保证代码成功的运行,这样才是一个完整的代码,最近有人想了解java二叉树的知识,想知道java二叉树的遍历算法代码是什么?那么接下来,我们就来给大家讲解一下这方面的内容。

代码如下:

package package2;
public class BinaryTree
{
    int data; //根节点数据
    BinaryTree left; //左子树
    BinaryTree right; //右子树
    public BinaryTree(int data) //实例化二叉树类
    {
        this.data = data;
        left = null;
        right = null;
    }
    public void insert(BinaryTree root, int data)
    { //向二叉树中插入子节点
        if (data > root.data) //二叉树的左节点都比根节点小
        {
            if (root.rightnull)
            {
                root.right = new BinaryTree(data);
            }
            else
            {
                this.insert(root.right, data);
            }
        }
        else
        { //二叉树的右节点都比根节点大
            if (root.leftnull)
            {
                root.left = new BinaryTree(data);
            }
            else
            {
                this.insert(root.left, data);
            }
        }
    }
}

当建立好二叉树类后可以创建二叉树实例,并实现二叉树的先根遍历,中根遍历,后根遍历,代码如下:

package package2;
public class BinaryTreePreorder
{
    public static void preOrder(BinaryTree root)
    { //先根遍历
        if (root != null)
        {
            System.out.print(root.data + "-");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    public static void inOrder(BinaryTree root)
    { //中根遍历
        if (root != null)
        {
            inOrder(root.left);
            System.out.print(root.data + "–");
            inOrder(root.right);
        }
    }
    public static void postOrder(BinaryTree root)
    { //后根遍历
        if (root != null)
        {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + "—");
        }
    }
    public static void main(String[] str)
        {
            int[] array = {12 , 76, 35, 22, 16 , 48, 90, 46, 9, 40};
            BinaryTree root = new BinaryTree(array[0]); //创建二叉树
            for (int i = 1; i < array.length; i++)
            {
                < p = "" >
                    root.insert(root, array[i]); //向二叉树中插入数据
            }
            System.out.println(“先根遍历:”);
            preOrder(root);
            System.out.println();
            System.out.println(“中根遍历:”);
            inOrder(root);
            System.out.println();
            System.out.println(“后根遍历:”);
            postOrder(root);

当运行上面的程序后结果如下:

先根遍历:

12-9-76-35-22-16-48-46-40-90-

中根遍历:

9–12–16–22–35–40–46–48–76–90–

后根遍历:

9—16—22—40—46—48—35—90—76—12—

二叉树的实现方式有哪些?

1.第一类数组实现

用数组root[]存储结点值,在这种实现当中,对于编号为k的节点,其左子节点的编号为2*k,右子节点的编号为2*k + 1,另外确定根节点的编号为1.毫无疑问,这种实现极易产生巨大的空间浪费,比如对于一个只有一条链的树,假设该树含有31个节点,存储这31个节点却需要开一个2^30的数组,因此此方法较少使用。(此处的2^30是指数值,由2k计算出来的数值过大)

2.结构体+指针实现

用结构体指针u来表示一个节点,其中u->v表示该节点的权值,u->left和u->right分别指向该节点的左右子节点,初始化全部为NULL,若需用到该节点,则申请空间,否则视为无子节点!就这样互相联系成一颗结构体指针二叉树!节省空间,但是容易出现指针悬挂或者未知的指针内存错误。

3..第二类数组实现

对于一棵有n个节点树,只需要开一个大小为n的数组,节点按照出现顺序依次编号,这么一来,每个节点的左右节点的编号就无法通过2*k,2*k+1的形式来直接确定了,这时就需要数组lch[maxn] , rch[maxn];其中lch[u]表示u节点的左子节点的编号,因此通过u = lch[u]就可以访问到u节点的左子节点,rch[u]的含义同理。另外,用value[u]表示编号为u节点的权值,如此一来,申请新节点的newnode函数与初始化的newtree函数写法就变得不同了,具体见代码。(此处只需结点个数个数组即可,并不计算数值!)

从文章中我们可以看出,java二叉树的相关内容还是很重要的,这也是在工作中会运用到的,所以这些代码大家一定要熟知并会运用哦!最后大家如果想要了解更多java常见问题知识,敬请关注奇Q工具网。

推荐阅读:

java初级面试题有哪些?java初级面试题分享

fastjson反序列化漏洞绕过方式有哪些?

java怎么做出界面?实例讲解