[go: up one dir, main page]
Scribd
Upload
12 views3 pages

Binary Tree

The document contains a Java implementation of a Binary Search Tree (BST) with methods for inserting, searching, deleting, updating nodes, performing in-order traversal, and breadth-first search (BFS). It defines a private inner class TreeNode to represent each node in the tree. The implementation includes error handling for various operations and uses a queue for the BFS method.

Uploaded by

Hữu Minh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
12 views3 pages

Binary Tree

The document contains a Java implementation of a Binary Search Tree (BST) with methods for inserting, searching, deleting, updating nodes, performing in-order traversal, and breadth-first search (BFS). It defines a private inner class TreeNode to represent each node in the tree. The implementation includes error handling for various operations and uses a queue for the BFS method.

Uploaded by

Hữu Minh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 3

import java.util.

LinkedList;
import java.util.Queue;

public class BinarySearchTree {

private TreeNode root;

private class TreeNode {


private int data;
private TreeNode left;
private TreeNode right;

public TreeNode(int data) {


this.data = data;
}
}

public void insert(int value) {


root = insert(root, value);
}

public TreeNode insert(TreeNode root, int value) {


if (root == null) {
root = new TreeNode(value);
return root;
}
if (value < root.info) { // str1.compareTo(str2) < 0
root.left = insert(root.left, value);
} else if(value > root.info){ // str1.compareTo(str2) < 0
root.right = insert(root.right, value);
}
return root;
}

public void inOrder() {


inOrder(root);
}

public void inOrder(TreeNode root) {


if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}

public TreeNode search(int key) {


return search(root, key);
}

public TreeNode search(TreeNode root, int key) {


if (root == null || root.data == key) {
return root;
}

if (key < root.data) {


return search(root.left, key);
} else {
return search(root.right, key);
}

}
public void delete(int key) {
root = delete(root, key);
}

private TreeNode delete(TreeNode root, int key) {


if (root == null) {
return root;
}

if (key < root.data) {


root.left = delete(root.left, key);
} else if (key > root.data) {
root.right = delete(root.right, key);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}

root.data = minValue(root.right);

root.right = delete(root.right, root.data);


}

return root;
}

private int minValue(TreeNode root) {


int minValue = root.data;
while (root.left != null) {
minValue = root.left.data;
root = root.left;
}
return minValue;
}

public void update(int key, int newValue) {


root = update(root, key, newValue);
}

private TreeNode update(TreeNode root, int key, int newValue) {


if (root == null) {
return root;
}

if (key < root.data) {


root.left = update(root.left, key, newValue);
} else if (key > root.data) {
root.right = update(root.right, key, newValue);
} else {
root.data = newValue;
}
return root;
}
public void bfs() {
bfs(root);
}
// Các bạn dùng queue có trong source hoặc import thư viện vào đều được
private void bfs(TreeNode root) {
if (root == null) {
return;
}

Queue<TreeNode> queue = new LinkedList<>();


queue.add(root);

while (!queue.isEmpty()) {
TreeNode currentNode = queue.poll();
System.out.print(currentNode.data + " ");

if (currentNode.left != null) {
queue.add(currentNode.left);
}

if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
}
}

You might also like