二分搜索树的遍历
深度优先遍历
前序遍历:先访问当前节点,再依次递归访问左右子树;
中序遍历:先递归访问左子数,再访问自身,再递归访问右子树;
后序遍历:先递归访问左右子树,再访问自身节点;
广度优先遍历
- 层序遍历
前序遍历
public void preOrder() {
preOrder(root);
}
private void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.value);
preOrder(node.left);
preOrder(node.right);
}
中序遍历
public void inOrder() {
inOrder(root);
}
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.value);
inOrder(node.right);
}
后序遍历
// 后序遍历
public void postOrder() {
postOrder(root);
}
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value);
}
层序遍历
// 层序遍历
public void levelOrder() {
LinkedList<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
Node node = q.remove();
System.out.print(node.value);
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
}
}