一文看懂数据结构中的树 值得收藏
|
具体来讲，我们会先访问根结点1再访问其左孩子2，接着是2的左孩子3，到达叶子结点回溯一步，访问2的右孩子4，进一步回溯，继续顺序访问5，6和7。在输出遍历结果时，据父结点值相对子结点输出顺序的不同，深度优先遍历又可细分为先序、中序和后序遍历三种情况。 先序遍历 即直接按照我们对结点的访问顺序输出遍历结果即实现，父结点值被最先输出。代码：  中序遍历  中序遍历输出结果为：3–2–4–1–6–5–7。 左孩子值最先输出，然后是父结点，最后是右孩子。对应代码如下：  后序遍历 后序遍历输出结果为：3–4–2–6–7–5–1. 左右孩子值依次输出，最后是父结点，对应代码如下：  广度优先搜索 (BFS) BFS：按照结点深度逐层遍历树结构。  再拿上面的图来实际解释这种方法： 逐层每层从左到右进行遍历，对应遍历结果为：1–2–5–3–4–6–7。对应代码如下：  你应该已经注意到了，我们要借助先进先出(FIFO)的队列(queue)结构完成操作，具体的出入队列顺序如下图所示：  二叉搜索树 二叉搜索树又名有序二叉树，结点元素按固定次序排布，使得我们可以在进行查找等操作时使用二分搜索提高效率。——维基百科 它最明显的特征是父结点值大于左子树任意结点值，小于右子树任意结点值。  上图以三个二叉树为例，哪个才是正确的呢? A 左右子树需要进行交换。B 满足条件，是二叉搜索树。C 值为4的结点需要移至3的右孩子处 接下来进行二叉搜索插入、结点检索、结点删除以及平衡的解释。 插入 假设以这种顺序插入结点: 50, 76, 21, 4, 32, 100, 64, 52。50会是我们初始的根结点。  再依次进行如下操作： 76 大于50，置于右边21 小于 50, 置于左边4 置于21左边 最终一气呵成我们会得到下面这棵树：  发现规律了么?像开车一样，从根结点驶入，待插入值大于当前结点值向右开否则向左开知道找到空位停车入库。(嘀嘀嘀，老司机) 代码实现也很简单：  这个算法最牛逼的地方在于他的递归部分，你知道是哪几行吗? 结点检索 其实结合我们的插入操作，检索的方法就显而易见，依旧从根结点开始，小于对应结点值左转，大于右转，等于报告找到，走到叶子结点都没找到 gg，就报没有该元素。例如我们想知道下图中有没有52这个值：  代码如下：  删除: 移除并重构 删除操作要更复杂一些，因为要处理三种不同情况： 情景 #1：叶子结点  是最简单的情况，直接删除就好. 情景 #2：只有左孩子或右孩子  该情景等价于链表上的结点删除，把当前结点删除并让其子结点替换自己原来位置。 情景 #3：同时具有左右孩子的结点  找到该结点右子树中最小值所在的结点，剔除要删除的当前结点并把最小值结点提升到空缺位置。 一些别的操作 清零：将三个属性全部置None即可。  （编辑：威海站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
