二叉树前, 中,后序查找算法(思路分析)

二叉树前,中,后序查找算法(思路分析)

问题: 编写前, 中, 后序查找算法,分别使用三种查找算法来查找二叉树中heroNo = 5的结点 , 并且分析各种查找算法分别比较了多少次

• 注意: 我们执行的递归的次数不等于我们的判断的次数, 我们这里说的判断的次数就是根据真正每次比较的次数,在有的递归的过程中我们是没有执行比较的操作的, 比如我们的后序查找算术中我们肯定是先一直遍历,遍历到最左端的结点 , 这个时候可能还是已经遍历了很多次了才到达这个节点 , 但是这个时候才是第一次比较

前序查找的思路:

1. 先判断当前节点的no是否等于要查找的no值
2. 如果相等,则返回当前节点
3. 如果不等, 则判断当前节点的左子节点是否为空, 如果不为空, 则递归前序查找左子树
4. 如果左递归前序查找过程中找到了结点, 则返回,否则就继续判断当前节点的右子节点是否为空,如果不空,则继续向右递归前序查找, 如果右递归中也没有找到就返回一个null,如果右递归中找到了则返回对应的结点

中序查找的思路:

1. 判断当前节点的左子节点是否为空, 如果不为空, 则递归前序查找左子树
2. 判断当前节点的no是否等于要查找的no值
3. 判断当前节点的右子节点是否为空,如果不空,则继续向右递归前序查找, 如果右递归中也没有找到就返回一个null,如果右递归中找到了则返回对应的结点

后序遍历查找的思路:

1. 判断当前节点的左子节点是否为空, 如果不为空, 则递归前序查找左子树
2. 如果左递归前序查找过程中找到了结点, 则返回,否则就继续判断当前节点的右子节点是否为空,如果不空,则继续向右递归前序查找, 如果右递归中找到了则返回对应的结点
3. 判断当前节点的no是否等于要查找的no值

难点分析:

此时我们向左和向右递归的时候要判断是否存在符合条件的结点, 如果有的话要将这个符合条件的结点返回, 那么我们的递归方法就是一个需要返回值的方法, 我们就是要在每一层递归方法中接收对应的下一层的递归方法的返回值, 并且我们要对这个返回值做出一个判断,看这个返回值是不是我们需要的结果, 如果是我们需要的结果就做出什么样的操作, 如果不是我们需要的结果我们就做出一个什么样的操作 —> 总之如果我们是要查找一个值的时候如果这个时候我们使用递归来解决那么这个时候递归方法肯定是要有返回值的, 因为我们要将查找的结果一层栈一层栈的返回回来