【数据结构】关于二叉树，你必须知道的遍历方法！！！
【数据结构】关于二叉树，你必须知道的遍历方法！！！
那么咱们开始吧 ~~~🎬
📚️1.什么是遍历
🎥1.1概念
遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
🎥1.2例子
1. 在计算机编程中，对数组进行遍历是常见操作。例如用循环语句依次访问数组中的每一个元素，以便进行数据处理、统计等操作。比如计算一个整数数组中所有元素的和，就需要遍历这个数组，将每个元素的值依次相加。
2.在链表的查找数值时，就要通过结点之间的地址来进行遍历，通过每个结点的值域来进行比较，从而实现查找目标数值。
📚️2.非递归遍历
🎥2.1引言
🌟🌟在遍历中，当我们打印一个结点的左树时，此时发现在左树打印完时，还需要通过结点的引用来遍历结点的右树，所以我们这里当结点还有用时，就要将结点存放在一个容器中，这个容器就是栈！！！
🎥2.2非递归的前序遍历
1.遍历原理：
首先在进行遍历时我们要了解前序遍历的原理，前序遍历的次序是（根结点->左子树->右子树），所以我们就能够依次原理来进行前序遍历。
💡💡2.遍历思路：
首先创建一个栈，若根结点不为空那么就放入栈中，此时然后遍历左树，在遍历过程中要进行每个结点的值域打印，并且放入栈中，然后当左树遍历时为空，那么就进行出栈，并且遍历出栈结点的右树，那么此时就为一个循环。
3.代码实例：
public void IpreOrder(TreeNode root){
Stack<TreeNode> stack=new Stack<>();//创建一个栈
if(root==null){
return;
}
TreeNode cur=root; //设一个结点等于根结点
TreeNode top;
while (cur!=null||!stack.isEmpty()){
while (cur!=null){
stack.push(cur);
System.out.print(cur.val+" ");
cur=cur.left;
}
top=stack.pop(); //结点没有用，就出栈
cur=top.right; //遍历出栈结点的右树
}
}🌟🌟注意：在跳出内循环时，要进行栈顶元素的右树遍历，还要再次进入循环，所以添加了一个外循环，但是存在右树为空，所以还要添加条件。
4.图解：
🎥2.2非递归的中序遍历
1.遍历原理：
首先在进行遍历时我们要了解中序遍历的原理，中序遍历的次序是（左子树->根结点->右子树），所以我们就能够依次原理来进行中序遍历。
💡💡 2.遍历思路：
和上述前序遍历的原理几乎一样，但是由于，遍历的顺序不同，所以遍历完左树时，在出栈的时候才能进行打印，然后再次进行右树的遍历，若右树为空再次出栈，进行打印，然后进入内部循环，再次进行新结点的遍历。
3.代码实例：
public void IinOrder(TreeNode root){
Stack<TreeNode> stack=new Stack<>(); //创建一个栈
if(root==null){
return;
}
TreeNode cur=root;
TreeNode top;
while (cur!=null||!stack.isEmpty()){ //当cur为空，并且栈为空就遍历完了
while (cur!=null){
stack.push(cur); //压栈
cur=cur.left;
}
top=stack.pop(); //发现为空，就跳出循环，并且出栈
System.out.print(top.val+" ");
cur=top.right; //遍历出栈结点的右树
}
}🎥2.3非递归的后序遍历
1.遍历原理：
首先在进行遍历时我们要了解后序遍历的原理，后序遍历的次序是（左子树->右子树->根结点），所以我们就能够依次原理来进行后序遍历。
💡💡2.遍历思路：
总体上思路上来说，与上述两种遍历基本一致，但是因为根是最后打印的，并且还要通过他俩进行右树的调用，所以不能出栈，但是因为没有出栈，为了防止循环打印，就还要另外设条件，实现打印并且再次出栈。
3.代码实例：
public void IpostOrder(TreeNode root){
Stack<TreeNode> stack=new Stack<>();
if(root==null){
return;
}
TreeNode cur=root;
TreeNode top;
TreeNode prve=null;
while (cur!=null||!stack.isEmpty()){
while (cur!=null){
stack.push(cur);
cur=cur.left;
}
top=stack.peek(); //此时还没有进行打印，有用所以不出栈
if (top.right==null||top.right==prve){//防止循环打印
System.out.print(top.val+" ");
stack.pop();
prve=top;
}else {
cur=top.right;
}
}
}🎥2.4非递归的层次遍历
1.遍历原理：
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
2，图片实例：
3.遍历思路：
首先我们要创建一个栈实现结点的存与出，当根结点不为空时入栈，然后进行打印，出栈，但是要将节点相邻的左右子结点进行入栈，再此出栈时就进行打印。
4.代码实例：
public void levelTree(TreeNode root){
if(root==null){
return;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur=queue.poll();
System.out.print(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
}📚️3.递归遍历
🎥3.1引言
在上述遍历中，可以发现条件复杂，还要借助栈来实我们的遍历，那么我们能够用其他办法来简单实现遍历，那么这里我们就要用到递归了。
🎥3.2递归的前序遍历
1.遍历思路：
💡💡首先判断根结点是否为空，然后进行打印，因为前序遍历的首个就是根结点，然后实现递归，如下代码，首先先一直递归左树，当遇到结点为空时就返回，并进行这个结点的右递归，为空就返回，存在就再次递归左树，每次递归都要进行打印。
2.代码实例：
public void preOrder(TreeNode root){
if(root==null){
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}3.图解思路：
~~~在看图时，遍历是从1到3，在从3到1,别看反咯😄😄😄
🎥3.3递归的中序遍历
1. 遍历思路：
💡💡和前序遍历基本一致，但是由于中序遍历的思路是（左子树->根结点->右子树），所以只能在遍历左树后遇到空结点才能够进行打印，然后再遍历右树，若右树为空，则返回，并进行打印结点，在遍历此节点的右树。
2.代码实例：
public void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}🎥3.4递归的后序遍历
1.遍历思路：
💡💡由于后序遍历的原理（左子树->右子树->根结点），所以首先进行左树的遍历，当遇到空结点的时候，返回并进行右树的遍历，当右树为空时，就进行打印，说明此节点为左树的叶子节点，然后返回再次遍历上一个节点的右树。
2.代码实例：
public void postOrder(TreeNode root){
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}3.图片实例：
~~~小编再次运用了这个图，说明很重要。
📚️4.总结
💬💬小编在这期讲述了二叉树遍的两种方法，分别为递归与非递归遍历，两者各不相同，各有优点，递归方法，代码简单但是内部原理不易，而非递归方法，更容易想到。
二叉树学习，确实存在较大的困难，其中涉及到递归的思想，但是一切困难度都不足畏惧！！！
🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！
💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。
😊😊 期待你的关注~~~ ————————————————
腾讯云开发者
