二叉树的前,中,后序遍历(思路分析)

前序遍历:

先输出父节点, 再遍历左子树和右子树

中序遍历:

先遍历左子树, 再输出父节点,再遍历右子树

后序遍历:

先遍历左子树,再遍历右子树,最后输出父节点

分析二叉树的前序,中序,后序的遍历步骤:

前序遍历:

1. 创建一颗二叉树
2. 先输出当前节点(初始的时候是root节点)
3. 如果左子节点不为空 , 则递归继续遍历左子树
4. 如果右子节点不为空,则递归继续遍历右子树

中序遍历:

1. 先创建一颗二叉树
2. 如果当前节点的左子节点不为空, 则递归中序遍历左子树
3. 输出当前节点
4. 如果当前节点的右子节点不为空 , 则递归中序遍历右子树

二叉排序树(二分搜索树)中序遍历的结果就是一个升序序列

后序遍历:

1. 先创建一颗二叉树
2. 如果当前节点的左子节点不为空 , 则递归后序遍历左子树
3. 如果当前节点的右子节点不为空, 则递归后序遍历右子树
4. 输出当前节点

小结:看输出父节点的顺序就能确定是前序,中序,还是后序遍历

注意: 此时我们没有讲二叉树的递归创建,所以此时我们会手动的创建一个二叉树来测试,并不会编写专门创建二叉树的方法

补充(2022-4-25):

对于二叉树和链表遍历的时候如果我们要给对应的链表结点类或者是树结点类重写toString()方法,这个时候我们一定要注意: 我们不能输出对应的指针域( 也就是对于链表我们不要输出next域. , 对于二叉树我们不要输出left和right), 我们这里以链表为例来进行一个讲解, 如果我们在链表结点类中重写toString()方法的时候输出了next属性,此时由于我们的next属性是引用类型的属性,这个时候输出这个next属性的时候就会自动调用这个next属性的toString()方法,这个时候这个next属性其实就是执行了下一个位置的节点,此时我们就相当于要输出下一个节点,而我们在这个next节点中的toString方法中又会输出这个next节点对应的next属性, 这个时候就一直递归了下去,知道输出到链表的最后一个节点的next属性的时候这个属性为null,然后就直接输出null,不会继续调用toString()方法

当我们输出一个引用类型数据的时候会自动调用这个引用类型数据的所在类中的toString()方法, 但是我们的java官方进行了一个优化, 就是如果我们是输出一个引用类型的变量,这个时候如果这个引用类型的变量指向了null,那么我们就不会使用这个引用类型的变量调用toString()方法 —> 就避免了空指针异常的发生

补充二(2022-4-25):

其实对于使用到链式结构的数据结构中(哈希表, 树等),我们可以将对应的一系列操作都放到节点类中完成, 比如如果是树结构我们要完成前序遍历, 我们可以将前序遍历的方法完成在我们的树节点类中,然后到二叉树类中直接调用这个前序遍历的方法就可以了(当然,我们肯定是要使用头结点调用 , 因为我们遍历树肯定是要从头结点开始遍历)

这个时候我们使用头结点调用这个树节点类的前序遍历的方法,那么我们的头结点在这个方法中扮演的角色就是这个方法中的this —> 我们的一个成员方法中,谁调用的这个方法,那么this就指向谁 构造方法中this表示的是正在创建的对象,创建哪个对象,对应的构造方法中的this就指向谁