Archive | Chương 13 – Cây nhị phân RSS for this section
June 20, 2011  

[C] 896 Kiểm tra cây nhị phân T có phải là “cây nhị phân cân bằng hoàn toàn” hay không?

Tác giả:

  • Trần Hán Huy – tranhanhuy.wordpress.com

Sách:

  • Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang

Đề bài

  • 896 Kiểm tra cây nhị phân T có phải là “cây nhị phân cân bằng hoàn toàn” hay không?

Code

//896 Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng hoàn toàn" hay không?
//cây nhị phân cân bằng hoàn toàn là cây nhị phân tìm kiếm mà tại mỗi nút của nó 
//số nút của cây con trái và cây con phải chêch lệch ko quá 1
//0 là cây nhị phân tìm kiếm
//1 ko phải là cây nhị phân tìm kiếm
void TimMax(Tree c, int &Max)
{
    if (c==NULL)
        return ;
    if (c->pLeft != NULL)
        Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
    if (c->pRight != NULL)
        Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
    Max = (Max > c->iX) ? Max : c->iX;
    TimMax(c->pLeft,Max);
    TimMax(c->pRight,Max);
}
int DemNode(Tree c)
{
    if (c==NULL)
        return 0;
    int DemR = DemNode(c->pRight);
    int DemL = DemNode(c->pLeft);
    return DemR + DemL + 1;
}

