diff options
| -rw-r--r-- | week3/BinaryTree.cs | 57 | ||||
| -rw-r--r-- | week3/Node.cs | 104 | ||||
| -rw-r--r-- | week3/Number.cs | 20 | ||||
| -rw-r--r-- | week3/Operand.cs | 31 |
4 files changed, 212 insertions, 0 deletions
diff --git a/week3/BinaryTree.cs b/week3/BinaryTree.cs new file mode 100644 index 0000000..8bed181 --- /dev/null +++ b/week3/BinaryTree.cs @@ -0,0 +1,57 @@ +using System; + +namespace ALGA { + public class BinaryTree { + public Node root; + + public void insert(int number) { + if (root == null) { + root = new Node(number); + return; + } + root.insert(number); + } + + public void delete(int number) { + if (root == null) return; + Node node = root.delete(number); + if (node == null) root = null; + } + + public bool exists(int number) { + if (root == null) return false; + return root.find(number) != null; + } + + public int min() { + if (root == null) return -1; + return root.min().number; + } + + public int max() { + if (root == null) return -1; + return root.max().number; + } + + public int depth() { + if (root == null) return 0; + return root.depth(); + } + + public int count() { + if (root == null) return 0; + return root.count(); + } + + public void print() { + if (root == null) return; + Console.WriteLine(string.Join(" ", root.flatten())); + } + + public void printInRange(int min, int max) { + if (root == null) return; + Console.WriteLine(string.Join(" ", root.flatten(min, max))); + } + } +} + diff --git a/week3/Node.cs b/week3/Node.cs new file mode 100644 index 0000000..4f1772a --- /dev/null +++ b/week3/Node.cs @@ -0,0 +1,104 @@ +using System; +using System.Collections.Generic; + +namespace ALGA { + public class Node { + public int number { get; private set; } + + public Node left = null; + public Node right = null; + + public Node(int number) { + this.number = number; + } + + public void insert(int value) { + if (number == value) return; + + if (value > number) { + if (right != null) + right.insert(value); + else + right = new Node(value); + } else { + if (left != null) + left.insert(value); + else + left = new Node(value); + } + } + + public Node delete(int value) { + return delete(this, value); + } + + private Node delete(Node here, int value) { + if (here == null) return null; + + if (value > here.number) here.right = delete(here.right, value); + else if (value < here.number) here.left = delete(here.left, value); + else { + if (here.left == null) return here.right; + if (here.right == null) return here.left; + + here.number = here.left.max().number; + here.left = delete(here.left, here.number); + } + + return here; + } + + public Node min() { + if (left == null) return this; + return left.min(); + } + + public Node max() { + if (right == null) return this; + return right.max(); + } + + public int count() { + int sum = 1; + if (left != null) sum += left.count(); + if (right != null) sum += right.count(); + return sum; + } + + public int depth() { + return depth(this); + } + private int depth(Node here) { + if (here == null) return 0; + return 1 + Math.Max(depth(here.left), depth(here.right)); + } + + public Node find(int value) { + if (number == value) return this; + if (value > number && right != null) return right.find(value); + if (value < number && left != null) return left.find(value); + return null; + } + + public List<int> flatten() { + List<int> flat = new List<int>(); + + if (left != null) flat.AddRange(left.flatten()); + flat.Add(number); + if (right != null) flat.AddRange(right.flatten()); + + return flat; + } + + public List<int> flatten(int min, int max) { + List<int> flat = new List<int>(); + + if (min < number && left != null) flat.AddRange(left.flatten(min, max)); + if (min <= number && number <= max) flat.Add(number); + if (right != null && number < max) flat.AddRange(right.flatten(min, max)); + + return flat; + } + } +} + diff --git a/week3/Number.cs b/week3/Number.cs new file mode 100644 index 0000000..2eb42bf --- /dev/null +++ b/week3/Number.cs @@ -0,0 +1,20 @@ +using System; + +namespace ALGA { + public class Number : Expression { + private int number; + + public Number(int number) { + this.number = number; + } + + public override String ToString() { + return $"{number}"; + } + + public override int evaluate() { + return number; + } + } +} + diff --git a/week3/Operand.cs b/week3/Operand.cs new file mode 100644 index 0000000..947f1de --- /dev/null +++ b/week3/Operand.cs @@ -0,0 +1,31 @@ +using System; + +namespace ALGA { + public class Operand : Expression { + private char operand; + private Expression left, right; + + public Operand(char operand, Expression left, Expression right) { + this.operand = operand; + this.left = left; + this.right = right; + } + + public override int evaluate() { + int a = left.evaluate(); + int b = right.evaluate(); + + switch (operand) { + case '+': return a + b; + case '*': return a * b; + } + + throw new NotImplementedException(); + } + + public override string ToString() { + return $"({left.ToString()}{operand}{right.ToString()})"; + } + } +} + |