01数据结构-二叉树的深搜和广搜概念及逻辑分析

1.二叉树的遍历

1.1遍历思想

• 遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
• 对线性结构而言，只有一条搜索路径（因为每个结点均只有一个后继），故不需要另加讨论。
• 二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。
  • 按层次，父子关系，知道了父，那么就把其所有的子结点都看一遍，从上到下，从左到右，像雷达图一样。（广搜）
  • 按深度，一条道走到黑，然后再返回走另一条道（深搜），先左后右，大部分会采用递归的思想。

1.2广度遍历

如图1在访问到一个节点（A）后，会有两个问题，
1.我们可以访问这个节点的子节点（B和E）了，在访问A的时候我们要同时处理B和E吗？
2.在处理B的时候，又有新的子节点C出现了，那这个时候是处理E呢还是处理C呢？

图1

如果我们处理逻辑中只有一个缓存区，当看到A的时候，无法同时记B和E,要不然处理B 要不然处理E,如果先处理B，此时B的子节点也是我们需要处理的节点，此时先前没处理的E节点就可能被我们缓存区给冲掉了。所以这个时候就遇到了一个矛盾，处理节点的逻辑太慢了，发现节点的逻辑很快，因为当发现一个新任务的时候，往下再处理新的任务会遇到两个任务，但我们只能一次处理一个。

此时我们总结一下广度搜素时访问一个节点时（消费者），发现两个新任务（生产者），这就是我在队列那里提到的一个快速的设备和一个慢速的设备之间要想实现所有生产出的新任务在慢速的设备中都能够访问到，我们就想到引入一个队列缓存来解决这个问题

• 算法思想
  • 引入队列，将根结点入队
  • 从队列中取出队头元素，访问该结点，将该结点的所有孩子节点入队
  • 再次从队列中取出队头元素，并访问，以此重复
  • 直到队列为空，说明所有元素都遍历完成

例子：如图2有一个二叉树，我们对其进行广搜，先将A（根节点）入队，如果我们只处理完A节点就出队，那A节点后面的信息我们就少处理了，所以我们在处理新任务时，为了防止新任务返回后找不到它，此时我们要先把节点的左节点入队（如果有），再入节点的右节点（如果有）如图3，再重复此操作，处理完B后如图4，处理完E后如图5。这样就实现了广度遍历的一层一层遍历。

图2

图3

图4

图5

1.3递归

递归的概念

• 递归其实就是某个函数直接或者间接的调用了自身。这种调用方式叫递归调用。说白了还是一个函数调用。
• 既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受
  其他函数的影响。
  递归的条件
  递归函数分为两个条件，边界条件和递归条件。
• 边界条件：就是递归中止条件，避免出现死循环。也叫做递归出口。
• 递归条件：也就是递归体。将一个大问题分解为一步步小问题。也是递归调用的阶段。
  递归函数在具备这两个要素以后，才可以在有限次的计算后得出想要的结果。

这里我们先了解一下概念

1.4深度遍历

如图6，我们按照深度搜索的定义拿到一个节点先看左边一直访问其左边的节点，左边走不通了再一直访问其右边的节点再回溯到上层节点继续访问得出

进入图6的树后先访问根节点A，从A往左走碰到B，B的左边已经空了,回到B，从B往右走到C,从C往左走到D，D的左边空，回到D，D的右边空再回D，因为C的右边还没走，回到C，走C的右边，C的右边空，回到C,再回B，再回A ,开始往A的右边走…后面大概应该已经知晓过程了吧最后得到ABBCDDDCCBAEEFGHHHGKKKGFFEA这段序列。通过这段序列我们知道，同一个节点我们会访问三次，但是我们每个节点只需要遍历一次，所以根据第几次访问节点的时候处理节点，这里就分三种方式遍历，这三种方法分别是：先序遍历，中序遍历，后序遍历。

图6

1.4.1先序遍历

第一次访问节点的时候处理节点根据上面那段序列，删掉每个节点第一次出现后的第二三次的出现 先序遍历序列：A B C D E F G H K

1.4.2中序遍历

第二次访问节点的时候处理节点根据上面那段序列，每个节点第一次出现后赶紧删掉，第二次出现后保留，第三次出现后又马上删除，中序序遍历序列：B D C A E H G K F

1.4.3后序遍历

第三次访问节点的时候处理节点根据上面那段序列，每个节点第一次出现和第二次后赶紧删掉，保留第三次时出现的节点，后序遍历序列：D C B H K G F E A

我们实际写序列的时候不用把ABBCDDDCCBAEEFGHHHGKKKGFFEA这种长序列写出来

