java数据结构二叉树是什么?特点是?

TheDisguiser 2020-08-18 16:52:07 java常见问答 3306

二叉树是什么?学习java的小伙伴可能经常会听到这个词,但具体是什么又不可知,下面小编就来带你详细了解下二叉树。

二叉树概念

二叉树,指计算机中的一种树结构,这种树结构中每个结点至多只有两个子树,它们一般被称为左子树(left subtree)与右子树(right subtree)。

二叉树特点

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

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

二叉树层次遍历计算

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

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

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

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

二叉树类型

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

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

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

二叉树实例

public class BinaryTree
{
    class Node
    { //声明一个节点类
        private Comparable data; //保存具体内容
        private Node left; //保存左子树
        private Node right; //保存右字数
        private Node(Comparable data)
        {
            this.data = data;
        }
        /**
         * 添加方法
         */
        public void addNOde(Node newNode)
        {
            if (newNode.data.compareTo(this.data) < 0)
            {
                if (this.left == null)
                {
                    this.left = newNode; //放在左子树
                }
                else
                {
                    this.left.addNOde(newNode);
                }
            }
            else
            {
                if (this.right == null)
                { //放在右子树
                    this.right = newNode;
                }
                else
                {
                    this.right.addNOde(newNode);
                }
            }
        }
        /**
         * 输出信息,输出时采用中序遍历
         */
        public void printNode()
        {
            if (this.left != null)
            {
                this.left.printNode(); //先输出左子树
            }
            System.out.print(this.data + "\t");
            if (this.right != null)
            { //再输出右子数
                this.right.printNode();
            }
        }
    }
    private Node root; //根元素
    /**
     * 添加的方法
     */
    public void add(Comparable data)
    {
        Node newNode = new Node(data); //每传入一个新的内容,就声明一个节点
        if (root == null)
        {
            root = newNode; //如果是第一个元素,设置成根节点
        }
        else
        {
            root.addNOde(newNode); //确定节点是放在左面还是右面
        }
    }
    /**
     * 打印方法
     */
    public void print()
    {
        if (this.root != null)
        { //数据不为空 ,输出内容
            this.root.printNode();
        }
    }
}

以上就是本篇文章的所有内容,二叉树的概念就是这样,小伙伴们知道了吗?更多java常见问题敬请关注奇Q工具网了解详情。

推荐阅读:

redis数据结构有哪些?redis数据结构使用方式

正则表达式的规则详解

es数据结构都有哪些?有什么用处?