migration C#, Java, C++ (day 12), binary tree

Trees are not difficult. They just require a little bit of practice in recursion. Today’s code uses the minimum framework. You can easily enhance this code for your purposes. Inherit from class Node or implement an interface in your personalized tree.
You have probably realized that I do not add new C++ fundamentals to learn in the C# to C++ series. The reason is that I do want to stay platform independent and also not use any non-standard classes.
Thus the code can be seen as pure training of C# to C++ translations.

tree as tree can

using System;

namespace Day12 {
  class Program {

    public class Node {
      public int key;
      public string description;
      public Node up = null;
      public Node down = null;
      public Node same = null;

      public Node(int xKey, string xDescription) { key = xKey; description = xDescription; }
    } // class


    public class BinaryTree {
      Node root;

      private void remove(Node xLeaf) {
        if (xLeaf == null) return;
        remove(xLeaf.same);
        remove(xLeaf.down);
        remove(xLeaf.up);
      } //

      private void insert(Node xNewLeaf, Node xLeaf) {
        // down
        if (xNewLeaf.key < xLeaf.key) {
          if (xLeaf.down != null) {
            insert(xNewLeaf, xLeaf.down);
            return;
          }
          xLeaf.down = xNewLeaf;
          return;
        }

        // up
        if (xNewLeaf.key > xLeaf.key) {
          if (xLeaf.up != null) {
            insert(xNewLeaf, xLeaf.up);
            return;
          }
          xLeaf.up = xNewLeaf;
          return;
        }

        // same
        if (xLeaf.same != null) insert(xNewLeaf, xLeaf.same);
        else xLeaf.same = xNewLeaf;
      } //

      public Node search(int xKey, Node xLeaf) {
        if (xLeaf != null) {
          if (xKey == xLeaf.key) return xLeaf;
          if (xKey < xLeaf.key) return search(xKey, xLeaf.down);
          else return search(xKey, xLeaf.up);
        }
        else return null;
      } //

      public void insert(Node xNewLeaf) {
        if (root != null) insert(xNewLeaf, root);
        else root = xNewLeaf;
      } //

      public Node search(int xKey) {
        return search(xKey, root);
      } //

      private void removeAll() {
        remove(root);
      } //

      public static void print(Node xLeaf, int xLevel, string xDirection) {
        if (xLeaf == null) return;

        for (int i = 0; i < xLevel; i++) { Console.Write(" "); }
        Console.WriteLine(xDirection + xLeaf.key + " " + xLeaf.description);
        xLevel++;
        print(xLeaf.same, xLevel, ".");
        print(xLeaf.down, xLevel, "-");
        print(xLeaf.up, xLevel, "+");
      } //

    } // class


    static void Main(string[] args) {
      BinaryTree lTree = new BinaryTree();
      Node lRoot = new Node(1975, "Despicable Me");
      lTree.insert(lRoot);
      lTree.insert(new Node(1926, "Elisabeth"));
      lTree.insert(new Node(1948, "Charles"));
      lTree.insert(new Node(1982, "William"));
      lTree.insert(new Node(1984, "Harry"));
      lTree.insert(new Node(1961, "Diana"));
      lTree.insert(new Node(1947, "Camilla"));
      lTree.insert(new Node(1921, "Phillip"));
      lTree.insert(new Node(1983, "Pippa"));
      lTree.insert(new Node(1982, "Catherine"));
      lTree.insert(new Node(1984, "George Orwell"));

      Node lSearchResult = lTree.search(1984);
      Console.WriteLine("found some nice guys in 1984: " + lSearchResult.description + " & " + lSearchResult.same.description + Environment.NewLine + Environment.NewLine);

      BinaryTree.print(lRoot, 0, "*");

      lTree = null;     // lTree.removeAll(); called by the garbage collector  

      Console.ReadKey();
    } //

  } // class
} // namespace

import java.io.IOException;

public class Program {

  public static class Node {

