Cây Nhị Phân Số Nguyên - BinaryTree

Cây Nhị Phân Số Nguyên - BinaryTree

20:11
Cây Nhị Phân Số Nguyên
Cây nhị phân số nguyên có đầy đủ các chức năng cơ bản: nhập cây, duyệt cây, chèn một nút vào cây, xóa một nút khỏi cây, tìm kiếm nút

// Nguyen Cong Cuong - KTPM K14B
#include iostream
#include stdlib.h
using namespace std;

typedef struct Node{
 int Data;
 Node* Left;
 Node* Right;
};

typedef struct Node* BinaryTree;

// Khoi tao
void InIt(BinaryTree& T){
 T = NULL;
}

//kiem tra rong

bool IsEmpty(BinaryTree T){
 return (T == NULL);
}

// Tao Noode
Node* AddNode(Node* P,int x){
 P = (Node*)malloc(sizeof(Node));
 P->Data = x;
 P->Left = NULL;
 P->Right = NULL;
 return P;
}

//Them vao nut la
void AddTree(BinaryTree& T, int x){
 Node* P = AddNode(P,x);
 if (IsEmpty(T)) T = P;
 else {
  Node* M = T;
  Node* Q = NULL;
  while (M != NULL){
   Q = M;
   if (M->Data < x){
    M = M->Right;
   }
   else M = M->Left;
  }
  if (Q->Data < x) Q->Right = P;
  else Q->Left = P;
 }
}

void InPut(BinaryTree& T, int n){
 int x;
 for (int i = 0; i < n; i++){
  cout << "Value: " << i + 1 << endl;
  cin >> x;
  AddTree(T, x);
 }
}

void DuyetTruoc(BinaryTree T){ // duyet truoc
 Node* M = T;
 if (M != NULL){
  cout << M->Data << " ";
  DuyetTruoc(M->Left);
  DuyetTruoc(M->Right);
 }

}
void DuyetGiua(BinaryTree T){
 Node* M = T;
 if (M != NULL){

  DuyetGiua(M->Left);
  cout << M->Data << " ";
  DuyetGiua(M->Right);
 }
}
void DuyetSau(BinaryTree T){
 Node* M = T;
 if (M != NULL){
  DuyetSau(M->Left);
  DuyetSau(M->Right);
  cout << M->Data << " ";
 }
}
// tim kiem
Node* TimKiem(BinaryTree T, int x){
 if (IsEmpty(T)) return NULL;
 else {
  Node* M = T;
  if (M->Data > x) TimKiem(M->Left, x);
  else if (M->Data < x) TimKiem(M->Right, x);
  else return M;
 }
}
// Tim cha cua mot nut
Node* TimCha(BinaryTree T, int x){
 Node* M = T;
 if (IsEmpty(M)) return NULL;
 else {

  while (M != NULL){
   if (M->Data < x) {
    M = M->Right;
   }
   else{
    M = M->Left;
   }
   if (M->Left != NULL && M->Left->Data == x) return M;
   if (M->Right != NULL && M->Right->Data == x) return M;
  }
 }
}
// Xoa
void DeleteTree(BinaryTree& T, int x){
 Node* M = T;
 if (M != NULL){
  if (M->Left != NULL && M->Left->Data == x){
   // nut la
   if (M->Left->Left == NULL && M->Left->Right == NULL) M->Left = NULL;
   else {
    // nut co 1 con
    if (M->Left->Left != NULL && M->Left->Right == NULL) M->Right = M->Left->Left;
    if (M->Left->Left == NULL && M->Left->Right != NULL) M->Left = M->Left->Right;
   }
  }
  if (M->Right != NULL && M->Right->Data == x){
   if (M->Right->Left == NULL && M->Right->Right == NULL) M->Right = NULL;
   else {
    if (M->Right->Left != NULL && M->Right->Right == NULL) M->Right = M->Left->Left;
    if (M->Right->Left == NULL && M->Right->Right != NULL) M->Left = M->Left->Right;
   }
  }
  if (M->Data == x){
   // nut co 2 con
   if (M->Left != NULL && M->Right != NULL){
    if (M->Right->Right == NULL && M->Left->Left == NULL){
     M->Data = M->Right->Data;
     M->Right = NULL;
    }
    else{
     Node* Q = M->Right;
     while (Q->Left->Left != NULL){
      Q = Q->Left;
     }

     if (Q->Left != NULL){
      M->Data = Q->Left->Data;
      DeleteTree(M->Left, Q->Left->Data);
      DeleteTree(M->Right, Q->Left->Data);
     }
     else {
      M->Data = Q->Right->Data;
      DeleteTree(M->Left, Q->Right->Data);
      DeleteTree(M->Right, Q->Right->Data);
     }
    }
   }
  }
  DeleteTree(M->Left, x);
  DeleteTree(M->Right, x);
 }
}
// Chen
void InsertTree(BinaryTree& T, int x){
 Node* P = AddNode(P,x);
 if (IsEmpty(T)) {
  P->Left = NULL;
  P->Right = NULL;
  T = P;
 }
 else {
  if (T->Data > x) InsertTree(T->Left, x);
  else{
   if (T->Data < x) InsertTree(T->Right, x);
   else cout << "Da co roi." << endl;
  }
 }
}
// So nut trong cay
int Dem(BinaryTree T){
 if (IsEmpty(T)) return 0;
 else return 1 + Dem(T->Left) + Dem(T->Right);
}

