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 tổng quát - Chiều cao của cây

    Share

    admin
    Admin
    Admin

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

    Cây tổng quát - Chiều cao của cây

    Bài gửi  admin on Mon Apr 19, 2010 10:34 am

    XÁC ĐỊNH CHIỀU CAO CỦA CÂY TỔNG QUÁT


    Chiều cao của cây là chiều cao của nút gốc tới nút lá với chiều cao là cao nhất.
    Ý tưởng:
      - Xác định độ sâu của 1 nút bất kỳ.
      - Tính độ sâu của tất cả các nút trên cây, tìm ra độ sâu lớn nhất đó chính là chiều cao của cây.


    Xét cấu trúc dữ liệu của cây tổng quát.
    Code:
    #define MAXLENGTH 100   //chi so toi da cua mang
    #define NIL -1
    typedef char DataType;
    typedef int Node;
    typedef struct {
       DataType Data[MAXLENGTH];   //Luu gia tri cua nut
       Node Parent[MAXLENGTH];      //Cha cua nut i se luu o vi tri i trong mang
       int MaxNode;
    }Tree;

    Hàm tính độ sâu của một nút.
    Code:
    //Do sau cua node p
    int DepthNode(Node p, Tree T) {
       if(p>=0|| p<T.MaxNode) {
          int temp = 0;
          while(p!=Root(T)) {
             p = T.Parent[p];
             temp++;
          }
          return temp;
       }
       else
          return NIL;
    }

    Hàm tính chiều cao của cây.
    Code:
    int HeightTree(Tree T) {
       int Max = NIL;
       for(int i = T.MaxNode-1; i>=0; i--)
          if(Max < DepthNode(i,T))
             Max = DepthNode(i,T);
       return Max;
    }

    Chương trình minh họa.
    Code:
    /* Chuong trinh cai dat cay tong quat bang mang - tinh chieu cao cua cay*/
    #include "conio.h"
    #include "stdio.h"

    #define MAXLENGTH 100   //chi so toi da cua mang
    #define NIL -1
    typedef char DataType;
    typedef int Node;
    typedef struct {
       DataType Data[MAXLENGTH];   //Luu gia tri cua nut
       Node Parent[MAXLENGTH];      //Cha cua nut i se luu o vi tri i trong mang
       int MaxNode;
    }Tree;

    //Khoi tao cay rong
    void MakeNull_Tree (Tree *T)
    {
       (*T).MaxNode=0;
    }
    //Kiem tra cay rong
    int EmptyTree(Tree T)
    {
       return T.MaxNode == 0;
    }
    //Xac dinh nut cha cua nut tren cay
    Node Parent(Node n,Tree T)
    {
       if (EmptyTree(T) || (n>T.MaxNode-1))
          return NIL;
       else
          return T.Parent[n];
    }
    //Xac dinh gia tri cua nut tren cay
    DataType Label_Node(Node n,Tree T)
    {
       if (!EmptyTree(T) && (n<=T.MaxNode-1))
          return T.Data[n];
       else
          return 13;  //ky ty Enter
    }
    //Xac dinh nut goc trong cay
    Node Root(Tree T)
    {
       if (!EmptyTree(T))
          return 0;
       else
          return NIL;
    }
    //Do sau cu nut p
    int DepthNode(Node p, Tree T) {
       if(p>=0|| p<T.MaxNode) {
          int temp = 0;
          while(p!=Root(T)) {
             p = T.Parent[p];
             temp++;
          }
          return temp;
       }
       else
          return NIL;
    }
    //Chieu cao cua cay
    int HeightTree(Tree T) {
       int Max = NIL;
       for(int i = T.MaxNode-1; i>=0; i--)
          if(Max < DepthNode(i,T))
             Max = DepthNode(i,T);
       return Max;
    }
    //Doc cay
    void ReadTree(Tree *T){
       int i;
       MakeNull_Tree(&*T);
       do {
          printf("Cay co bao nhieu nut? ");
          scanf("%d",&(*T).MaxNode);
       } while (((*T).MaxNode<1) || ((*T).MaxNode>MAXLENGTH));
       printf("Nhap nhan cua nut goc: ");
       fflush(stdin);
       scanf("%c",&(*T).Data[0]);
       (*T).Parent[0]=NIL; /* nut goc khong co cha */
       for (i=1;i<=(*T).MaxNode-1;i++){
          printf("Nhap cha cua nut %d: ",i);
          scanf("%d",&(*T).Parent[i]);
          printf("Nhap nhan cua nut %d: ",i);
          fflush(stdin);
          scanf("%c",&(*T).Data[i]);
       }
    }
    //Chuong trinh chinh
    void main(){
       clrscr();
       Tree T;   
       printf("Nhap du lieu cho cay tong quat\n");
       ReadTree(&T);
       if(HeightTree(T)!=NIL)
          printf("Chieu cao cua cay la: %d", HeightTree(T));
       else
          printf("Cay rong!!!");
       getch();
    }

      Hôm nay: Sat Apr 19, 2014 1:10 am