Binary tree

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a triple (L, S,R), where L and R are binary trees or the empty set and S is a singleton set.Some authors allow the binary tree to be the empty set as well.       

   

For more understanding visit this link 

For visualization visit this link

Node.h

#include <iostream>

using namespace std;

class Node {
public:
 Node ();
 Node (int a);
 ~Node ();
 void SetValue (int a);
 int GetValue ();
 void SetLeft (Node* L);
 Node* GetLeft ();
 void SetRight (Node* R);
 Node* GetRight ();
private:
 int Value;
 Node* Left;
 Node* Right;
};

Node :: Node () {
 Value = 0;
 Left = NULL;
 Right = NULL;
}

Node :: Node (int a) {
 Value = a;
 Left = NULL;
 Right = NULL;

}

Node :: ~Node () {
 delete Left;
 delete Right;
}

void Node :: SetValue (int a) {
 Value = a;
}

int Node :: GetValue () {
 return Value;
}

void Node :: SetLeft (Node* L) {
 Left = L;
}

Node* Node :: GetLeft () {
 return Left;
}

void Node :: SetRight (Node* R) {
 Right = R;
}

Node* Node :: GetRight () {
 return Right;
}

BT.h

#include "Node.h"

class BT {
public:
 BT ();
 ~BT ();
 void SetRoot(Node* R);
 Node* GetRoot ();
 void Insert (int a);
 void PreOrder (Node* N);
 Node* FindMin (Node* N);
 Node* Delete (Node* N, int a);
private:
 Node* Root;
};

BT :: BT () {
 Root = NULL;
}

BT :: ~BT () {
 delete Root;
}

void BT :: SetRoot(Node* R) {
 Root = R;
}

Node* BT :: GetRoot () {
 return Root;
}

void BT :: Insert (int a) {
 if (GetRoot () == NULL) {
  Node* NN = new Node (a);
  SetRoot (NN);
 }
 else {
  Node *p, *q;
  p = q = GetRoot();
  while (p->GetValue() != a && q != NULL ) {
   p = q;
   if (p->GetValue() < a)
    q = p->GetRight();
   else
    q = p->GetLeft();
  }

  if (p->GetValue() == a)
   cout << "Duplicate Value" << endl;
  else if (p->GetValue() < a) {
   Node* NN = new Node(a);
   p->SetRight(NN);
  }
  else {
   Node* NN = new Node(a);
   p->SetLeft(NN);
  }
 }
}

void BT :: PreOrder (Node* N) {
 if (N != NULL) {
  cout << N->GetValue() << endl;
  PreOrder(N->GetLeft());
  PreOrder (N->GetRight());
 }
}

Node* BT :: FindMin (Node* N) {
 if (N == NULL) return N;
 else if (N->GetLeft() == NULL) return N;
 else FindMin (N->GetLeft());
}

Node* BT :: Delete (Node* N, int a) {
 Node *NN;
 if (a < N->GetValue()) {
  NN = Delete(N->GetLeft(), a);
  N->SetLeft(NN);
 }
 else if (a > N->GetValue()) {
  NN = Delete(N->GetRight(), a);
  N->SetRight(NN);
 }
 else if (N->GetLeft() != NULL && N->GetRight() != NULL) {
  Node* MN = FindMin (N->GetRight());
  N->SetValue (MN->GetValue());
  NN = Delete (N->GetRight(), MN->GetValue());
  N->SetRight(NN);
 }
 else {
  if (N->GetRight() == NULL) {
   N = N->GetLeft();
  }
  else if (N->GetLeft() == NULL) {
   N = N->GetRight();
  }
  else N = NULL;
 }
 return N;
}

main.cpp

#include "BT.h"

int main () {
 BT ob;
 ob.Insert(25);
 ob.Insert(86);
 ob.Insert(69);
 ob.Insert(25);
 ob.PreOrder(ob.GetRoot());
 cout << (ob.FindMin(ob.GetRoot()))->GetValue() << endl;
 cout << (ob.FindPreviousNode(69))->GetValue() << endl;
 ob.delete(ob.GetRoot(),86);
 return 0;
}