int Max(int a, int b){
 if (a > b) return a;
 else return b;
}
// Chieu cao cua cay
int ChieuCao(BinaryTree T){
 if (IsEmpty(T)) return 0;
 else return Max(ChieuCao(T->Left), ChieuCao(T->Right)) + 1;
}
Node* ConTrai(BinaryTree T, int x){
 if (IsEmpty(T)) return NULL;
 else {
  Node* M = T;
  while (M != NULL){
   if (M->Data > x) M = M->Left;
   else if (M->Data < x) M = M->Right;
   else {
    if (M->Left != NULL) return  M->Left;
    else return NULL;
   }
  }
 }
}

Node* ConPhai(BinaryTree T, int x){
 if (IsEmpty(T)) return NULL;
 else {
  Node* M = T;
  while (M != NULL){
   if (M->Data > x) M = M->Left;
   else if (M->Data < x) M = M->Right;
   else {
    if (M->Right != NULL) return  M->Right;
    else return NULL;
   }
  }
 }
}

int SoNutLa(BinaryTree T){
 if (IsEmpty(T)) return 0;
 else {
  if (T->Left == NULL && T->Right == NULL) return 1;
  else return SoNutLa(T->Left) + SoNutLa(T->Right);
 }
}
int main(){
 BinaryTree T;
 InIt(T);
 int n, x;
 cout << "So luong: ";
 cin >> n;
 InPut(T, n);
 system("cls");
 int chon;
 do{
  system("cls");
  cout << "1. Chen." << endl;
  cout << "2. Xoa. " << endl;
  cout << "3. Tim kiem." << endl;
  cout << "4. Xuat." << endl;
  cout << "5. So nut" << endl;
  cout << "6. Tim cha." << endl;
  cout << "7. Chieu cao." << endl;
  cout << "8. Tim con. " << endl;
  cout << "9. So nut la. " << endl;
  cin >> chon;
  switch (chon)
  {
  case 1:{
       cout << "Nhap so can chen: ";
       cin >> x;
       InsertTree(T, x);
       system("pause");
       break;
  }
  case 2:{
       cout << "Nhap so can xoa: ";
       cin >> x;
       DeleteTree(T, x);
       system("pause");
       break;
  }
  case 3:{
       cout << "Nhap so can tim: ";
       cin >> x;
       if (TimKiem(T, x) != NULL) cout << x << " co trong cay" << endl;
       else cout << x << " khong co trong cay" << endl;
       system("pause");
       break;
  }
  case 4:{
       cout << "Duyet truoc: "; DuyetTruoc(T);
       cout << endl;
       cout << "Duyet giua: "; DuyetGiua(T);
       cout << endl;
       cout << "Duyet sau: "; DuyetSau(T);
       cout << endl;
       system("pause");
       break;
  }
  case 5:{
       int dem = 0;
       cout << Dem(T) << endl;
       system("pause");
       break;
  }
  case 6:{
       cout << "Tim cha cua: ";
       cin >> x;
       if (x != T->Data){
        if (TimCha(T, x) != NULL)
         cout << TimCha(T, x)->Data << endl;
        else cout << x << " khong co trong cay" << endl;
       }
       else cout << x << " khong co cha" << endl;
       system("pause");
       break;
  }
  case 7:{
       cout << ChieuCao(T) << endl;;
       system("pause");
       break;
  }
  case 8:{
       cout << "Nhap so: ";
       cin >> x;
       if (ConTrai(T, x) != NULL) cout << "Con trai: " << ConTrai(T, x)->Data << endl;
       if (ConPhai(T, x) != NULL) cout << "Con phai: " << ConPhai(T, x)->Data << endl;
       system("pause");
       break;
  }
  case 9:{
       cout << SoNutLa(T) << endl;
       system("pause");
       break;
  }
  }
 } while (chon != 0);
 return 0;
}

Share this :

Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.

Đăng ký: Đăng Nhận xét (Atom)