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

⼆叉树的前序、中序、后序遍历（附java代码）前序、中序、后序遍历思想1. 前序遍历的顺序是根左右，即先遍历根节点，接着遍历左节点，最后遍历右节点；2. 中序遍历的顺序是左根右，即先遍历左节点，接着遍历根节点，最后遍历右节点；3. 后序遍历的顺序是左右根，即先遍历左节点，接着遍历右节点，最后遍历根节点。4. 总结：前序、中序、后序遍历就是看访问根节点的位置。 举例说明 假设⼀颗如图所⽰的⼆叉树，如何写出前序、中序、后序遍历呢？⼆叉树⽰意图 我们可以将上图转化为如图所⽰的⼀个个⼦⼆叉树。⼦⼆叉树划分⽰意图那么根据前序遍历的特点（根左右），先A->B，这时，将B作为根节点，遍历B的左⼦树，即B->D，此时，D已是叶⼦节点，接着遍历B的右⼦树，B->E，此时，E也是叶⼦节点了，并且对于A来说，左⼦树已全部遍历完毕，接着遍历A的右⼦树，A->C，这时，将C作为根节点，遍历C的左⼦树，C->F，此时，F已是叶⼦节点，⼜C没有右⼦树，那么对于A节点来说右⼦树也遍历完成，结束，遍历顺序为：A->B->D->E->C->F。同样，依据中序遍历的特点（左根右），可以写出遍历顺序为：D->B->E->A->F->C。最后，依据后序遍历特点（左右根），可以写出遍历顺序为：D->E->B->F->C->A。代码实现⾸先，我们需要利⽤代码定义⼀颗⼆叉树，即表述出节点之间的关系，代码如下：class TreeNode { //存⼊的值 String value; //左⼦树⽗节点，默认是null TreeNode left; //右⼦数⽗节点，默认是null TreeNode right; public TreeNode(String value) { = value; } public TreeNode(String value, TreeNode left, TreeNode right) { = value; = left; = right; }}前序遍历代码（递归法）： //前序遍历

public void preOrder() { //先输出⽗节点 ( + " "); //递归左⼦树 if ( != null) { er(); } //递归右⼦树 if ( != null) { er(); } }中序遍历代码（递归法）： //中序遍历 public void midOrder() { //递归左节点 if ( != null) { er(); } //输出⽗节点 ( + " "); //递归右节点 if ( != null) { er(); } }后序遍历代码（递归法）： //右序遍历 public void afterOrder() { //递归左节点 if ( != null) { rder(); } //递归右节点 if ( != null) { rder(); } //输出⽗节点 ( + " "); } 整体代码：public class Solution { public static void main(String[] args) { //创建节点 TreeNode rootA = new TreeNode("A"); TreeNode nodeB = new TreeNode("B"); TreeNode nodeC = new TreeNode("C"); TreeNode nodeD = new TreeNode("D"); TreeNode nodeE = new TreeNode("E"); TreeNode nodeF = new TreeNode("F"); //描述关系 = nodeB; = nodeC; = nodeD; = nodeE; = nodeF; ("前序遍历->"); er(); n(); ("中序遍历->"); er(); n(); ("后序遍历->"); rder(); }}}class TreeNode { //存⼊的值 String value; //左⼦树⽗节点，默认是null TreeNode left; //右⼦数⽗节点，默认是null TreeNode right; public TreeNode(String value) { = value; } public TreeNode(String value, TreeNode left, TreeNode right) { = value; = left; = right; } //前序遍历 public void preOrder() { //先输出⽗节点 ( + " "); //递归左⼦树 if ( != null) { er(); } //递归右⼦树 if ( != null) { er(); } } //中序遍历 public void midOrder() { //递归左节点 if ( != null) { er(); } //输出⽗节点 ( + " "); //递归右节点 if ( != null) { er(); } } //右序遍历 public void afterOrder() { //递归左节点 if ( != null) { rder(); } //递归右节点 if ( != null) { rder(); } //输出⽗节点 ( + " "); }}测试结果：