fork download
copy 
  1.  
  2.  
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Xml.Linq;
  6.  
  7. class Program
  8. {
  9.     public static int Counter = 0;
  10.     static void Main()
  11.     {
  12.         BCT btree = new BCT();
  13.         btree.Insert(10);
  14.         btree.Insert(20);
  15.         btree.Insert(5);
  16.         btree.Insert(7);
  17.         btree.Insert(8);
  18.         btree.Insert(0);
  19.         btree.Insert(30);
  20.         btree.Print(); // 0 3 6 7 9 13 20 
  21.  
  22.     }
  23.  
  24.     public static int Fibo(int n)
  25.     {
  26.         Counter++;
  27.         if (n == 0) return 0;
  28.         if (n == 1) return 1;
  29.  
  30.         int left = Fibo(n - 1);
  31.         int right = Fibo(n - 2);
  32.         return left + right;
  33.     }
  34.  
  35.     public class TreeNode
  36.     {
  37.         public TreeNode Left;
  38.         public TreeNode Right;
  39.         public int Value;
  40.  
  41.         public TreeNode(int value)
  42.         {
  43.             Value = value;
  44.         }
  45.     }
  46.  
  47.     public class BTree
  48.     {
  49.         public TreeNode Root;
  50.  
  51.         public void Insert(int value)
  52.         {
  53.             InsertNode(Root, value);
  54.         }
  55.  
  56.         private void InsertNode(TreeNode node, int value)
  57.         {
  58.             // 1. Base case (nothing exists)
  59.             if (Root == null)
  60.             {
  61.                 Root = new TreeNode(value);
  62.                 return;
  63.             }
  64.             // 2. General case (smth exists)
  65.             if (value < node.Value)
  66.             {
  67.                 // Exit point
  68.                 if (node.Left == null)
  69.                 {
  70.                     node.Left = new TreeNode(value);
  71.                     return;
  72.                 }
  73.                 else
  74.                 {
  75.                     InsertNode(Root.Left, value);
  76.                 }
  77.             }
  78.             else if (value > node.Value)
  79.             {
  80.                 // Exit point
  81.                 if (node.Right == null)
  82.                 {
  83.                     node.Right = new TreeNode(value);
  84.                     return;
  85.                 }
  86.                 else
  87.                 {
  88.                     InsertNode(Root.Right, value);
  89.                 }
  90.             }
  91.         }
  92.  
  93.         public bool Contains(int value)
  94.         {
  95.             return ContainsNode(Root, value);
  96.         }
  97.  
  98.         private bool ContainsNode(TreeNode node, int value)
  99.         {
  100.             if (node == null) return false;
  101.             if (value < node.Value) return ContainsNode(node.Left, value);
  102.             if (value > node.Value) return ContainsNode(node.Right, value);
  103.             return true;
  104.         }
  105.  
  106.         public void Print()
  107.         {
  108.             PrintTree(Root);
  109.  
  110.         }
  111.         private void PrintTree(TreeNode root)
  112.         {
  113.             if (root == null) return;
  114.             PrintTree(root.Left);
  115.             Console.WriteLine(root.Value);
  116.             PrintTree(root.Right);
  117.  
  118.         }
  119.  
  120.     }
  121.  
  122.     public class MyDictionary<TKey, TValue>
  123.     {
  124.         private LinkedList<KeyValuePair<TKey, TValue>>[] _buckets;
  125.  
  126.         private const int DefaultCapacity = 10;
  127.  
  128.         public MyDictionary(int defaultCapacity = DefaultCapacity)
  129.         {
  130.             if (defaultCapacity < 0) defaultCapacity = DefaultCapacity;
  131.  
  132.             _buckets = new LinkedList<KeyValuePair<TKey, TValue>>[defaultCapacity];
  133.         }
  134.  
  135.         private int GetIndex(TKey key)
  136.         {
  137.             int hash = Math.Abs(key.GetHashCode());
  138.  
  139.             return hash % _buckets.Length;
  140.         }
  141.  
  142.         public bool AddOrUpdate(TKey key, TValue value)
  143.         {
  144.             int index = GetIndex(key);
  145.  
  146.             if (_buckets[index] == null)
  147.             {
  148.                 _buckets[index] = new LinkedList<KeyValuePair<TKey, TValue>>();
  149.             }
  150.  
  151.             LinkedList<KeyValuePair<TKey, TValue>> list = _buckets[index];
  152.  
  153.             foreach (var pair in list)
  154.             {
  155.                 if (pair.Key.Equals(key))
  156.                 {
  157.                     list.Remove(pair);
  158.                     list.AddLast(new KeyValuePair<TKey, TValue>(key, value));
  159.                     return false; // no new element was added, but previous was updated
  160.                 }
  161.             }
  162.  
  163.             list.AddLast(new KeyValuePair<TKey, TValue>(key, value));
  164.  
  165.             return true;
  166.         }
  167.  
  168.         public bool TryGetValue(TKey key, out TValue value)
  169.         {
  170.             int index = GetIndex(key);
  171.  
  172.             if (_buckets[index] != null)
  173.             {
  174.                 LinkedList<KeyValuePair<TKey, TValue>> list = _buckets[index];
  175.  
  176.                 foreach (var pair in list)
  177.                 {
  178.                     if (pair.Key.Equals(key))
  179.                     {
  180.                         value = pair.Value;
  181.                         return true;
  182.                     }
  183.                 }
  184.             }
  185.  
  186.             value = default;
  187.             return false;
  188.         }
  189.  
  190.         public bool Remove(TKey key)
  191.         {
  192.             int index = GetIndex(key);
  193.  
  194.             if (_buckets[index] != null)
  195.             {
  196.                 LinkedList<KeyValuePair<TKey, TValue>> list = _buckets[index];
  197.  
  198.                 foreach (var pair in list)
  199.                 {
  200.                     if (pair.Key.Equals(key))
  201.                     {
  202.                         list.Remove(pair);
  203.                         return true;
  204.                     }
  205.                 }
  206.             }
  207.  
  208.             return false;
  209.         }
  210.  
  211.         public bool ContainsKey(TKey key)
  212.         {
  213.             int index = GetIndex(key);
  214.  
  215.             if (_buckets[index] != null)
  216.             {
  217.                 return true;
  218.             }
  219.  
  220.             return false;
  221.         }
  222.  
  223.         public TValue this[TKey key]
  224.         {
  225.             get
  226.             {
  227.                 TValue dummy = default;
  228.                 TryGetValue(key, out dummy);
  229.                 return dummy;
  230.             }
  231.             set
  232.             {
  233.                 AddOrUpdate(key, value);
  234.             }
  235.         }
  236.     }
  237.  
  238.     public class BCT
  239.     {
  240.         TreeNode root;
  241.         Queue<TreeNode> queue = new Queue<TreeNode>();
  242.  
  243.         public void Insert(int value)
  244.         {
  245.             if (root == null)
  246.             {
  247.                 root = new TreeNode(value);
  248.                 queue.Enqueue(root);
  249.                 return;
  250.             }
  251.             TreeNode top = queue.Peek();
  252.             if (top.Left == null)
  253.             {
  254.                 top.Left = new TreeNode(value);
  255.                 queue.Enqueue(top.Left);
  256.             }
  257.             else if (top.Right == null)
  258.             {
  259.                 top.Right = new TreeNode(value);
  260.                 queue.Enqueue(top.Right);
  261.             }
  262.  
  263.             if (top.Left != null && top.Right != null)
  264.                 queue.Dequeue();
  265.         }
  266.  
  267.         public void Print()
  268.         {
  269.             Queue<TreeNode> qq = new Queue<TreeNode>();
  270.             qq.Enqueue(root);
  271.  
  272.             while (qq.Count > 0)
  273.             {
  274.                 TreeNode current = qq.Dequeue();
  275.                 Console.Write(current.Value+" ");
  276.                 if (current.Left != null) qq.Enqueue(current.Left);
  277.                 if (current.Right != null) qq.Enqueue(current.Right);
  278.  
  279.             }
  280.         }
  281.     }
  282.  
  283.  
  284. }
  285.  
  286.  
Success #stdin #stdout 0.04s 28824KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
10 20 5 7 8 0 30
https://ideone.com/qUw7Wp
language:
C# (NET 6.0)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!