Java 中 BST 的层序遍历
Level Order Traversal of BST in Java
我正在尝试对以下 BST 进行层序遍历。
BST bst = new BST();
int [] arr = {12, 15, 7, 3, 81, 9, 36, 23, 33, 41, 4};
for (int i = 0; i <arr.length; i++) {
bst.add(arr[i]);
}
这是我的代码。
public static void levelOrderTraversal(Node root){
if(root == null) return;
Queue<Node> queue = new ArrayDeque<Node>();
queue.add(root);
while(!queue.isEmpty()){
Node current = queue.peek();
System.out.print(current.getData() + " ");
if (current.left != null)
queue.add(current.left);
if (current.right != null){
queue.add(current.right);
}
queue.poll();
}
}
我得到的输出是
12 7 15 3 9 81 4 36 23 41 33
这显然不是正确的 BFS。我哪里错了。
我不明白为什么,鉴于您提供的元素列表,树将如下所示:
12
|- 7 (L)
|- 3 (L)
|- 4 (R)
|- 9 (R)
|- 15 (R)
|- 81 (R)
|- 36 (L)
|- 23 (L)
|- 33 (R)
|- 41 (R)
或者更好的视觉效果:
12
/ \
7 15
/ \ \
3 9 81
\ /
4 36
/ \
23 41
\
33
请注意,这不是 平衡 二叉搜索树。 BST 将首先简单地创建一个节点 12
(您提供的第一个元素)。 12
将保留为根。所有小于的元素都向左排序(并开始生长自己的根等)
你的遍历函数是正确的。您可能需要查看此在线工具
https://www.cs.usfca.edu/~galles/visualization/BST.html
它还提供插入、删除和查找过程的可视化。这是生成的树:
我正在尝试对以下 BST 进行层序遍历。
BST bst = new BST();
int [] arr = {12, 15, 7, 3, 81, 9, 36, 23, 33, 41, 4};
for (int i = 0; i <arr.length; i++) {
bst.add(arr[i]);
}
这是我的代码。
public static void levelOrderTraversal(Node root){
if(root == null) return;
Queue<Node> queue = new ArrayDeque<Node>();
queue.add(root);
while(!queue.isEmpty()){
Node current = queue.peek();
System.out.print(current.getData() + " ");
if (current.left != null)
queue.add(current.left);
if (current.right != null){
queue.add(current.right);
}
queue.poll();
}
}
我得到的输出是
12 7 15 3 9 81 4 36 23 41 33
这显然不是正确的 BFS。我哪里错了。
我不明白为什么,鉴于您提供的元素列表,树将如下所示:
12
|- 7 (L)
|- 3 (L)
|- 4 (R)
|- 9 (R)
|- 15 (R)
|- 81 (R)
|- 36 (L)
|- 23 (L)
|- 33 (R)
|- 41 (R)
或者更好的视觉效果:
12
/ \
7 15
/ \ \
3 9 81
\ /
4 36
/ \
23 41
\
33
请注意,这不是 平衡 二叉搜索树。 BST 将首先简单地创建一个节点 12
(您提供的第一个元素)。 12
将保留为根。所有小于的元素都向左排序(并开始生长自己的根等)
你的遍历函数是正确的。您可能需要查看此在线工具
https://www.cs.usfca.edu/~galles/visualization/BST.html
它还提供插入、删除和查找过程的可视化。这是生成的树: