Cài đặt cây nhị phân tổng quát

Cài đặt cây nhị phân sau, sau đó duyệt theo thứ tự trước, thứ tự sau và thứ tự giữa: Image Hosted by ImageShack.us Code: .cpp

#include <iostream>
#include <stdio.h>
#include <conio.h>

typedef struct Tree
{
            char data;
            Tree * LeftChild, * RightChild;
};

Tree * root;

void AddChildNode(Tree * root, Tree * LeftChild, Tree * RightChild)
{
     root->LeftChild = LeftChild;
     root->RightChild = RightChild;
}

int IsChild(Tree * p, Tree * q) // Kiem tra xem q co phai la hau due cua p hay khong
{
       if (p == NULL) return 0;
          else if (p == q) return 1;
               else return IsChild(p->LeftChild, q) || IsChild(p->RightChild, q);
}

int SizeOfNode(Tree * p) // Find the size of node p
{
       if (p == NULL) return 0;
          else return SizeOfNode(p->LeftChild) + SizeOfNode(p->RightChild) + 1;
}

void CreatTree()
{
    root = new Tree[14]; // Chi su dung cac phan tu tu 1 toi 13

    // Khoi tao cay
    // Khoi tao gia tri
    int i;
    for (i=1; i<= 13; i++) root[i].data = char(65+i-1);
    // Tao cac moi noi
    AddChildNode(&root[1], &root[2], &root[3]);
    AddChildNode(&root[2], &root[4], &root[5]);
    AddChildNode(&root[4], NULL, NULL);
    AddChildNode(&root[5], &root[8], NULL);
    AddChildNode(&root[8], &root[12], &root[13]);
    AddChildNode(&root[12], NULL, NULL);
    AddChildNode(&root[13], NULL, NULL);
    AddChildNode(&root[3], &root[6], &root[7]);
    AddChildNode(&root[6], &root[9], &root[10]);
    AddChildNode(&root[9], NULL, NULL);
    AddChildNode(&root[10], NULL, NULL);
    AddChildNode(&root[7], NULL, &root[11]);
    AddChildNode(&root[11], NULL, NULL);
}

void PreOrder(Tree * r)
{
     if (r == NULL) return;
     printf("%c", r->data);
     PreOrder(r->LeftChild);
     PreOrder(r->RightChild);
}

void InOrder(Tree * r)
{
     if (r == NULL) return;
     InOrder(r->LeftChild);
     printf("%c", r->data);
     InOrder(r->RightChild);
}

void PostOrder(Tree * r)
{
     if (r == NULL) return;
     PostOrder(r->LeftChild);
     PostOrder(r->RightChild);
     printf("%c", r->data);
}

int main()
{
    CreatTree();
    printf("Size of the node 5 is %d\n", SizeOfNode(&root[5]));
    printf("Size of the node 3 is %d\n\n", SizeOfNode(&root[3]));

    if (IsChild(&root[3], &root[10])) printf("The node 3 is the father of the node 10\n");
       else printf("The node 3 is not the father of the node 10\n");

    if (IsChild(&root[2], &root[9])) printf("The node 2 is the father of the node 9");
       else printf("The node 2 is not the father of the node 9");

    printf("\n\nPreOrder:\n");
    PreOrder(&root[1]);

    printf("\n\nInOrder:\n");
    InOrder(&root[1]);

    printf("\n\nPostOrder:\n");
    PostOrder(&root[1]);

    getch();
}

One Response to “Cài đặt cây nhị phân tổng quát”

  1. tosonnguyen Says:

    Vì cây nhị phân dạng tổng quát có thể có hình dạng bất kì (khác với cây nhị phân hoàn chỉnh hoặc cây nhị phân đầy đủ – có hình dạng cố định) nên việc xây dựng cây bắt buộc phải làm giống như hàm CreateTree ở trên.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: