数据结构之树之二叉树，平衡二叉树，B树

怼烎@ 2022-05-29 03:12 163阅读 0赞

2018年第一篇博客，不知道怎么写开头。

树常用来表示层级结构。算了还是直接一点吧。

**二叉树**

1.二叉树的每个节点最多有两个子树（度最大为2，不存在度大于2的节点）。

2.二叉树的子树有左右之分，不能互相颠倒。

最重要的就是二叉树的性质：

1.非空二叉树，第i层的节点总数不超过2^i-1，i>=1;

2.深度为h的二叉树最多有2^h-1个节点，最少有h个节点。

3.对于任意一棵二叉树，如果其叶子节点数为n0,度为2的节点数为n2,则n0=n2+1;

4。给定N个节点，就能构成h(N)种不同的二叉树，其中h(n)为卡特兰树的第n项，h(n)=C(2\*n,n)/(n-1)\\

5。设有i个节点，I为所有支点的道路长度总和，J为叶的道路长度总和J=i+2^i;

完全二叉树：

具有N个节点的完全二叉树的深度为log2(n+1)

具有n个节点的完全二叉树， 如果各节点用顺序方式存储，则节点之间有如下关系：

若I为节点编号，则I>1，则其父节点编号为I/2;

如果2I<=N,则其左孩子为的编号为2I,如果2I>N，则无左孩子。

如果2I+1<=N,则其右孩子的节点编号为2I+1，若2I+1>N，则无右孩子。

然后，就是二叉树的遍历方式了，中序遍历，先序遍历，后序遍历。

我这里不举例子了。。。。

**二叉搜索树，二叉排序树，二叉查找树---BST：**

BST定义：

若左子树不为空，左子树上 所有的值均小于它的根节点的值。

若右子树不为空，右子树上的所有的值均大于它的根节点的值。

左右子树也分别为二叉排序树。

BST的初始化过程就是排序的过程，树初始化完成后，进行中序遍历就是排序后的数据。二叉查找树 的高度决定了二叉查找树的查找效率。时间复杂度是O(logN),最坏是O(N)。（删除和插入，查找算法就不记录了。百度一大把，天下文章一大抄。。。。。）

但是，当原始的数据近似于有序的时候，就是二叉排序排序最糟糕的时候了，BST就会趋近类似链表。

所以就有了

**平衡二叉树**。

平衡二叉树是一棵空树或者左右两个子树的平衡因子的绝对值不超过1，并且左右子树都是平衡二叉树。

常用算法：红黑树，AVL树。

常用操作：插入，删除。

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*这里会补上插入删除的图示\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

自己总结，如果有问题，请告知。感激不尽。

插入的时候，最困难的就是左旋和右旋了。什么时候旋，怎么旋，搞清了这两个问题，就没有什么难点了。

A.旋不旋转看平衡因子。

B.左子树的高度为正整数，右子树的高度为负整数，则平衡因子大于0 ，右旋，小于0，左旋

C：以谁为基准旋转：

父左左--中间节点，直接右旋  
         父左右----以右为基准，右旋两次，旋转完毕之后，左右子树交换位置  
         父右右----以中间节点，直接左旋  
         父右左----左旋两次，左右子树交换位置

**B-tree：**B树(没点B树，怎么敢说自己是程序员。。。。。。)

B树，是平衡的多路查找树。

一棵度为m的B树称为m阶B树。B树一定会满足一下性质：

要么是一棵空树,

要么满足：

1.每个非叶子节点最多有m棵子树。

2.除根节点外，所有非叶子节点至少有ceil(m/2)棵子树。

3.所有的非终端节点中包含如下信息的数据：  
（n,A0,K1,A1,K2,A2,….,Kn,An）   
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，  
Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.   
（\[m/2\]-1<=n<=m-1）

n 为关键码的个数。

4.所有叶子节点都出现同一个层次上，并且不带有信息，可以看作是外部节点或者是查找失败的节点，实际上这些节点都不存在，指向这些节点的指针为空。

常用操作：插入，删除。

/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*这里应该有插入删除的操作过程解析，以后补\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/

tips：B树源于B-Tree,所以B-树，就是B树。没有"B减数"，没点B树。。。。。。。。。

2018-03-15  20:52  方小白 --畅游大厦

如果有误，敬请指正。不尽感激。

## 最后 ##

如果你觉得写的还不错，就关注下公众号呗，关注后，有点小礼物回赠给你。  
你可以获得5000+电子书，java,springCloud,adroid,python等各种视频教程，IT类经典书籍，各种软件的安装及破解教程。  
希望一块学习，一块进步！  
![20190901125800286.jpg][]

[20190901125800286.jpg]: https://img-blog.csdnimg.cn/20190901125800286.jpg