Bài 10-Cài đặt cây nhị phân tìm kiếm

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <conio.h>

#include <alloc.h>

typedef struct NODE{

             int info;

             NODE *left;

             NODE *right;

};

void MakeNull(NODE **T);

NODE *Makenode(int x);

void NhapMoi( NODE **T);

void PreOrder(NODE **T)

void Insert(NODE **T,int x);

/* CHUONG TRINH CHINH */

void main()

{  char chucnang;  NODE *T;  int x;

   MakeNull(&T);

   do

   {  clrscr();

      printf("\n\n\t\tCHUONG TRINH MINH HOA CAY NHI PHAN TIM KIEM\n");

      printf("   1: Tao cay moi\n");

      printf("   2: Duyet cay theo PreOrder\n");

      printf("   3: Them mot nut vao cay\n");

      printf("   4: Tim kiem mot nut\n");

      printf("   ESC: Ket thuc chuong trinh\n");

      printf("Chuc nang ban chon: ");

      chucnang =getch();

      switch(chucnang)

      {

                case '1':NhapMoi(&T);              break;

                case '2':printf("\n\nDuyet cay theo thu tu truoc\n\n");

                           PreOrder(&T); getch(); break;

                case '3':printf("\nThem mot nut\n");

                           printf("\nNhap gia tri:"); scanf("%d",&x);

                           Insert(&T,x);

                           PreOrder(&T); getch(); break;

 

      }

   } while(chucnang!=27);

}

void MakeNull(NODE **T)

{

   (*T) = NULL;

   (*T)->left = NULL;

   (*T)->right= NULL;

}

// Tao mot nut co noi dung la x;

NODE *Makenode(int x)

{

   NODE *p;

   p = new NODE;

   p->info = x;

   p->left = NULL;

   p->right= NULL;

   return (p);

}

void NhapMoi( NODE **T)

{ int x;

  NODE *p,*q; int ch;

  printf("\nNhap mot cay moi:");

  do {

      printf("\nNhap mot nut :");

      scanf("%d",&x);

      q=Makenode(x); // tao nut moi q

      if ( *T==NULL) (*T) = q;

      else{

              p=*T;

              while (p!=NULL)

              {

                 if(x < p->info)

                       if(p->left!=NULL)   p=p->left;// da co con trai

                       else// khong co con trai

                        {

                          p->left=q;    // bo xung con trai la q

                          p=NULL;

                        }      // khi da chen xong gan p=NULL( nut nay se la la}

                 else

                       if(x >p->info)

                         if(p->right!=NULL)  p=p->right;  // da co con phai

                         else // chua co con phai

                              {

                                 p->right=q;    // q se la con phai

                                 p=NULL;

                              }

                       else {  printf("\n\nDA CO NUT %d",x," ROI ");

                                 p=NULL;

                              }

               }

       }

      printf("\nBan co tiep tuc nua khong(Y/N)?:");

      ch = getch();

      ch =toupper(ch);

      }while( ch !='N');

}

 

void PreOrder(NODE **T)

{

  if (*T!=NULL)

    {

      printf("%3d",(*T)->info);

      PreOrder( &(*T)->left);  // duyet con trai

      PreOrder( &(*T)->right); // duyet con phai

    }

}

void Insert(NODE **T,int x)

{   NODE *q;

    if ( (*T)==NULL){

          q = Makenode(x);

          (*T) = q;

          }

    else

          if( x < (*T)->info) Insert( &(*T)->left,x);

          else                          Insert( &(*T)->right,x);

}

Bình luận

Bài viết khác

Bài 16- Thuật toán Ford -Fulkerson

Thuật toán Ford - Fulkerson  Việc chứng minh định lý luồng cực đại - lát cắt cực tiểu cho ta một thuật toán tìm luồng cực đại (thuật toán Ford- Fulkerson)

Bài 15-Cài đặt thuật toán Dijkstra

Năm 1959, Edsger W. Dijkstra đưa ra một thuật toán rất hiệu quả để giải bài toán đường đi ngắn nhất. Thuật toán thực hiện việc gán và giảm giá trị của nhãn tại mỗi đỉnh của đồ thị.

Bài 14-Thuật toán Prim

Thuật toán Prim do Robert Prim đưa ra vào năm 1957, ý tưởng chính của nó là lần lượt ghép vào cây khung các cạnh có trọng số tối thiểu liên thuộc với một đỉnh của cây mà không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi có được n - 1 cạnh vào cây. Dưới đây là mô tả các bước của thuật toán Prim.

Bài 13-Cài đặt thuật toán Kruskal tìm cây khung tối thiểu

File dữ liệu về đồ thị dạng text;

ĐỐI TÁC CỦA CHÚNG TÔI