java-二叉树广度优先实现、深度优先之前序实现(非递归)

小灰灰 2021-05-12 11:50 403阅读 0赞

深度优先遍历--->栈；

广度优先遍历--->队列；

这里以二叉树为例来实现。

Java代码   ![收藏代码][icon_star.png]

1.  **import** java.util.ArrayDeque;  
2.    
3.  **public** **class** BinaryTree \{  
4.      **static** **class** TreeNode\{  
5.          **int** value;  
6.          TreeNode left;  
7.          TreeNode right;  
8.            
9.          **public** TreeNode(**int** value)\{  
10.             **this**.value=value;  
11.         \}  
12.     \}  
13.       
14.     TreeNode root;  
15.       
16.     **public** BinaryTree(**int**\[\] array)\{  
17.         root=makeBinaryTreeByArray(array,1);  
18.     \}  
19.   
20.     /\*\* 
21.      \* 采用递归的方式创建一颗二叉树 
22.      \* 传入的是二叉树的数组表示法 
23.      \* 构造后是二叉树的二叉链表表示法 
24.      \*/  
25.     **public** **static** TreeNode makeBinaryTreeByArray(**int**\[\] array,**int** index)\{  
26.         **if**(index<array.length)\{  
27.             **int** value=array\[index\];  
28.             **if**(value!=0)\{  
29.                 TreeNode t=**new** TreeNode(value);  
30.                 array\[index\]=0;  
31.                 t.left=makeBinaryTreeByArray(array,index\*2);  
32.                 t.right=makeBinaryTreeByArray(array,index\*2\+1);  
33.                 **return** t;  
34.             \}  
35.         \}  
36.         **return** **null**;  
37.     \}  
38.       
39.     /\*\* 
40.      \* 深度优先遍历，相当于先根遍历 
41.      \* 采用非递归实现 
42.      \* 需要辅助数据结构：栈 
43.      \*/  
44.     **public** **void** depthOrderTraversal()\{  
45.         **if**(root==**null**)\{  
46.             System.out.println("empty tree");  
47.             **return**;  
48.         \}         
49.         ArrayDeque<TreeNode> stack=**new** ArrayDeque<TreeNode>();  
50.         stack.push(root);         
51.         **while**(stack.isEmpty()==**false**)\{  
52.             TreeNode node=stack.pop();  
53.             System.out.print(node.value+"    ");  
54.             **if**(node.right!=**null**)\{  
55.                 stack.push(node.right);  
56.             \}  
57.             **if**(node.left!=**null**)\{  
58.                 stack.push(node.left);  
59.             \}             
60.         \}  
61.         System.out.print("\\n");  
62.     \}  
63.   
64.     /\*\* 
65.      \* 广度优先遍历 
66.      \* 采用非递归实现 
67.      \* 需要辅助数据结构：队列 
68.      \*/  
69.     **public** **void** levelOrderTraversal()\{  
70.         **if**(root==**null**)\{  
71.             System.out.println("empty tree");  
72.             **return**;  
73.         \}  
74.         ArrayDeque<TreeNode> queue=**new** ArrayDeque<TreeNode>();  
75.         queue.add(root);  
76.         **while**(queue.isEmpty()==**false**)\{  
77.             TreeNode node=queue.remove();  
78.             System.out.print(node.value+"    ");  
79.             **if**(node.left!=**null**)\{  
80.                 queue.add(node.left);  
81.             \}  
82.             **if**(node.right!=**null**)\{  
83.                 queue.add(node.right);  
84.             \}  
85.         \}  
86.         System.out.print("\\n");  
87.     \}  
88.       
89.     /\*\*  
90.      \*                  13 
91.      \*                 /  \\ 
92.      \*               65    5 
93.      \*              /  \\    \\ 
94.      \*             97  25   37 
95.      \*            /    /\\   / 
96.      \*           22   4 28 32 
97.      \*/  
98.     **public** **static** **void** main(String\[\] args) \{  
99.         **int**\[\] arr=\{ 0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0\};  
100.         BinaryTree tree=**new** BinaryTree(arr);  
101.         tree.depthOrderTraversal();  
102.         tree.levelOrderTraversal();  
103.     \}  
104. \} 
105. 运行结果：
106. 13    65    97    22    25    4    28    5    37    32      
    13    65    5    97    25    37    22    4    28    32

注：深度优先(前、中、后序)可以使用递归、非递归实现；广度优先一般都采用非递归实现，递归不太好完成！

[icon_star.png]: /images/20210511/e7c5ed16481a4f92a7eaa5dd2bf44081.png