Sa

#include <iostream>
#include <queue>

using std::cin;
using std::cout;

struct Btnode
{
  Btnode* lc_;
  Btnode* rc_;
  int value_;
  Btnode* p_;
 
  typedef Btnode NT;
   
  NT*& lc(void)
 {
  return lc_;
 }
 
  NT*& rc(void)
 {
  return rc_;
 }
 
  int& value(void)
 {
  return value_;
 }

  bool has_lc(void)
 {
    return lc() != 0;
 }
 
  bool has_rc(void)
 {
  return rc() != 0;
 }
 
  bool leafnode(void)
 {
  return !has_lc() && !has_rc();
 }
};

typedef Btnode NT;

void inorder(NT* root)
{
  if(root != 0)
  {
    inorder(root->lc());
    cout<<root->value_<<"  ";
    inorder(root->rc());
  }
}

void preorder(NT* root)
{
  if(root != 0)
  {
    cout<<root->value_<<"  ";
    preorder(root->lc());
    preorder(root->rc());
  }
}

void postorder(NT* root)
{
  if(root != 0)
  {
    postorder(root->lc());
    postorder(root->rc());
    cout<<root->value_<<"  ";
  }
}

void levelorder(NT* root)
{
  if(root == 0)
    return;
  std::queue<NT*> q;
  q.push(root);
  while(!q.empty())
  {
    NT* t = q.front();
    q.pop();
    if(t->has_lc())
      q.push(t->lc());
    if(t->has_rc())
      q.push(t->rc());
    cout<<t->value_<<"  ";
  } 
}

bool search(NT* tree, int x)
{
     while (tree != NULL)
     {
           if (tree->value_ == x)
           return true;
           if (x > tree->value_)
           return search(tree->rc_,x);
           else
           return search(tree->lc_,x);
     }
     return false;
}

int minimum(NT* tree)
{
    while (tree->lc_ != NULL)
    tree = tree->lc_;
    return tree->value_;
}

int maximum(NT* tree)
{
    while (tree->rc_ != NULL)
    tree = tree->rc_;
    return tree->value_;
}

void parent(NT* tree)
{
     if (tree->lc_ != NULL)
     tree->lc_->p_ = tree;
     if (tree->rc_ != NULL)
     tree->rc_->p_ = tree;
}

void set_parent(NT* root)
{
  if(root != 0)
  {
    set_parent(root->lc());
    parent(root);
    set_parent(root->rc());
  }
}

int successor(NT* x)
{
    if (x->rc_ != NULL)
    return minimum(x->rc_);
    NT* y = x->p_;
    while ((y != NULL) && (x == y->rc_))
    {
          x = y;
          y = y->p_;
    }
    return y->value_;
}      

void insert(NT* root,NT n)
{
     if ( root == NULL)
     root = &n;
     NT* temp;
     while (root != NULL)
     {
           temp = root;
           if (n.value_ < root->value_)
           root = root->lc_;
           else root = root->rc_;
     }
     if (n.value_ < temp->value_)
     temp->lc_ = &n;
     else temp->rc_ = &n;
}              

//NT dlt(NT* tree,NT n)
//{
//     NT x;
//     NT y;
//     if ((n.lc_ == NULL) || (n.rc_ == NULL))
//     y = n;
//     else y = successor(n);
//     if (y.lc_ != NULL)
//     x = y.lc_;
//     else x = y.rc_;
//     if (x != NULL)
//     x.p_ = y.p_;
//     if (y.p_ == NULL)
//     tree = &x;
//     else if (y == y.p_.lc_)
//     y.p_.lc_ = x;
//     else y.p_.rc_ = x;
//     if (y != n)
//     n.value_ = y.value_;
//     return y;       
//}

int main()
{
    NT a = {0,0,7};
    NT b = {0,&a,6};
    NT c = {&b,0,10};
    NT d = {0,0,3};
    NT e = {0,0,13};
    NT f = {&c,&e,12};
    NT g = {&d,&f,5};
    NT h = {0,0,18};
    NT i = {0,0,23};
    NT j = {&h,&i,20};
    NT k = {0,&j,16};
    NT l = {&g,&k,15};
    NT* root = &l;
    set_parent(root);
   
    cout << "inorder : ";
    inorder(root);
    cout << '\n' << '\n';
   
    cout << "preorder : ";
    preorder(root);
    cout << '\n' << '\n';
   
    cout << "postorder : ";
    postorder(root);
    cout << '\n' << '\n';
   
    cout << "levelorder : ";
    levelorder(root);
    cout << '\n' << '\n';
   
    cout << "search element 10 : ";
    cout << search(root,10) << '\n' << '\n';
   
    cout << "search element 100 : ";
    cout << search(root,100) << '\n' << '\n';
   
    cout << "The minimum value of the tree is : ";
    cout << minimum(root) << '\n' << '\n';
   
    cout << "The maximum value of the tree is : ";
    cout << maximum(root) << '\n' << '\n';
   
    cout << "The successor of the element 5 is : ";
    cout << successor(&g) << '\n' << '\n';
   
    cout << "The successor of the element 13 is : ";
    cout << successor(&e) << '\n' << '\n';
   
    cout << "After inserting 8 : ";
    NT node = {0,0,8};
    insert(root,node);
    inorder(root);
    cout << '\n'<< '\n';
   
    system("pause");
    return 0;
}