b树是二叉树吗?b树是什么树?

TheDisguiser 2020-05-27 21:29:43 java常见问答 5310

b树你知道吗?对于对计算机不是非常熟悉的人来说,可能都没听说过,下面让我一起来了解一下什么是b树及它和二叉树有什么联系吧。

一、什么是b树?

b树是二叉树吗

B树是一种平衡多叉树,一般适用于外查找,它也可以看作是对2-3查找树的一种扩展,即它允许每个节点有M-1个子节点。

B树特点

1.根节点至少有两个子节点

2.每个节点有M-1个key,并且以升序排列

3.位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

4.其它节点至少有M/2个子节点

2-3树

2-3树是一种最简单的b树结构,它的每个非叶节点都有两个或三个子女,而且所有叶都在统一层上。2-3树不是二叉树,它的节点可以拥有3个孩子。2-3树与满二叉树相似。若某棵2-3树不包含3-节点,则看上去像满二叉树,其所有内部节点都可有两个孩子,所有的叶子都在同一级别。另一方面,2-3树的一个内部节点确实有3个孩子,故比相同高度的满二叉树的节点更多。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数,即至少有2^h-1个节点。换一个角度分析,包含n的节点的2-3树的高度不大于[log2(n+1)](即包含n个节点的二叉树的最小高度)。

如:下图显示高度为3的2-3树。包含了两个孩子的节点称为2-节点,再二叉树中的节点都是2-节点;包含三个孩子的节点称为3-节点。

b树是二叉树吗

数据项放入2-3树节点中的规则是:

(1)2-节点有两个孩子,必含一个数据项,其查找关键字大于左孩子的查找关键字,而小于右孩子的查找关键字。

(2)3-节点有三个孩子 ,必含两个数据项,其查找关键字S和L满足下列关系:S大于左孩子的查找关键字,而小于中孩子的查找关键字;L大于中孩子的查找关键字,而小于右孩子的查找关键字。

(3)叶子可以包含一个或两个数据项。

B树因为其分支结点同样存储着数据,所以我们如果要找到具体的数据,就要进行一次中序遍历按序来扫。

二、b树是二叉树吗?

不是,二叉树是一种各个节点至多只有两个子树的树结构。它的子树一般被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树子树有着左右之分,且它的顺序不能随意颠倒。所以,b树不是二叉树,它是一种适用于外查找的树,它是平衡多叉树。

以上就是关于b树是不是二叉树的所有内容啦,更多相关java常见问答知识,请持续关注我们来了解吧。

推荐阅读:

b树与b+树的区别是什么?各自有什么优点?

重建二叉树(思路和实现)

将二叉树变换为源二叉树的镜像如何实现?思路和实现