二叉树层次如何计算?二叉树是什么?

XIAO 2020-04-19 16:44:21 java常见问答 7783

众所周知,树在计算机领域是一种重要的非线性数据结构,直观的看,它还是数据元素按分支关系组织起来的结构呢,那下面小编跟大家带来聊聊一种名叫二叉树的数据结构,一起来看看二叉树层次又是如何计算的呢?

那么何为二叉树呢?是这样的,树是有很多种, 其中每个节点最多只能有两个子节点的叫二叉树,二叉树的子节点又分为左节点和右节点,如果呢,二叉树的所有叶子节点全部都在最后一层, 并且结点总数=2^n-1, n为层数, 则我们称之为满二叉数,如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续, 倒数第二层的叶子节点在右边连续, 我们就称之为完全二叉树。

计算二叉树层次示例如下:

import java.util.LinkedList;
import java.util.List;
public class BinaryTreeDeep
{
    public static void main(String[] args)
    {
        Tree tree1 = new Tree("1");
        Tree tree2 = new Tree("2");
        Tree tree3 = new Tree("3");
        Tree tree4 = new Tree("4");
        Tree tree5 = new Tree("5");
        Tree tree7 = new Tree("7");
        Tree tree8 = new Tree("8");
        Tree tree9 = new Tree("9");
        Tree tree10 = new Tree("10");
        tree1.setLeft(tree2);
        tree1.setRight(tree3);
        tree2.setLeft(tree4);
        tree3.setRight(tree5);
        tree5.setLeft(tree7);
        tree7.setLeft(tree8);
        tree8.setRight(tree9);
        tree4.setRight(tree10);
        /*
               1
             2    3
           4         5
             10         7
                      8
                          9
         */
        int deep = getDeep(tree1);
        System.out.println("深度(递归)是" + deep);
        int deep1 = getDeep1(tree1);
        System.out.println("深度(非递归)是" + deep1);
        System.out.println("层次遍历是:");
        levelTraversal(tree1);
    }
    private static int getDeep(Tree root)
    {
        if (null == root)
        {
            return 0;
        }
        if (null == root.getLeft() && null == root.getRight())
        {
            return 1; //如果只有他自己就是1
        }
        int left = 0;
        int right = 0;
        if (null != root.getLeft())
        {
            left = getDeep(root.getLeft());
        }
        if (null != root.getRight())
        {
            right = getDeep(root.getRight());
        }
        int deep = Math.max(left, right) + 1;
        return deep;
    }
    private static int getDeep1(Tree root)
    {
        if (null == root)
        {
            return 0;
        }
        List < Tree > nodes = new LinkedList < > ();
        ((LinkedList < Tree > ) nodes)
        .offer(root);
        int current = 0;
        int deep = 0;
        int levelNodeSize = 0;
        while (nodes.size() > 0)
        {
            levelNodeSize = nodes.size(); //当前层节点的个数
            current = 0;
            while (current < levelNodeSize)
            {
                Tree tmp = ((LinkedList < Tree > ) nodes)
                    .poll();
                if (null != tmp.getLeft())
                {
                    ((LinkedList < Tree > ) nodes)
                    .offer(tmp.getLeft());
                }
                if (null != tmp.getRight())
                {
                    ((LinkedList < Tree > ) nodes)
                    .offer(tmp.getRight());
                }
                current++;
            }
            deep++;
        }
        return deep;
    }
    private static void levelTraversal(Tree root)
    {
        List < Tree > nodes = new LinkedList < > ();
        ((LinkedList < Tree > ) nodes)
        .offer(root);
        while (!nodes.isEmpty())
        {
            Tree tmp = ((LinkedList < Tree > ) nodes)
                .poll();
            System.out.print(tmp.getRoot() + " ");
            if (null != tmp.getLeft())
            {
                ((LinkedList < Tree > ) nodes)
                .offer(tmp.getLeft());
            }
            if (null != tmp.getRight())
            {
                ((LinkedList < Tree > ) nodes)
                .offer(tmp.getRight());
            }
        }
        System.out.println("");
    }
}
class Tree
{
    private String root;
    private Tree left;
    private Tree right;
    public Tree(String root)
    {
        this.root = root;
    }
    public String getRoot()
    {
        return root;
    }
    public void setRoot(String root)
    {
        this.root = root;
    }
    public Tree getLeft()
    {
        return left;
    }
    public void setLeft(Tree left)
    {
        this.left = left;
    }
    public Tree getRight()
    {
        return right;
    }
    public void setRight(Tree right)
    {
        this.right = right;
    }
}

那么以上就是有关二叉树的所有内容了,如果还想了解更多java一些知识问答那么记得关注本站消息哦,更多精彩内容等你来了解。