来看一个具体的习题实践：
题目
根据二叉树前序遍历序列例如：7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#，构建二叉树，并且用前序、中序、后序进行遍历
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类，定义二叉树节点 */ static class TreeNode { public String data; TreeNode lchild; TreeNode rchild; public TreeNode(String x) { this.data = x; } } /** * 根据前序序列递归构建二叉树 * * @return */ public static TreeNode createBtree() { TreeNode root = null; if (count >= str.length || str[count++].equals("#")) { root = null; } else { root = new TreeNode(str[count - 1]); root.lchild = createBtree(); root.rchild = createBtree(); } return root; } /** * 前序遍历 * * @param root */ public static void preTraverse(TreeNode root) { if (root != null) { System.out.print(root.data + " "); preTraverse(root.lchild); preTraverse(root.rchild); } } /** * 中序遍历 * * @param root */ public static void inTraverse(TreeNode root) { if (root != null) { inTraverse(root.lchild); System.out.print(root.data + " "); inTraverse(root.rchild); } } /** * 后序遍历 * * @param root */ public static void postTraverse(TreeNode root) { if (root != null) { postTraverse(root.lchild); postTraverse(root.rchild); System.out.print(root.data + " "); } } public static void main(String args[]) { Scanner cin = new Scanner(System.in); while (cin.hasNext()) { String s = cin.nextLine(); str = s.split(","); count = 0; TreeNode root = createBtree(); // 前序遍历 preTraverse(root); System.out.println(); // 中序遍历 inTraverse(root); System.out.println(); // 后序遍历 postTraverse(root); System.out.println(); } } } |
二叉树的深度
下面是是实现二叉树的递归算法的实现，其思想就是，若为空，则其深度为0，否则，其深度等于左子树和右子树的深度的最大值加1：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Node{ String name; Node left; Node right; public Node(String name) { this.name = name; } @Override public String toString() { return name; }}//定义二叉树class BinaryTree{ Node root; public BinaryTree(){ root = null; } //为了方便起见，我就直接写个初始化的二叉树，详细的可以见以前的日志 public void initTree(){ Node node1 = new Node("a"); Node node2 = new Node("b"); Node node3 = new Node("c"); Node node4 = new Node("d"); Node node5 = new Node("e"); root = node1; node1.left = node2; node2.right = node3; node1.right = node4; node3.left = node5; } //求二叉树的深度 int length(Node root){ int depth1; int depth2; if(root == null) return 0; //左子树的深度 depth1 = length(root.right); //右子树的深度 depth2 = length(root.left); if(depth1>depth2) return depth1+1; else return depth2+1; }}public class TestMatch{ public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.initTree(); System.out.println(tree.length(tree.root)); }} |