• 先序遍历的时候，第一次访问的时候就可以写数序列号了，从左边的“棒”回来不写，从右边的“棒”回来不写
• 中序遍历的时候，第一次访问不写序列号，从左边的“棒”回到该节点的时候在写，从右边的“棒”回来不写
• 后序遍历的时候，第一次访问不写序列号，从左边的“棒”回到该节点不写，从右边的“棒”回来的时候写

1.4.4遍历的规律

先看先序遍历A B C D E F G H K和后序遍历D C B H K G F E A,先序遍历的第一个序列可以确定第一个节点，后序遍历的最后一个序列也可以确定第一个根节点，在A是根节点的一个情况下，来看中序遍历B D C A E H G K F，A的左边都是A的左子树的节点，A的右边都是右子树的节点，也就是说如果我们能在先序确定一个根，那么再根据中序遍历我们就能确定以这个根为根节点这棵树，A看完确定左右后我们再来看先序遍历中的B，发现如果以B为根节点中序遍历中在B和A之间,D和C只在B的右边，B左边为空，在图6中B的左边确实为空，依次类推，我们可以得出一个结论，先序遍历确定根，中序遍历确定左右来画出原本的树。一般来说期末考试可能会考这种题告诉你前序，中序遍历的序列，让你写后序遍历的序列，一般思路我们都先根据先序和中序画出树，再根据树得出后序遍历的序列

接下来来看两道例题：

• 例1：若某二叉树的先序遍历访问顺序是序abdgcefh，中序遍历顺序是dgbaechf，求后序遍历

  • 如图7：由先序遍历的第一个点是a可以知道a是根节点，再看中序遍历中a的左边是dgb,知道dgb三个节点在a的左边，a的右边是echf，知道echf四个节点在a的右边并在先序中找到左右各自对应的序列顺序

  • 如图8：拆分成左右后看左边的先序是bdg，知道a的左边是b，再看中序中b的右边没有，证明dg都在b的左边，写出dg对应前序的序列dg，d在前面，结合dg都在b的左边，把d连在b的左边，将d看作根节点，中序遍历中g在d的右边，证明g连在d的右边。

  • 右边的子树和上面一样的思路，最终结果如图9
    
    图7
    
    图8

图9

• 例2：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。
  • 这里的思路和例题1是一样的需要注意的是A根节点很好确定，在中序划分了左：BDCE和右：FHG，对应后序的左：DECB和右：HGF后应该从最后一个开始看，即A的左边连接后序序列：DECB的最后一个序列B，A的右边连接后序序列：HGF的最后一个序列F，依次类推，这里就不在这里着重讲解了。最终结果如图10。

图10

1.4.5深度遍历递归代码

在深度遍历中对每个节点的处理逻辑是一样的，只是每个节点值不一样，我们很容易想到用递归函数来实现深度遍历的代码，这样对一棵树的操作，我们细分成每一个节点的操作即可，由于我没找到动图，下面请来看一组图片。

下面先序遍历的伪代码

初始是节点进入递归函数，函数传的参数是A节点，发现A！=NULL，打印A的数据，执行第三句话进入子函数1，传递的参数B（A->left）。

子函数1接收的参数为B判断不为空，打印B的数据，执行第三句话，传的参数是B->left，进入子函数2。

子函数2接收的参数是B->left==NULL，直接返回到子函数1的第三句话，此时子函数2由于return直接没有了。进入子函数1的第四句话。传递的参数是B->right=D;进入子函数3。

子函数3接收的参数是B->right=D，判断不为空，打印D的数据

进入子函数3的第三句话，传入的值是NULL，进入子函数4，发现为NULL return后子函数4没有了，return到子函数3的第三句话，进入子函数3的第四句话，传入的值是NULL，进入子函数5，发现为NULL return后子函数5没有了，返回到子函数3的第四句话。此时发现子函数3的四句话都执行完成了，而子函数3是由子函数1执行第四句话时传递参数B->right=D时产生的，所以子函数1也执行完了，而子函数1是由于初始时递归函数在执行第三句话传入参数A节点的left产生的，此时说明已经处理完A的左边，现在执行最初的递归函数的第四句话传入的参数A->right进入子函数6

子函数6接收的参数是C(A->right)，不为空，打印C的值，执行第三句话传递C->left参数，进入子函数7

子函数7接收的参数是C->left是NULL，直接return到子函数6，执行子函数6第四句话，传递的参数C->right是NULL，直接return到子函数6的第四话，子函数6结束，而子函数6接收的参数是A->right即最初的递归函数四句话全部执行完，整个函数执行完毕。

由于是第一次遇到比较难的思想：递归，所以我这里写的有点多也有点绕 ，但是耐心看懂了对自己理解递归很有帮助，我个人能力有限，只能讲成这样，各位可以去另外的大神那里看看这部分的内容。

大概先写这些吧，明天单独写树的广搜和深搜的代码，今天的博客就先写到这，谢谢您的观看。