來看一個具體的習題實踐：
題目
根據二叉樹前序遍歷序列例如：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)); }} |
