java二叉树遍历算法有哪些?如何操作?

2020-04-21 17:10:56 java常见问答 4285

大家是否有了解过算法呢?今天小编讲的内容知识则是Java的二叉树算法,希望大家能从今天这篇文章收获到知识哦,接下来就让我们一起来了解下吧。

二叉树的遍历有三种方式分别为如下:

先序遍历:遍历顺序规则为(根左右)

中序遍历:遍历顺序规则为(左根右)

后序遍历:遍历顺序规则为(左右根)

问题来了,什么是(根左右)呢?就是先遍历根,再遍历左孩子,最后遍历右孩子。不知道这样解释是否通俗易懂呢?

它的前序遍历顺序为:ABDGHCEIF(规则是先是根结点,再前序遍历左子树,再前序遍历右子树)

它的中序遍历顺序为:GDHBAEICF(规则是先中序遍历左子树,再是根结点,再是中序遍历右子树)

它的后序遍历顺序为:GHDBIEFCA(规则是先后序遍历左子树,再是后序遍历右子树,再是根结点)

接下来通过代码的方式进行展示:

public class BTree
{
    public int data;
    public BTree father, leftSon, rightSon;
    public static BTree root;
    public boolean hasleft()
    {
        return leftSon != null;
    }
    public boolean hasright()
    {
        return rightSon != null;
    }
    public BTree()
    {}
    //直接插入方法
    public void insert(int data)
    {
        if (root == null)
        {
            root = new BTree();
            root.data = data;
            return;
        }
        insert(data, root);
    }
    //递归插入方法
    public void insert(int data, BTree father)
    {
        //插入的数据和父节点比较大小
        int compare = data - father.data;
        if (compare == 0)
        {
            return;
        }
        //放在右边
        if (compare > 0)
        {
            //判断有没有右孩子,如果有则递归下一级
            if (father.hasright())
            {
                insert(data, father.rightSon);
            }
            else
            {
                //创建一个新的节点没有左孩子
                father.rightSon = new BTree();
                father.rightSon.data = data;
                father.rightSon.father = father;
            }
        }
        if (compare < 0)
        {
            //判断有没有左孩子,如果有则递归下一级
            if (father.hasleft())
            {
                insert(data, father.leftSon);
            }
            else
            {
                father.leftSon = new BTree();
                father.leftSon.data = data;
                father.leftSon.father = father;
            }
        }
    }
    //先序遍历
    public static void query1()
    {
        if (root == null)
        {
            return;
        }
        query1(root);
    }
    public static void query1(BTree tree)
    {
        if (tree == null)
        {
            return;
        }
        System.out.print(tree.data + "  ");
        if (tree.hasleft())
        {
            query1(tree.leftSon);
        }
        if (tree.hasright())
        {
            query1(tree.rightSon);
        }
    }
    //中序遍历
    public static void query2()
    {
        if (root == null)
        {
            return;
        }
        query2(root);
    }
    public static void query2(BTree tree)
    {
        if (tree == null)
        {
            return;
        }
        if (tree.hasleft())
        {
            query2(tree.leftSon);
        }
        System.out.print(tree.data + "  ");
        if (tree.hasright())
        {
            query2(tree.rightSon);
        }
    }
    //后序遍历
    public static void query3()
    {
        if (root == null)
        {
            return;
        }
        query3(root);
    }
    public static void query3(BTree tree)
    {
        if (tree == null)
        {
            return;
        }
        if (tree.hasleft())
        {
            query3(tree.leftSon);
        }
        if (tree.hasright())
        {
            query3(tree.rightSon);
        }
        System.out.print(tree.data + "  ");
    }
    public static void main(String[] args)
    {
        BTree tree = new BTree();
        tree.insert(56);
        tree.insert(23);
        tree.insert(98);
        tree.insert(33);
        tree.insert(54);
        tree.insert(44);
        tree.insert(66);
        tree.insert(53);
        tree.insert(75);
        tree.insert(11);
        tree.insert(32);
        tree.insert(76);
        BTree.query1();
        System.out.println();
        BTree.query2();
        System.out.println();
        BTree.query3();
    }
}

结果为:

56 23 12 54 53 45 32 98 67 76 99

12 23 32 45 53 54 56 67 76 98 99

12 32 45 53 54 23 76 67 99 98 56

以上就是今天所讲的二叉树相关的Java常见问答,如果想要了解跟多,请继续关注本网站。