心里有点树不？

虽然没有植过树，但是学到过很多树的结构，比如二叉树、B+ 树，红黑树。每次面试必问，恰逢植树节，本来是想讲解 B 树，但发现必须要理解了二叉树之后才能更好地讲解 B 树，所以先给大家讲下二叉树是什么，后面文章再更新 B 树。

大白话讲解二叉树

比如现在有个数组，存放了很多用户的名字，需要从这个数组中找到包含指定的用户名，最快的方式是什么?

我们会想到二分查找，虽然这种方式很快，但要达到最快还需要有个条件：数组有序。

如果我们能把插入用户名的时候直接给他排序，那最后的结构就是有序结构。

因此有人设计了一种数据结构：二叉查找树，也叫做二叉树。

如下图所示：这是一种二叉树结构。有四个术语需要说明：节点、左节点、右节点、根节点。

其中每个红色圆球都算一个节点，节点左下边相连接的节点叫做左节点，而右边相连的叫做右节点。比如 Alice 被称作 Herry 节点的左节点，Mike 被称作 Herry 的右节点。而根节点只会有一个，属于最上面的节点，上图中的 Herry 就是根节点。

对于其中每个节点，左子节点的值都比它小，而右子节点的值都比它大。比如 Alice < Herry < Mike。

假设现在我们想要查找 Ivy，首先检查根节点，发现比 Herry 大，所以往下继续找，找到了根节点的右节点 Mike，再继续找，比 Mike 小，所以找 Mike 的左节点，正好找到 Ivy。

二叉查找树中查找节点时，平均运行时间是 O(logn)，最糟糕的情况下所需时间为 O(n); 而在有序数组中查找时，及时最糟糕的情况，二分查找最多也是 O(logn)，所以你可能会觉得，二分查找比二叉查找要快很多。但是二叉查找树的插入和删除操作的速度是要快很多的。这里我们做一个对比：

（编辑：阜新站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!