【Java数据结构】实现二叉树及其基本操作

1. import java.util.LinkedList;
2. import java.util.Queue;
3. 
4. public class BinaryTree {
5. 
6. static class TreeNode {
7. public char val;
8. public TreeNode left;//左孩子的引用
9. public TreeNode right;//右孩子的引用
10. 
11. public TreeNode(char val) {
12. this.val = val;
13.         }
14.     }
15. 
16. 
17. /**
18.      * 创建一棵二叉树 返回这棵树的根节点
19.      *
20.      * @return
21.      */
22. public TreeNode createTree() {
23.         TreeNode A=new TreeNode('A');
24.         TreeNode B=new TreeNode('B');
25.         TreeNode C=new TreeNode('C');
26.         TreeNode D=new TreeNode('D');
27.         TreeNode E=new TreeNode('E');
28.         TreeNode F=new TreeNode('F');
29.         A.left=B;
30.         A.right=C;
31.         C.left=F;
32.         B.left=D;
33.         B.right=E;
34. 
35. 
36. return A;
37. 
38.     }
39. 
40. // 前序遍历
41. public void preOrder(TreeNode root) {
42. if(root==null){
43. return;
44.         }
45.         System.out.print(root.val+" ");
46.         preOrder(root.left);
47.         preOrder(root.right);
48. 
49.     }
50. 
51. // 中序遍历
52. void inOrder(TreeNode root) {
53. if(root==null){
54. return;
55.         }
56.         inOrder(root.left);
57.         System.out.print(root.val+" ");
58.         inOrder(root.right);
59.     }
60. 
61. // 后序遍历
62. void postOrder(TreeNode root) {
63. if(root==null){
64. return;
65.         }
66.         postOrder(root.left);
67.         postOrder(root.right);
68.         System.out.print(root.val+" ");
69. 
70.     }
71. 
72. public static int nodeSize;
73. 
74. /**
75.      * 获取树中节点的个数：遍历思路
76.      */
77. public int size(TreeNode root) {
78. if(root==null){
79. return 0;
80.       }
81.       nodeSize++;
82.       size(root.left);
83.       size(root.right);
84. return nodeSize;
85. 
86.     }
87. 
88. /**
89.      * 获取节点的个数：子问题的思路
90.      *
91.      * @param root
92.      * @return
93.      */
94. public int size2(TreeNode root) {
95. if(root==null){
96. return 0;
97.        }
98. return size2(root.left)+size2(root.right)+1;
99.     }
100. 
101. 
102. /*
103.      获取叶子节点的个数：遍历思路
104.      */
105. public static int leafSize = 0;
106. 
107. public int getLeafNodeCount1(TreeNode root) {
108. if(root==null)return 0;
109. if(root.left==null&&root.right==null)
110.             leafSize++;
111.         getLeafNodeCount1(root.left);
112.         getLeafNodeCount1(root.right);
113. return leafSize;
114.     }
115. 
116. /*
117.      获取叶子节点的个数：子问题
118.      */
119. public int getLeafNodeCount2(TreeNode root) {
120. if(root==null)return 0;
121. if(root.left==null&&root.right==null)
122. return 1;
123. return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
124. 
125.     }
126. 
127. /*
128.     获取第K层节点的个数
129.      */
130. public int getKLevelNodeCount(TreeNode root, int k) {
131. if(root==null||k<=0)return 0;
132. if(k==1)return 1;
133. 
134. return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
135. 
136.     }
137. 
138. /*
139.      获取二叉树的高度
140. 
141.      */
142. public int getHeight(TreeNode root) {
143. 
144. if(root==null)return 0;
145. 
146. return Math.max(getHeight(root.left),getHeight(root.right))+1;
147.     }
148. 
149. 
150. // 检测值为value的元素是否存在
151. public TreeNode find(TreeNode root, char val) {
152. if(root==null)return null;
153. 
154. if(root.val==val)return root;
155. if(find(root.left,val)!=null)
156. return find(root,val);
157. if(find(root.right,val)!=null)
158. return find(root.right,val);
159. 
160. return null;
161. 
162.     }
163. 
164. //层序遍历
165. public void levelOrder(TreeNode root) {
166. if(root==null)return;
167. 
168.        Queue<TreeNode>qu=new LinkedList<>();
169.        qu.offer(root);
170. while(!qu.isEmpty()){
171. 
172.            TreeNode cur=qu.poll();
173.            System.out.print(cur.val+" ");
174. 
175. if(cur.left!=null)
176.                qu.offer(cur.left);
177. if(cur.right!=null)
178.                qu.offer(cur.right);
179. 
180.        }
181. 
182. 
183.     }
184. 
185. 
186. // 判断一棵树是不是完全二叉树
187. public boolean isCompleteTree(TreeNode root) {
188. if(root==null)return true;
189. 
190.        Queue<TreeNode>qu=new LinkedList<>();
191.        qu.offer(root);
192. while(!qu.isEmpty()){
193. 
194.            TreeNode cur=qu.poll();
195. if(cur!=null){
196.                qu.offer(cur.left);
197.                qu.offer(cur.right);
198.            }else{
199. break;
200.            }
201. 
202.        }
203. 
204. while(!qu.isEmpty()){
205.            TreeNode pop=qu.poll();
206. if(pop!=null)return false;
207. 
208.        }
209. return true;
210.     }
211. }

1. public class Test {
2. public static void main(String[] args) {
3.         BinaryTree binaryTree=new BinaryTree();
4. 
5.         binaryTree.preOrder(binaryTree.createTree());
6.         System.out.println();
7. 
8.         binaryTree.inOrder(binaryTree.createTree());
9. 
10.         System.out.println();
11.         binaryTree.postOrder(binaryTree.createTree());
12.         System.out.println();
13.         System.out.println(binaryTree.size(binaryTree.createTree()));
14.         System.out.println(binaryTree.size2(binaryTree.createTree()));
15.         System.out.println(binaryTree.getLeafNodeCount1(binaryTree.createTree()));
16.         System.out.println(binaryTree.getLeafNodeCount2(binaryTree.createTree()));
17.         System.out.println(binaryTree.getKLevelNodeCount(binaryTree.createTree(), 3));
18.         System.out.println(binaryTree.getHeight(binaryTree.createTree()));
19.         System.out.println("=========================");
20.         binaryTree.levelOrder(binaryTree.createTree());
21.         System.out.println(binaryTree.isCompleteTree(binaryTree.createTree()));
22. 
23. 
24.     }
25. }