    public int key;
    public String description;
    public Node up = null;
    public Node down = null;
    public Node same = null;

    public Node(int xKey, String xDescription) {
      key = xKey;
      description = xDescription;
    } // constructor
  } // class

  public static class BinaryTree {

    private Node root;

    private void remove(Node xLeaf) {
      if (xLeaf == null)
        return;
      remove(xLeaf.same);
      remove(xLeaf.down);
      remove(xLeaf.up);
    } //

    private void insert(Node xNewLeaf, Node xLeaf) {
      // down
      if (xNewLeaf.key < xLeaf.key) {
        if (xLeaf.down != null) {
          insert(xNewLeaf, xLeaf.down);
          return;
        }
        xLeaf.down = xNewLeaf;
        return;
      } //

      // up
      if (xNewLeaf.key > xLeaf.key) {
        if (xLeaf.up != null) {
          insert(xNewLeaf, xLeaf.up);
          return;
        }
        xLeaf.up = xNewLeaf;
        return;
      } //

      // same
      if (xLeaf.same != null) insert(xNewLeaf, xLeaf.same);
      else xLeaf.same = xNewLeaf;
    } //

    public final Node search(int xKey, Node xLeaf) {
      if (xLeaf != null) {
        if (xKey == xLeaf.key)
          return xLeaf;
        if (xKey < xLeaf.key)
          return search(xKey, xLeaf.down);
        else
          return search(xKey, xLeaf.up);
      } else
        return null;
    } //

    public final void insert(Node xNewLeaf) {
      if (root != null)
        insert(xNewLeaf, root);
      else
        root = xNewLeaf;
    } // 

    public final Node search(int xKey) {
      return search(xKey, root);
    } //

    private void removeAll() {
      remove(root);
    } //

    public static void print(Node xLeaf, int xLevel, String xDirection) {
      if (xLeaf == null) return;

      for (int i = 0; i < xLevel; i++)
        System.out.print(" ");
      System.out.println(xDirection + xLeaf.key + " " + xLeaf.description);
      xLevel++;
      print(xLeaf.same, xLevel, ".");
      print(xLeaf.down, xLevel, "-");
      print(xLeaf.up, xLevel, "+");
    } //

  } // class

  public static void main(String[] args) {
    try {
      BinaryTree lTree = new BinaryTree();
      Node lRoot = new Node(1975, "Despicable Me");
      lTree.insert(lRoot);
      lTree.insert(new Node(1926, "Elisabeth"));
      lTree.insert(new Node(1948, "Charles"));
      lTree.insert(new Node(1982, "William"));
      lTree.insert(new Node(1984, "Harry"));
      lTree.insert(new Node(1961, "Diana"));
      lTree.insert(new Node(1947, "Camilla"));
      lTree.insert(new Node(1921, "Phillip"));
      lTree.insert(new Node(1983, "Pippa"));
      lTree.insert(new Node(1982, "Catherine"));
      lTree.insert(new Node(1984, "George Orwell"));

      Node lSearchResult = lTree.search(1984);
      System.out.println("found some nice guys in 1984: " + lSearchResult.description + " & " + lSearchResult.same.description + "\n\n");

      BinaryTree.print(lRoot, 0, "*");

      lTree = null; // lTree.removeAll(); called by the garbage collector

      System.in.read();
    } catch (IOException ex) {
      System.out.println("IOException: " + ex.getMessage());
    }
  } //

} // class
#include <functional>
#include <string>
#include <iostream>

using namespace std;


class Node {
public:
  int key;
  string description;
  Node *up = nullptr;
  Node *down = nullptr;
  Node *same = nullptr;

  Node(int xKey, const string &xDescription) { key = xKey; description = xDescription; }
}; // class


class BinaryTree {
public:
  BinaryTree() { root = nullptr; }
  ~BinaryTree() { removeAll(); }

