Tổng hợp code cây nhị phân _Lập trình C++ căn bản

*)Giới thiệu:

- Cây nhị phân là một cấu trúc lưu trữ dữ liệu thông dụng trong thực tế. Nó giúp việc tìm kiếm, sắp xếp, lưu trữ,...dễ dàng và có tổ chức hơn. Sau đây là code tổng hợp các hàm thông dụng để thao tác trên cây nhị phân.

*)Đối tượng hướng đến:
- Các bạn đang học lập trình C/C++, dùng con trỏ thuần thục, đã làm quen với kiểu dữ liệu danh sách,list, queue,..
- Các đối tượng khác đọc tham khảo

*) Code mẫu tổng hợp:

#include<iostream>
#include<queue>
using namespace std;
struct Node
{
 int data;
 Node*Left;
 Node*Right;
 Node()
 {
  this->Left = NULL;
  this->Right = NULL;
 }
};

Node* createNode(int x)
{
 Node*P = new Node;
 P->data = x;
 return P;
}
struct Tree
{
 Node*Root;
 Tree()
 {
  cout << "Tree is declared\n";
   this->Root = NULL;
 }
 void add(Node*&R, int x);
 void deleteTree(Node*&Root);
 void romoveNode(Node*&R, int x);   //xoa mot node co gia tri x
 int countLeaf(Node*&R);      //dem so la
 int countHeight(Node*&R);    //tinh chieu cao
 int countNode(Node*&R);      //dem node
 void breathFirsttraversal();  //xuat cay theo tung bac
 Node*& search(Node*&R, int x);
};
void Tree::deleteTree(Node*&Root)
{
 if (Root)
 {
  deleteTree(Root->Left);
  deleteTree(Root->Right);
  delete Root;
 }
}
void Tree::add(Node*&R, int x)
{
 if (!R)
 {
  R = new Node;
  R->data = x;
 }
 else
 {
  if (R->data == x)
  {
   return;   //khong tiep tuc them nua
  }
  else
  {
   if (R->data < x)
   {
    add(R->Right, x);
   }
   else
   {
    add(R->Left, x);
   }
  }
 }
}
void Tree::romoveNode(Node*&R, int x)
{
 if (!R)
 {
  return;  //khong tim thay node can xoa
 }
 if (R->data > x)
 {
  romoveNode(R->Left, x);
 }
 else
 {
  if (R->data < x)
  {
   romoveNode(R->Right, x);
  }
  else
  {
   if (!R->Left)
   {
    R = R->Right;
   }
   else
   {
    if (!R->Right)
    {
     R = R->Left;
    }
    else
    {
     Node*P = R;
     Node*Q = R->Left;
     while (Q->Right)
     {
      P = Q;
      Q = Q->Right;
     }
     if (P != R)
     {
      P->Right = Q->Left;
     }
     else
     {
      P->Left = Q->Left;
     }
     R->data = Q->data;
     delete Q;
    }
   }
  }
 }
}
int Tree::countLeaf(Node*&R)
{
 if (!R)
 {
  return 0;
 }
 if (!R->Left&&!R->Right)
 {
  return 1;
 }
 return(countLeaf(R->Left) + countLeaf(R->Right));
}
int Tree::countHeight(Node*&R)
{
 if (!R)
 {
  return 0;    //tuy vao qui uoc lap trinh vien, mot so nguoi return -1
 }
 int left = countHeight(R->Left);
 int right = countHeight(R->Right);
 return (left > right ? left : right) + 1;
}
int Tree::countNode(Node*&R)
{
 if (!R) return 0;
 return (1 + countNode(R->Left) + countNode(R->Right));
}
void Tree::breathFirsttraversal()
{
 queue<Node*> nodes;
 nodes.push(this->Root);
 int number_of_currently_Parent = 1;       //s? node cha hi?n t?i đang trong hàng đ?i
 int number_of_following_Node = 0;       //s? con theo sau
 while (!nodes.empty())
 {
  if (number_of_currently_Parent != 0)
  {
   if (nodes.front()->Left)             //n?u bên trái node hi?n t?i khác null th? thêm nút bên trái đó vào hàng đ?i
   {
    nodes.push(nodes.front()->Left);
    number_of_following_Node++;
   }
   if (nodes.front()->Right)           //tương t? bên trên
   {
    nodes.push(nodes.front()->Right);
    number_of_following_Node++;
   }
   cout << nodes.front()->data << " ";
   nodes.pop();
   number_of_currently_Parent--;
  }
  else
  {
   cout << "\n";
   number_of_currently_Parent = number_of_following_Node;
   number_of_following_Node = 0;
  }
 }
}
Node*& Tree::search(Node*&R, int x)
{
 if (!R) return R;  //return ve null
 if (R->data > x)
 {
  return search(R->Left, x);
 }
 else
 {
  if (R->data < x)
  {
   return search(R->Right, x);
  }
  else
  {
   return R;
  }
 }
}
//main function
int main()
{
 Tree T;
 cout << "add node to Tree, enter 0 to finish\n";
 for (int i = 9; i != 0;)
 {
  cin >> i;
  if (i)   //n?u i khác 0 th? thêm vào cây T
  {
   T.add(T.Root, i);
  }
  cout << "continue adding\n";
 }
 //muốn dùng hàm gì thì thêm vào đây 
 return 0;
}