int KiemTra(Tree c)
{
    if (c==NULL)
        return 0;
    int Left = KiemTra(c->pLeft);
    //kiểm tra điều kiện của cây nhị phân tìm kiếm
    int MaxL, MaxR;
    if (c->pLeft != NULL && c->pRight != NULL)
    {
        TimMax(c->pLeft, MaxL);
        TimMax(c->pRight, MaxR);
        if (!(MaxL < c->iX && c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft == NULL && c->pRight != NULL)
    {
        TimMax(c->pRight, MaxR);
        if (!(c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft != NULL && c->pRight == NULL)
    {
        TimMax(c->pLeft, MaxL);
        if (!(MaxL < c->iX))
            return 1;
    }
    //kiểm tra điều kiện của cây nhị phân tìm kiếm cân bằng hoàn toàn
    int NodeR = DemNode(c->pRight);
    int NodeL = DemNode(c->pLeft);
    printf ("ntnode: %d lech Right: %d, Left: %d", c->iX,NodeR,NodeL);
    if (abs(NodeR - NodeL) > 1)    //chêch lệch lớn hơn 1
        return 1;
    int Right = KiemTra(c->pRight);
    return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
    int Kt = KiemTra(c);
    if (Kt == 0)
        printf("nla cay nhi phan tim kiem can bang hoan toan");
    else
        printf("nko phai cay nhi phan tim kiem can bang hoan toan");
}

Link source:

June 20, 2011  

[C] 895 Kiểm tra cây nhị phân T có phải là “cây nhị phân cân bằng” hay không?

Tác giả:

  • Trần Hán Huy – tranhanhuy.wordpress.com

Sách:

  • Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang

Đề bài

  • 895 Kiểm tra cây nhị phân T có phải là “cây nhị phân cân bằng” hay không?

Code

//895 Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" hay không?
//Cây nhị phân cân bằng là cây nhị phân tìm kiếm mà tại mỗi nút của nó 
//độ cao của cây con trái và cây con phải chêch lệch ko quá 1
//0 là cây nhị phân tìm kiếm
//1 ko phải là cây nhị phân tìm kiếm
void TimMax(Tree c, int &Max)
{
    if (c==NULL)
        return ;
    if (c->pLeft != NULL)
        Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
    if (c->pRight != NULL)
        Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
    Max = (Max > c->iX) ? Max : c->iX;
    TimMax(c->pLeft,Max);
    TimMax(c->pRight,Max);
}
int DoCao(Tree c)
{
    if (c==NULL)
        return 0;
    int DoCaoR = DoCao(c->pRight);
    int DoCaoL = DoCao(c->pLeft);
    int max = (DoCaoR > DoCaoL) ? DoCaoR : DoCaoL;
    return max + 1;
}

int KiemTra(Tree c)
{
    if (c==NULL)
        return 0;
    int Left = KiemTra(c->pLeft);
    //kiểm tra điều kiện của cây nhị phân tìm kiếm
    int MaxL, MaxR;
    if (c->pLeft != NULL && c->pRight != NULL)
    {
        TimMax(c->pLeft, MaxL);
        TimMax(c->pRight, MaxR);
        if (!(MaxL < c->iX && c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft == NULL && c->pRight != NULL)
    {
        TimMax(c->pRight, MaxR);
        if (!(c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft != NULL && c->pRight == NULL)
    {
        TimMax(c->pLeft, MaxL);
        if (!(MaxL < c->iX))
            return 1;
    }
    //kiểm tra điều kiện của cây nhị phân tìm kiếm cân bằng
    int DoCaoR = DoCao(c->pRight);
    int DoCaoL = DoCao(c->pLeft);
    printf ("ntnode: %d lech Right: %d, Left: %d", c->iX,DoCaoR, DoCaoL);
    if (abs(DoCaoR - DoCaoL) > 1)    //chêch lệch lớn hơn 1
        return 1;
    int Right = KiemTra(c->pRight);
    return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
    int Kt = KiemTra(c);
    if (Kt == 0)
        printf("nla cay nhi phan tim kiem can bang");
    else
        printf("nko phai cay nhi phan tim kiem can bang");
}

Link source:

June 20, 2011  

[C] 894 Kiểm tra cây nhị phân T có phải là “cây nhị phân tìm kiếm” hay không?

Tác giả:

  • Trần Hán Huy – tranhanhuy.wordpress.com

Sách:

  • Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang

Đề bài

  • 894 Kiểm tra cây nhị phân T có phải là “cây nhị phân tìm kiếm” hay không?

Thuật giải 1: tìm max mỗi nhánh (left, right) để so sánh theo đúng qui tắc của cây nhị phân tìm kiếm

Thuật giải 2: Duyệt node theo thứ tự Left Node Right nếu cho ra kết qủa tăng dần thì là cây nhị phân tìmkiếm

Code

/*Nick yahoo: conloyal*/
/*Soft: visual studio 2008*/

//894 Kiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không?
//0 là cây nhị phân
//1 ko phải là cây nhị phân
void TimMax(Tree c, int &Max)
{
    if (c==NULL)
        return ;
    if (c->pLeft != NULL)
        Max = (Max > c->pLeft->iX)? Max : c->pLeft->iX;
    if (c->pRight != NULL)
        Max = (Max > c->pRight->iX)? Max : c->pRight->iX;
    Max = (Max > c->iX) ? Max : c->iX;
    TimMax(c->pLeft,Max);
    TimMax(c->pRight,Max);
}

int KiemTra(Tree c)
{
    if (c==NULL)
        return 0;
    int Left = KiemTra(c->pLeft);
    int MaxL, MaxR;
    if (c->pLeft != NULL && c->pRight != NULL)
    {
        TimMax(c->pLeft, MaxL);
        TimMax(c->pRight, MaxR);
        if (!(MaxL < c->iX && c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft == NULL && c->pRight != NULL)
    {
        TimMax(c->pRight, MaxR);
        if (!(c->iX < MaxR))
            return 1;
    }
    else if (c->pLeft != NULL && c->pRight == NULL)
    {
        TimMax(c->pLeft, MaxL);
        if (!(MaxL < c->iX))
            return 1;
    }
    int Right = KiemTra(c->pRight);
    return Left + Right;
}
void XuatKqKiemTra(Tree c)
{
    int Kt = KiemTra(c);
    if (Kt == 0)
        printf("nla cay nhi phan tim kiem");
    else
        printf("nko phai cay nhi phan tim kiem");
}

Link source:

June 20, 2011  

[C] 893 Tính chiều cao cây

Tác giả:

  • Trần Hán Huy – tranhanhuy.wordpress.com

Sách:

  • Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang

Đề bài

  • 893 Tính chiều cao cây

Code

/*Nick yahoo: conloyal*/
/*Soft: visual studio 2008*/

//893 Tính chiều cao cây
int ChieuCao(Tree c)
{
    if (c!=NULL)
    {
        int a = ChieuCao(c->pLeft);
        int b = ChieuCao(c->pRight);
        int max = (a>b)?a:b;
        return 1 + max;
    }
    return 0;
}

Link source:

June 20, 2011  

[C] 892 Tính tổng các nút có đúng 2 con mà thông tin tại nút đó là số chính phương

Tác giả:

  • Trần Hán Huy – tranhanhuy.wordpress.com

Sách:

  • Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang

Đề bài

  • 892 Tính tổng các nút có đúng 2 con mà thông tin tại nút đó là số chính phương

Code

/*Nick yahoo: conloyal*/
/*Soft: visual studio 2008*/

//892 Tính tổng các nút có đúng hai con mà thông tin nút đó là số chính phương
bool SoChinhPhuong(int n)
{
    int a = sqrt((double)n);
    if (a*a != n)
        return false;
    return true;
}
int Tinh(Tree c)
{
    if (c!=NULL)
    {
        int a = Tinh(c->pLeft);
        int b = Tinh(c->pRight);
        if (SoChinhPhuong(c->iX))
            if (c->pLeft != NULL && c->pRight != NULL)
                return c->iX + a + b;
        return a + b;
    }
    return 0;
}

Link source:

« Older Posts