  void insert(Node *xNewLeaf);
  Node *search(int xKey);
  static void print(Node *xLeaf, int xLevel, const string &xDirection);
  void removeAll();

private:
  void remove(Node *xLeaf);
  void insert(Node *xNewLeaf, Node *xLeaf);
  Node *search(int key, Node *xLeaf);

  Node *root;
}; // class

void BinaryTree::remove(Node *xLeaf) {
  if (xLeaf == nullptr) return;
  remove(xLeaf->same);
  remove(xLeaf->down);
  remove(xLeaf->up);
  delete xLeaf;
} //

void BinaryTree::insert(Node *xNewLeaf, Node *xLeaf) {
  // down
  if (xNewLeaf->key < xLeaf->key) {
    if (xLeaf->down != nullptr) {
      insert(xNewLeaf, xLeaf->down);
      return;
    }

    xLeaf->down = xNewLeaf;
    return;
  }

  // up
  if (xNewLeaf->key > xLeaf->key)  {
    if (xLeaf->up != nullptr) {
      insert(xNewLeaf, xLeaf->up);
      return;
    }

    xLeaf->up = xNewLeaf;
    return;
  }

  // same
  if (xLeaf->same != nullptr) insert(xNewLeaf, xLeaf->same);
  else xLeaf->same = xNewLeaf;
} //

Node *BinaryTree::search(int xKey, Node *xLeaf) {
  if (xLeaf != nullptr) {
    if (xKey == xLeaf->key) return xLeaf;
    if (xKey < xLeaf->key) return search(xKey, xLeaf->down);
    else return search(xKey, xLeaf->up);
  }
  else return nullptr;
} //

void BinaryTree::insert(Node *xNewLeaf) {
  if (root != nullptr) insert(xNewLeaf, root);
  else root = xNewLeaf;
} //

Node *BinaryTree::search(int xKey) {
  return search(xKey, root);
} //

void BinaryTree::removeAll() {
  remove(root);
} //

void BinaryTree::print(Node *xLeaf, int xLevel, const string &xDirection) {
  if (xLeaf == nullptr) return;
  
  for (int i = 0; i < xLevel; i++)  { cout << " "; }
  cout << xDirection << xLeaf->key << " " << xLeaf->description << endl;
  xLevel++;
  print(xLeaf->same, xLevel, ".");
  print(xLeaf->down, xLevel, "-");
  print(xLeaf->up, xLevel, "+");  
} //

void test() {

  BinaryTree lTree;
  Node *lRoot = new Node(1975, "Despicable Me");
  lTree.insert(lRoot);
  lTree.insert(new Node(1926, "Elisabeth"));
  lTree.insert(new Node(1948, "Charles"));
  lTree.insert(new Node(1982, "William"));
  lTree.insert(new Node(1984, "Harry"));
  lTree.insert(new Node(1961, "Diana"));
  lTree.insert(new Node(1947, "Camilla"));
  lTree.insert(new Node(1921, "Phillip"));
  lTree.insert(new Node(1983, "Pippa"));
  lTree.insert(new Node(1982, "Catherine"));
  lTree.insert(new Node(1984, "George Orwell"));

  Node *lSearchResult = lTree.search(1984);
  cout << "found some nice guys in 1984: " << lSearchResult->description << " & " << lSearchResult->same->description << endl;
  cout << endl << endl;

  lTree.print(lRoot, 0, "*");

  // lTree.removeAll();  called by the deconstructor
  cin.get();
} //
found some nice guys in 1984: Harry & George Orwell


*1975 Despicable Me
 -1926 Elisabeth
  -1921 Phillip
  +1948 Charles
   -1947 Camilla
   +1961 Diana
 +1982 William
  .1982 Catherine
  +1984 Harry
   .1984 George Orwell
   -1983 Pippa
Advertisements

About Bastian M.K. Ohta

Happiness only real when shared.

Posted on March 18, 2014, in C#, C++, Java and tagged , , , , , , , . Bookmark the permalink. 1 Comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: