add week 3

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()})";
+		}
+	}
+}
+