在Java中树层是很重要的，在树层深处又有二叉树层，大家知道二叉树层吗?二叉树层是什么?它又该怎么计算呢?一起来看看吧。

首先我们先来了解一点基础吧，二叉树层，是指在计算机科学中的一种树结构，这种树结构每个结点最多有两个子树，它们通常被称为左子树(left subtree)与右子树(right subtree)。

在二叉树层中，一棵深度为k，且具有2^k-1个结点的二叉树，被称为满二叉树。这种树的特点是每一层的结点数都是最大结点数，并且在一棵二叉树中，除最后一层外，若其余层都是满的，或者最后一层是满的，又或者是在右边缺少连续若干结点的话，这种二叉树就叫完全二叉树。二叉树层中，具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

二叉树层基本概念

二叉树通常是递归定义的，结点有左右子树之分，并且在逻辑上有五种基本心态。

树类型

1.完全二叉树：设二叉树的高度为n，除n 层外，其余各层 (1～h-1) 的结点数都达到最大个数，第n层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2.满二叉树：满二叉树是除了叶结点外每一个结点都有左右子叶并且叶子结点都处在最底层的二叉树。

3.平衡二叉树：平衡二叉树又被称为AVL树(区别于AVL算法)，它是一棵二叉排序树，具有以下性质：它是空树，它的左右子树的高度差绝对值不超过1，并且左右两个子树都是平衡二叉树。

二叉树层次遍历计算

1、首先将二叉树的根节点进入队列中，判断队列不为NULL。

2、打印输出该节点存储的元素。

3、判断节点如果有子树(左子树、右子树)，就将孩子进入队列中。

4、循环以上操作，直到 BT->lchild == NULL、BT->rchild=NULL。

例：

#include

#include

#
define MaxSize 1024
typedef struct Node
{ //定义二叉链
    struct Node * lchild; //指向左孩子节点
    char data; //数据元素
    struct Node * rchild; //指向右孩子节点
}
BTNode; //struct Node 的别名
typedef struct Quene
{ //定义顺序队
    int front; //队头指针
    BTNode * data[MaxSize]; //存放队中元素
    int rear; //队尾指针
}
SqQueue; //struct Queue 的别名
//初始化队列
void initQueue(SqQueue * & q)
{
    q = (SqQueue * ) malloc(sizeof(SqQueue)); //分配一个空间
    q - > front = q - > rear = -1; //置 -1
}
//判断队列是否为空
bool emptyQueue(SqQueue * & q)
{
    if (q - > front == q - > rear)
    { //首指针和尾指针相等，说明为空
        return true; //返回真
    }
    else
    {
        return false; //返回假
    }
}
//进队列
bool enQueue(SqQueue * & q, BTNode * & BT)
{
    if (q - > rear == MaxSize - 1)
    { //判断队列是否满了
        return false; //返回假
    }
    q - > rear++; //头指针加 1
    q - > data[q - > rear] = BT; //传值
    return true; //返回真
}
//出队列
bool deQueue(SqQueue * & q, BTNode * & BT)
{
    if (q - > front == q - > rear)
    { //判断是否空了
        return false; //返回假
    }
    q - > front++; //尾指针加 1
    BT = q - > data[q - > front]; //取值
    return true; //返回真
}
//创建二叉树
int createBTNode(BTNode * & BT, char * str, int n)
{
    char ch = str[n]; //把第 n 个字符赋给ch,方便后面判断
    n = n + 1;
    if (ch != '')
    { //如果 ch 不等于结束符就继续创建，否则就结束
        if (ch == '#')
        { //以 # 号代表 NULL，下面没有了
            BT = NULL;
        }
        else
        {
            BT = new BTNode; //新建一个二叉链
            BT - > data = ch; //把字符存入二叉链
            n = createBTNode(BT - > lchild, str, n); //左递归创建
            n = createBTNode(BT - > rchild, str, n); //右递归创建
        }
    }
    return n; //返回 n,记录字符串使用到哪里了
}
//先序遍历
void preOrder(BTNode * & BT)
{
    if (BT != NULL)
    { //判断不为空
        printf("%c", BT - > data); //访问根节点
        preOrder(BT - > lchild); //递归，先序遍历左子树
        preOrder(BT - > rchild); //递归，先序遍历右子树
    }
}
//中序遍历
void inOrder(BTNode * & BT)
{
    if (BT != NULL)
    {
        inOrder(BT - > lchild);
        printf("%c", BT - > data);
        inOrder(BT - > rchild);
    }
}
//后序遍历
void postOrder(BTNode * & BT)
{
    if (BT != NULL)
    {
        postOrder(BT - > lchild);
        postOrder(BT - > rchild);
        printf("%c", BT - > data);
    }
}
//层次遍历
void levelOrder(BTNode * & BT)
{
    SqQueue * q; //定义队列
    initQueue(q); //初始化队列
    if (BT != NULL)
    {
        enQueue(q, BT); //根节点指针进队列
    }
    while (emptyQueue(q) != true)
    { //队不为空循环
        deQueue(q, BT); //出队时的节点
        printf("%c", BT - > data); //输出节点存储的值
        if (BT - > lchild != NULL)
        { //有左孩子时将该节点进队列
            enQueue(q, BT - > lchild);
        }
        if (BT - > rchild != NULL)
        { //有右孩子时将该节点进队列
            enQueue(q, BT - > rchild);
        } //一层一层的把节点存入队列
    } //当没有孩子节点时就不再循环
}
int main()
{
    //例子：ABDH###E##CF##G##
    BTNode * BT;
    printf("输入字符串：");
    char * str = (char * ) malloc(sizeof(char) * 1024);
    scanf("%s", str);
    createBTNode(BT, str, 0);
    printf("二叉树建立成功
");
    printf("先序遍历结果：");
    preOrder(BT);
    printf("
");
    printf("中序遍历结果：");
    inOrder(BT);
    printf("
");
    printf("后序遍历结果：");
    postOrder(BT);
    printf("
");
    printf("层序遍历结果：");
    levelOrder(BT);
    printf("
");
    return 0;
}

小结：

创建二叉树是以 “#” 为结束符NULL。

上例结果应为：ABCDEFGH

以上就是关于二叉树层的一些知识，如果你想了解更多关于java一些知识问答的知识的话，请多多关注本站吧。