1. Toy模板网首页
  2. > Toy博客

二叉树的前序、中序、后序遍历（递归版）

10月前 作者：一只眠羊。 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了二叉树的前序、中序、后序遍历（递归版）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

 

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。

1、二叉树的遍历方法

对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

所谓前序，中序，后续遍历命名的由来是我们访问二叉树，根节点的顺序。前序遍历就是优先访问根节点，中序遍历是第二个访问根节点，后续遍历就是访问完左右节点之后，最后访问根节点。

注意访问二字。访问和获取是两个不同的概念，我们可以获取一个节点，但是不访问他。对应在计算机里的概念是，获取一个节点表示将他入栈，访问一个节点是他处于栈顶，我们即将让他出栈。

2、前序遍历（先序遍历）

前序遍历，就是优先访问根节点，然后访问左子节点，最后访问右子节点。说简单点就是：根左右。

直接上代码：

二叉树的前序、中序、后序遍历（递归版）二叉树的前序、中序、后序遍历（递归版）
 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 public class treeTest {
49 
50     public static void main(String[] args) {
51         Queue<TreeNode<Integer>> queue = new LinkedList<>();
52         TreeNode<Integer> root = new TreeNode<>(0);
53         root.setLeft(1);
54         root.setRight(2);
55         root.getLeft().setLeft(3);
56         root.getLeft().setRight(4);
57         root.getRight().setLeft(5);
58         root.getRight().setRight(6);
59         System.out.println("   " + root.getVal());
60         System.out.println("  /  \\");
61         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
62         System.out.println("/ \\  / \\");
63         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
64                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
65 
66 
67 
68         List<Integer> qianXu = qian(root);
69         System.out.println(qianXu);
70     }
71 
72     private static List<Integer> qian(TreeNode<Integer> root) {
73         List<Integer> resut = new ArrayList<>();
74 
75         if(null == root) return resut;
76 
77         resut.add(root.getVal());
78         resut.addAll(qian(root.getLeft()));
79         resut.addAll(qian(root.getRight()));
80 
81         return resut;
82     }
83 }
前序遍历

输出结果：

二叉树的前序、中序、后序遍历（递归版）

3、中序遍历

中序遍历，就是优先访问左子节点，然后访问根节点，最后访问右子节点。说简单点就是：左根右。

示例代码：

二叉树的前序、中序、后序遍历（递归版）二叉树的前序、中序、后序遍历（递归版）
 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 
49 public class treeTest {
50 
51     public static void main(String[] args) {
52         Queue<TreeNode<Integer>> queue = new LinkedList<>();
53         TreeNode<Integer> root = new TreeNode<>(0);
54         root.setLeft(1);
55         root.setRight(2);
56         root.getLeft().setLeft(3);
57         root.getLeft().setRight(4);
58         root.getRight().setLeft(5);
59         root.getRight().setRight(6);
60         System.out.println("   " + root.getVal());
61         System.out.println("  /  \\");
62         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
63         System.out.println("/ \\  / \\");
64         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
65                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
66 
67         List<Integer> zhongXu = zhong(root);
68         System.out.println(zhongXu);
69     }
70 
71     private static List<Integer> zhong(TreeNode<Integer> root) {
72         List<Integer> resut = new ArrayList<>();
73 
74         if(null == root) return resut;
75 
76         resut.addAll(zhong(root.getLeft()));
77         resut.add(root.getVal());
78         resut.addAll(zhong(root.getRight()));
79 
80         return resut;
81     }
82 }
中序遍历

输出结果：

二叉树的前序、中序、后序遍历（递归版）

4、后序遍历

后序遍历，就是优先访问左子节点，然后访问右子节点，最后访问根节点。说简单点就是：左右根。

示例代码：

二叉树的前序、中序、后序遍历（递归版）二叉树的前序、中序、后序遍历（递归版）
 1 public class TreeNode<N> implements Serializable {
 2 
 3     private N val;
 4 
 5     private TreeNode<N> left;
 6 
 7     private TreeNode<N> right;
 8 
 9     public TreeNode() {
10     }
11 
12     public TreeNode(N val) {
13         this.val = val;
14     }
15 
16     public TreeNode(N val, N leftVal, N rightVal) {
17         this.val = val;
18         this.left = new TreeNode<>(leftVal);
19         this.right = new TreeNode<>(rightVal);
20     }
21 
22     public N getVal() {
23         return val;
24     }
25 
26     public void setVal(N val) {
27         this.val = val;
28     }
29 
30     public TreeNode<N> getLeft() {
31         return left;
32     }
33 
34     public void setLeft(N left) {
35         this.left = new TreeNode<>(left);
36     }
37 
38     public TreeNode<N> getRight() {
39         return right;
40     }
41 
42     public void setRight(N right) {
43         this.right = new TreeNode<>(right);
44     }
45 }
46 
47 
48 public class treeTest {
49 
50     public static void main(String[] args) {
51         Queue<TreeNode<Integer>> queue = new LinkedList<>();
52         TreeNode<Integer> root = new TreeNode<>(0);
53         root.setLeft(1);
54         root.setRight(2);
55         root.getLeft().setLeft(3);
56         root.getLeft().setRight(4);
57         root.getRight().setLeft(5);
58         root.getRight().setRight(6);
59         System.out.println("   " + root.getVal());
60         System.out.println("  /  \\");
61         System.out.println(" " + root.getLeft().getVal() + "    " + root.getRight().getVal());
62         System.out.println("/ \\  / \\");
63         System.out.println(root.getLeft().getLeft().getVal() + " " +  root.getLeft().getRight().getVal() + "  "
64                 + root.getRight().getLeft().getVal() + "  " + root.getRight().getRight().getVal());
65 
66         List<Integer> houXu = hou(root);
67         System.out.println(houXu);
68     }
69 
70     private static List<Integer> hou(TreeNode<Integer> root) {
71         List<Integer> resut = new ArrayList<>();
72 
73         if(null == root) return resut;
74 
75         resut.addAll(hou(root.getLeft()));
76         resut.addAll(hou(root.getRight()));
77         resut.add(root.getVal());
78 
79         return resut;
80     }
81 }
后序遍历

 输出结果：

二叉树的前序、中序、后序遍历（递归版）文章来源地址https://www.toymoban.com/news/detail-693637.html

到了这里，关于二叉树的前序、中序、后序遍历（递归版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包