二叉树的度是什么意思?二叉树是什么?

TheDisguiser 2020-05-28 21:31:36 java常见问答 5967

不知道小伙伴们对二叉树知道多少呢?比如,什么是二叉树啊?二叉树的性质如它的度又是什么意思呢?下面一起来详细看看吧。

一、什么是二叉树?

想要理解二叉树是什么,首先我们要了解,树是什么?一般来说,在计算机科学里,树就是一种重要的非线性数据结构,直观的看,它是数据元素按分支关系组织起来的结构。

二叉树就是所有节点至多只有两个子树的有序树。一般它们子树的根都被称为“左子树”与“右子树”。二叉树经常被用做二叉查找树和二叉堆又或是二叉排序树。二叉树中的每个节点至多只有两颗子树,二叉树有左右之分,次序不能颠倒。

简单的说,满足以下两个条件的树就是二叉树:

1.本身是有序树;

2.树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;

如下图:

二叉树的度

二叉树的性质

二叉树具有以下性质:

1. 二叉树中,第 i 层最多有 2i-1 个结点。

2. 如果二叉树深度为 K,那么此二叉树最多只有 2K-1 个结点。

3. 二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。

性质 3 计算方法为:对于一个二叉树来说,除了度为 0 的叶子结点和度为 2 的结点,剩下的就是度为 1 的结点(设为 n1),那么总结点 n=n0+n1+n2。

同时,对于每一个结点来说都是由其父结点分支表示的,假设树中分枝数为 B,那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的,即 B=n1+2*n2。所以,n 用另外一种方式表示为 n=n1+2*n2+1。

两种方式得到的 n 值组成一个方程组,就可以得出 n0=n2+1。

二、什么是二叉树的度?

二叉树的度意思就是:二叉树中某个结点的子节点或直接后继节点的个数,1度就代表只有一个子节点或者它是单子树,2度就代表有两个子节点或是左右子树都有,二叉树就是一个连通的无环图,并且每一个顶点的度不大于3。

一般来说,在二叉树中,一棵深度为k,且有着2^k-1个节点的二叉树,就被称为满二叉树。它的特点就是每一层上的节点数都是最大节点数。且在一棵二叉树中,除最后一层外,如果其余层都是满的,并且最后一层是满的或是在右边缺少连续若干节点,则这个二叉树就为完全二叉树。

二叉树的度

以上就是二叉树相关的所有内容了,更多java常见问答相关知识,快关注我们了解吧。

推荐阅读:

二叉树遍历例题及答案详解,java入门教程

java二叉树有什么作用?有哪些实际应用?

二叉树的深度怎么算?求二叉树深度的算法(思路和代码实现)