Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Cây nhị phân - Cài đặt bằng mảng

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Cây nhị phân - Cài đặt bằng mảng

Bài gửi  admin on Mon Apr 19, 2010 7:11 pm

CÀI ĐẶT CÂY NHỊ PHÂN BẰNG MẢNG


Tại nút thứ i:
    - Con trái là nút 2*(i+1)-1
    - Con phải 2*(i+1)


Chương trình minh họa cây nhị phân cài đặt bằng mảng.
Code:
#include <stdio.h>
#include <conio.h>
#define max 100
#define MAXLENGTH 100         //chi so toi da cua mang
#define NIL -1
typedef int DataType;
typedef int Node;
typedef struct {
   DataType Data[MAXLENGTH];   //Luu gia tri cua nut
   int MaxNode;
}Tree;
//Kiem tra cay rong
int EmptyTree(Tree T) {
   return T.MaxNode == 0;
}
//Xac dinh nut goc trong cay
Node Root(Tree T) {
   if (!EmptyTree(T))
      return 0;
   else
      return NIL;
}
//con trai cua nut p
int Left_Child(Node p, Tree T) {
      return 2*(p+1) - 1;
}
//con phai cua nut p
int Right_Child(Node p, Tree T) {
      return 2*(p+1);
}
//duyet tien tu
void NLR(Node p, Tree T) {
   if(T.Data[p]!=NIL) {
      printf("%d  ", T.Data[p]);
      NLR(Left_Child(p,T),T);
      NLR(Right_Child(p,T),T);
   }
}
//duyet trung tu
void LNR(Node p, Tree T) {
   if(T.Data[p]!=NIL) {
      LNR(Left_Child(p,T),T);
      printf("%d  ", T.Data[p]);
      LNR(Right_Child(p,T),T);
   }
}
//duyet hau tu
void LRN(Node p, Tree T) {
   if(T.Data[p]!=NIL) {
      LRN(Left_Child(p,T),T);
      LRN(Right_Child(p,T),T);
      printf("%d  ", T.Data[p]);
   }
}
/*doc cay
neu khong co con trai hoac phai thi nhap -1*/
void Read_Tree(Tree * T) {
   int i = 0, Child = 0;
   printf("Nhap vao so nut: ");
   scanf("%d",&(*T).MaxNode);
   while(i<(*T).MaxNode) {
      if(i==0)
      {
         printf("Nut goc:");
         scanf("%d",&(*T).Data[i]);
         (*T).Data[Left_Child(i,*T)] = NIL;
         (*T).Data[Right_Child(i,*T)] = NIL;
         i++;
      }
      else
      if((*T).Data[Child]!=NIL)
      {   int k;
         printf("Con trai %d: ",Child);
         k = Left_Child(Child,*T);
         scanf("%d",&(*T).Data[k]);
         if((*T).Data[k] != NIL) {
            (*T).Data[Left_Child(k,*T)] = NIL;
            (*T).Data[Right_Child(k,*T)] = NIL;
            i++;
         }
         printf("Con phai %d: ",Child);
         k = Right_Child(Child,*T);
         scanf("%d",&(*T).Data[k]);
         if((*T).Data[k] != NIL) {
            (*T).Data[Left_Child(k,*T)] = NIL;
            (*T).Data[Right_Child(k,*T)] = NIL;
            i++;
         }
         Child++;
      }
   }
}
void main() {
   Tree T;
   clrscr();
   Read_Tree(&T);
   printf("Duyet tien tu.\n");
   NLR(Root(T),T);
   printf("\nDuyet trung tu.\n");
   LNR(Root(T),T);
   printf("\nDuyet hau tu.\n");
   LRN(Root(T),T);
   getch();
}

    Hôm nay: Sat Dec 03, 2016 11:39 am