fork(1) download
copy 
  1. /* cs */
  2. using System;
  3.  
  4. class Node<T> where T : struct, IComparable { 
  5.   private T key;
  6.   private Node<T> left, right;
  7.   public Node(T key) {
  8.     this.left = this.right = null;
  9.     this.key = key;
  10.   }
  11.  
  12.   public static void insertNode<S>(ref Node<S> root, S key) where S : struct, IComparable {
  13.     if (root == null) {
  14.       root = new Node<S>(key);
  15.       return;
  16.     }
  17.     if (key.CompareTo(root.key) < 0)
  18.       insertNode<S>(ref root.left, key);
  19.     else
  20.       insertNode<S>(ref root.right, key);
  21.   }
  22.  
  23.   public static bool deleteNode<S>(ref Node<S> root, S key) where S : struct, IComparable {
  24.     if (root == null) return false;
  25.     if (key.CompareTo(root.key) < 0)
  26.       return deleteNode<S>(ref root.left, key);
  27.     else if (key.CompareTo(root.key) > 0)
  28.       return deleteNode<S>(ref root.right, key);
  29.     else {
  30.       if (root.left == null) {
  31.         root = root.right;
  32.       } else if (root.right == null) {
  33.         root = root.left;
  34.       } else { // root.left != null && root.right != null
  35.         Node<S> p;
  36.         for (p = root.left; p.right != null; p = p.right)
  37.           ;
  38.         p.right = root.right;
  39.         root = root.left;
  40.       }
  41.     }
  42.     return true;
  43.   }
  44.  
  45.   public void vomitTree<S>(int c) where S : struct, IComparable {
  46.     if (this.left != null)
  47.       this.left.vomitTree<S>(c + 3);
  48.     for (int i = 0; i < c; i++) System.Console.Write(' ');
  49.     System.Console.WriteLine(this.key);
  50.     if (this.right != null)
  51.       this.right.vomitTree<S>(c + 3);
  52.   }
  53. };
  54.  
  55. class BinaryTree {
  56.   private Node<int> root;
  57.   public BinaryTree() { this.root = null; }
  58.   public void insertNode(int key) { Node<int>.insertNode<int>(ref this.root, key); }
  59.   public bool deleteNode(int key) { return Node<int>.deleteNode<int>(ref this.root, key); } 
  60.   public void vomitTree() { if (this.root != null) this.root.vomitTree<int>(0); }
  61. };
  62.  
  63. class Sample{
  64.   public static void Main() {
  65.     BinaryTree tree = new BinaryTree();
  66.     for (;;) {
  67.       System.Console.Write("> ");
  68.       int input = int.Parse(System.Console.ReadLine());
  69.       if (input < 0)
  70.         break;
  71.       tree.insertNode(input);
  72.       tree.vomitTree();
  73.     }
  74.     System.Console.WriteLine("deleting.");
  75.     for (;;) {
  76.       System.Console.Write("> ");
  77.       int input = int.Parse(System.Console.ReadLine());
  78.       if (input < 0)
  79.         break;
  80.       if (tree.deleteNode(input))
  81.         System.Console.WriteLine("deleted.");
  82.       else
  83.         System.Console.WriteLine("not found.");
  84.       tree.vomitTree();
  85.     }
  86.   }
  87. }
  88. /* end */
  89.  
Success #stdin #stdout 0.04s 33736KB
comments (?)
stdin
copy 
10
5
15
1
8
12
20
-1
5
10
15
100
8
12
20
100
1
1
-1
stdout
copy 
> 10
>    5
10
>    5
10
   15
>       1
   5
10
   15
>       1
   5
      8
10
   15
>       1
   5
      8
10
      12
   15
>       1
   5
      8
10
      12
   15
      20
> deleting.
> deleted.
   1
      8
10
      12
   15
      20
> deleted.
1
   8
         12
      15
         20
> deleted.
1
   8
      12
         20
> not found.
1
   8
      12
         20
> deleted.
1
   12
      20
> deleted.
1
   20
> deleted.
1
> not found.
1
> deleted.
> not found.
>
https://ideone.com/vQpT1F
language:
C# (gmcs 5.20.1)
created:
10 years 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!