2023年6月22日发(作者：)

⼆叉树的前序、中序、后序、层序遍历，Java实现（递归、⾮递归）关于⼆叉树的内容，我觉得⼆叉树最核⼼的地⽅就是它的⼏种遍历⽅式，基本上所有的问题都是围绕着⼏种遍历⽅式来的。因此就在这总结⼀下这⼏种遍历⽅式。前序遍历⼀、简介前序遍历（DLR），是⼆叉树遍历的⼀种，也叫做先根遍历、先序遍历，可记做根左右。前序遍历⾸先访问根结点然后遍历左⼦树，最后遍历右⼦树。在遍历左、右⼦树时，仍然先访问根结点，然后遍历左⼦树，最后遍历右⼦树。若⼆叉树为空则结束返回，否则：1.访问根结点2.前序遍历左⼦树2.前序遍历右⼦树如图：前序遍历结果：ABDECF⼆、代码实现1.递归实现class TreeNode{//TreeNode类，后边同样 TreeNode left; TreeNode right; int val; TreeNode(int val){ = val; }}public class PreOrderTraversal { public void preOrder(TreeNode root){ if(root != null){ n();//打印根节点 preOrder();//访问左⼦树 preOrder();//访问右⼦树 } }}2.⾮递归实现⽅法⼀： 根节点存⼊栈中打印根节点，然后访问这个根节点的左⼦树，左⼦树也是将左⼦树的根存⼊栈中打印根节点，依次往下直到左⼦树为空，再取出栈顶元素，栈顶元素(访问完左⼦树的根节点)作为新的根节点去访问右⼦树。public void preorderTraversal(TreeNode root) { Stack stack = new Stack<>();//⽤⼀个栈来存放树中的节点 while(root != null || !y()) {//只要当前节点不为空(即当前节点的左右⼦树没有访问完毕)或者栈中还有节点(还有节点没有访问) while (root != null) {//⼀直往左⾛ (root);//根节点⼊栈 n();//打印根节点 root = ;//访问左⼦树 } root = ();//取出根节点 root = ;//访问右⼦树 } }⽅法⼆： 我们知道前序遍历遵从根左右的顺序，所以我们打印根节点，并将它的右⼦树，左⼦树按照顺序压⼊栈中，每次只取出栈顶的⼀个节点，这样就可以保证所有的左⼦树都会在右⼦树之前取出并打印。import ;public class PreOrderTraversal { public void preorderTraversal(TreeNode root) { Stack stack = new Stack<>(); if(root == null)//树为空 return; (root);//将根节点压⼊栈中 while(!y()){//只要栈不为空，执⾏循环 TreeNode node = ();//取出栈顶元素打印，此时的栈顶元素是以node为根的⼦树的根 n(); if( != null)//将右⼦树压⼊栈中 (); if( != null)//将左⼦树压⼊栈中 (); } }}中序遍历⼀、简介中序遍历（LDR）是⼆叉树遍历的⼀种，也叫做中根遍历、中序周游。可记做左根右中序遍历⾸先遍历左⼦树，然后访问根结点，最后遍历右⼦树。若⼆叉树为空则结束返回，否则：1.中序遍历左⼦树2.访问根结点3.中序遍历右⼦树如图：中序遍历结果:DBEAFC⼆、代码实现1.递归实现public class InOrderTraversal { public void inorderTraversal(TreeNode root){ if(root != null){ inorderTraversal();//访问左⼦树 n();//打印根节点 inorderTraversal();//访问右⼦树 } }}2.⾮递归实现根前序遍历⽅法⼀思路⼀样，不同的只是先不打印根节点，⽽是先访问左⼦树，再打印根节点，访问右⼦树。import ;public class InOrderTraversal { public void inorderTraversal(TreeNode root){ Stack stack = new Stack<>(); while(root != null || !y()){//只要当前节点不为空(即当前节点的左右⼦树没有访问完毕)或者栈中还有节点(还有节点没有访问) while(root != null){ (root);//根节点⼊栈 root = ;//访问左⼦树 } root = ();//取出左⼦树的根节点 n();//打印根节点 root = ;//访问右⼦树 } }}后序遍历⼀、简介⾸先遍历左⼦树，然后遍历右⼦树，最后遍历访问根结点，在遍历左、右⼦树时，仍然先遍历左⼦树，然后遍历右⼦树，最后遍历根结点。若⼆叉树为空则结束返回，否则：1.中序遍历左⼦树2.中序遍历右⼦树3.访问根结点如图：后序遍历结果:DEBFCA⼆、代码实现1.递归实现public class PostOrderTraversal { public void postOrder(TreeNode root){ if(root != null){ postOrder();//访问左⼦树 postOrder();//访问右⼦树 n();//打印根节点 } }}2.⾮递归实现⽅法⼀： 常规遍历左右根，和前序、中序⽅法⼀类似。import ;public class PostOrderTraversal { public void postorderTraversal(TreeNode root) { Stack stack = new Stack<>(); TreeNode node = root; TreeNode prev = null; while(node != null || !y()){ while(node != null){ //访问左⼦树 (node); node = ; } //判断栈顶元素(根) node = (); //1.如果此时的根的右⼦树为空 == null //2.如果此时的根的右⼦树已经访问过了 == prev(prev记录的是上次访问打印的节点) if( == null || == prev){ //打印根节点，并出栈，将打印过的节点从栈中删除 (); n(); //记录prev，表⽰以当前prev为根的⼦树已经访问过了 prev = node; //node置null就不会再次访问以node为根节点的左右⼦树，这⾥的node既然已经打印，说明它的左右⼦树早已访问完毕 node = null; }else{ //访问右⼦树 node = ; } } }}⽅法⼆： 和前序遍历的⽅法⼆类似，我们可以⽤⼀个线性表存放后序遍历的结果。我们知道后序遍历是左右根，但是我们可以反过来，⼀样先访问根，只是将根放在后边然后访问右⼦树放在根的前边左⼦树的后边，我们可以⽤线性表头插来实现这个操作，先访问根再右⼦树再左⼦树，只是每次都对线性表进⾏头插，这样最后的结果就还是左右根。import List;import ;import ;public class PostOrderTraversal { public List postorderTraversal(TreeNode root) { Stack stack = new Stack<>(); List list = new LinkedList<>(); if(root == null) return list; (root); while(!y()){ TreeNode node = (); (0, );//头插此时根节点 if( != null) (); if( != null) (); } return list; }}层序遍历⼀、简介除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根节点所在层数为1，层序遍历就是从所在⼆叉树的根节点出发，⾸先访问第⼀层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。如图：层序遍历结果:ABCDEF⼆、代码实现import List;import ;public class LevelOrder { public void levelOrder(TreeNode root) { Queue queue = new LinkedList<>(); if(root != null){//如果根节点不为空,将第⼀层根节点⼊队列 (root); } while(!y()){//只要队列不为空，执⾏循环 int num = ();//记录此时队列的长度，此时的num代表了某⼀层⼀共有多少个节点，防⽌被后边⼊队的节点个数影响输出这⼀层的节点 for(int i = 0; i < num; i++){//对某⼀层的所有节点进⾏操作(从左到右) TreeNode topNode = ();//取出这⼀层第⼀个节点 n();//打印节点 if( != null){//将此节点的左⼦树根节点⼊队列 (); } if( != null){//将此节点的右⼦树根节点⼊队列 (); } } } }}总结：所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。访问结点所做的操作依赖于具体的应⽤问题。 遍历是⼆叉树上最重要的运算之⼀，是⼆叉树上进⾏其它运算之基础。⼀定要仔细体会其中的遍历过程。