Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Stack;
- public class BinaryTree {
- Node root;
- public void add(int value) {
- root = add(root, value);
- }
- private Node add(Node current, int value) {
- if (current == null) {
- return new Node(value);
- }
- if (value < current.value) {
- current.left = add(current.left, value);
- } else if (value > current.value) {
- current.right = add(current.right, value);
- }
- return current;
- }
- public void delete(int value) {
- root = delete(root, value);
- }
- private Node delete(Node current, int value) {
- if (current == null) {
- return null;
- }
- if (value == current.value) {
- // Case 1: no children
- if (current.left == null && current.right == null) {
- return null;
- }
- // Case 2: only 1 child
- if (current.right == null) {
- return current.left;
- }
- if (current.left == null) {
- return current.right;
- }
- // Case 3: 2 children
- int smallestValue = findSmallestValue(current.right);
- current.value = smallestValue;
- current.right = delete(current.right, smallestValue);
- return current;
- }
- if (value < current.value) {
- current.left = delete(current.left, value);
- return current;
- }
- current.right = delete(current.right, value);
- return current;
- }
- private int findSmallestValue(Node root) {
- return root.left == null ? root.value : findSmallestValue(root.left);
- }
- public int Depth (){
- return maxDepth(root);
- }
- private int maxDepth(Node node) {
- if (node == null)
- return 0;
- else {
- int lDepth = maxDepth(node.left);
- int rDepth = maxDepth(node.right);
- if (lDepth > rDepth)
- return (lDepth + 1);
- else
- return (rDepth + 1);
- }
- }
- public void traverseInOrder() {
- Stack<Node> stack = new Stack<Node>();
- Node current = root;
- stack.push(root);
- while(! stack.isEmpty()) {
- while(current.left != null) {
- current = current.left;
- stack.push(current);
- }
- current = stack.pop();
- printVal(current.value);
- if(current.right != null) {
- current = current.right;
- stack.push(current);
- }
- }
- }
- public void traversePreOrder() {
- Stack<Node> stack = new Stack<Node>();
- Node current = root;
- stack.push(root);
- while(! stack.isEmpty()) {
- current = stack.pop();
- printVal(current.value);
- if(current.right != null)
- stack.push(current.right);
- if(current.left != null)
- stack.push(current.left);
- }
- }
- public void traversePostOrder() {
- Stack<Node> stack = new Stack<Node>();
- Node prev = root;
- Node current = root;
- stack.push(root);
- while (!stack.isEmpty()) {
- current = stack.peek();
- boolean hasChild = (current.left != null || current.right != null);
- boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null));
- if (!hasChild || isPrevLastChild) {
- current = stack.pop();
- printVal(current.value);
- prev = current;
- } else {
- if (current.right != null) {
- stack.push(current.right);
- }
- if (current.left != null) {
- stack.push(current.left);
- }
- }
- }
- }
- private void printVal(int value) {
- System.out.print(" " + value);
- }
- public void traverseLevelOrder() {
- if (root == null) {
- return;
- }
- Queue<Node> nodes = new LinkedList<>();
- nodes.add(root);
- while (!nodes.isEmpty()) {
- Node node = nodes.remove();
- System.out.print(" " + node.value);
- if (node.left != null) {
- nodes.add(node.left);
- }
- if (node.right!= null) {
- nodes.add(node.right);
- }
- }
- }
- public void rttraverseLevelOrder() {
- if (root == null) {
- return;
- }
- Queue<Node> nodes = new LinkedList<>();
- nodes.add(root);
- while (!nodes.isEmpty()) {
- Node node = nodes.remove();
- System.out.print(" " + node.value);
- if (node.left != null) {
- nodes.add(node.left);
- }
- if (node.right!= null) {
- nodes.add(node.right);
- }
- }
- }
- class Node {
- int value;
- Node left;
- Node right;
- Node(int value) {
- this.value = value;
- right = null;
- left = null;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement