Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.IO;
- namespace ConsoleAppCS
- {
- class Program
- {
- static void Main(string[] args)
- {
- BinTree tree = new BinTree();
- using (StreamReader sr = new StreamReader("input.txt"))
- {
- string[] toks = sr.ReadLine().Split();
- foreach (string s in toks)
- tree.Add(int.Parse(s));
- }
- Console.WriteLine("tree.IsBalanced(): {0}", tree.IsBalanced());
- Tuple<object, object> res = tree.CanBeBalanced();
- if (res == null)
- Console.WriteLine("Can't balance the tree...");
- else if (res.Item1 == null)
- Console.WriteLine("Tree is already balanced!");
- else
- {
- Console.WriteLine("Tree can be balanced with element from {0} to {1}", res.Item1, res.Item2);
- Console.WriteLine("Adding {0}", res.Item1);
- tree.Add(res.Item1);
- Console.WriteLine("tree.IsBalanced(): {0}", tree.IsBalanced());
- }
- }
- }
- }
- using System;
- namespace ConsoleAppCS
- {
- internal class BinTree
- {
- class Node
- {
- public object value;
- public Node leftChild, rightChild;
- public int Counter { get; private set; }
- public Node(object value)
- {
- this.value = value;
- leftChild = rightChild = null;
- Counter = 1;
- }
- public static void Add(ref Node r, object value)
- {
- if (r == null)
- r = new Node(value);
- else
- {
- ++r.Counter;
- if (((IComparable)value).CompareTo(r.value) < 0)
- Add(ref r.leftChild, value);
- else
- Add(ref r.rightChild, value);
- }
- }
- public static void PrintInorder(Node r)
- {
- if (r != null)
- {
- PrintInorder(r.leftChild);
- Console.Write(r.value + " ");
- PrintInorder(r.rightChild);
- }
- }
- public static void PrintPreorder(Node r)
- {
- if (r != null)
- {
- Console.Write(r.value + " ");
- PrintPreorder(r.leftChild);
- PrintPreorder(r.rightChild);
- }
- }
- public static void PrintPostorder(Node r)
- {
- if (r != null)
- {
- PrintPostorder(r.leftChild);
- PrintPostorder(r.rightChild);
- Console.Write(r.value + " ");
- }
- }
- public static Node Search(Node r, object value)
- {
- if (r == null)
- return null;
- int cmpRes = ((IComparable)r.value).CompareTo(value);
- if (cmpRes == 0)
- return r;
- else if (cmpRes > 0)
- return Search(r.leftChild, value);
- else return Search(r.rightChild, value);
- }
- public static bool Delete(ref Node r, object key)
- {
- if (r == null)
- return false;
- int cmpRes = ((IComparable)r.value).CompareTo(key);
- if (cmpRes > 0)
- if (Delete(ref r.leftChild, key))
- {
- --r.Counter;
- return true;
- }
- else return false;
- else if (cmpRes < 0)
- if (Delete(ref r.rightChild, key))
- {
- --r.Counter;
- return true;
- }
- else return false;
- else if (r.leftChild == null)
- r = r.rightChild;
- else if (r.rightChild == null)
- r = r.leftChild;
- else Del(r, ref r.leftChild);
- return true;
- }
- private static void Del(Node r, ref Node l)
- {
- if (l.rightChild != null)
- Del(r, ref l.rightChild);
- else
- {
- r.value = l.value;
- l = l.leftChild;
- }
- }
- public static bool CanBeBalanced(ref Node r, ref object min, ref object max, ref bool needsTo)
- {
- if (r == null)
- return true;
- int lc = r.leftChild != null ? r.leftChild.Counter : 0;
- int rc = r.rightChild != null ? r.rightChild.Counter : 0;
- int diff = lc - rc;
- if (Math.Abs(diff) > 2)
- return false;
- if (Math.Abs(diff) == 2)
- needsTo = true;
- if (diff > 0)
- {
- min = r.value;
- return CanBeBalanced(ref r.rightChild, ref min, ref max, ref needsTo) && IsBalanced(r.leftChild);
- }
- else if (diff < 0)
- {
- max = (int)r.value - 1;
- return CanBeBalanced(ref r.leftChild, ref min, ref max, ref needsTo) && IsBalanced(r.rightChild);
- }
- else
- {
- object tempMin = r.value, tempMax = max;
- bool tmpNeeds = needsTo;
- if (CanBeBalanced(ref r.rightChild, ref tempMin, ref tempMax, ref tmpNeeds) && IsBalanced(r.leftChild))
- {
- min = tempMin;
- max = tempMax;
- needsTo = tmpNeeds;
- return true;
- }
- max = (int)r.value - 1;
- return CanBeBalanced(ref r.leftChild, ref min, ref max, ref needsTo) && IsBalanced(r.rightChild);
- }
- }
- public static bool IsBalanced(Node r)
- {
- if (r == null)
- return true;
- int lc = r.leftChild == null ? 0 : r.leftChild.Counter;
- int rc = r.rightChild == null ? 0 : r.rightChild.Counter;
- int diff = Math.Abs(lc - rc);
- return diff <= 1 && IsBalanced(r.leftChild) && IsBalanced(r.rightChild);
- }
- }
- Node root;
- object minElem, maxElem;
- public BinTree()
- {
- root = null;
- }
- private BinTree(Node root)
- {
- this.root = root;
- }
- public void Add(object value)
- {
- if (minElem == null || ((IComparable)value).CompareTo(minElem) < 0)
- minElem = value;
- if (maxElem == null || ((IComparable)value).CompareTo(maxElem) > 0)
- maxElem = value;
- Node.Add(ref root, value);
- }
- public void PrintInorder()
- {
- Node.PrintInorder(root);
- Console.WriteLine();
- }
- public void PrintPreorder()
- {
- Node.PrintPreorder(root);
- Console.WriteLine();
- }
- public void PrintPostorder()
- {
- Node.PrintPostorder(root);
- Console.WriteLine();
- }
- public BinTree Search(object value)
- {
- return new BinTree(Node.Search(root, value));
- }
- public void Delete(object key)
- {
- Node.Delete(ref root, key);
- if (key == minElem)
- {
- Node el = root;
- while (el.leftChild != null)
- el = el.leftChild;
- minElem = el.leftChild.value;
- }
- if (key == maxElem)
- {
- Node el = root;
- while (el.rightChild != null)
- el = el.rightChild;
- maxElem = el.rightChild.value;
- }
- }
- public bool IsBalanced()
- {
- return Node.IsBalanced(root);
- }
- public Tuple<object, object> CanBeBalanced()
- {
- object min = (int)minElem - 1, max = (int)maxElem + 1;
- bool needs = false;
- bool res = Node.CanBeBalanced(ref root, ref min, ref max, ref needs);
- if (res)
- {
- if (needs)
- return new Tuple<object, object>(min, max);
- else
- return new Tuple<object, object>(null, null);
- }
- return null;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement