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