Cây nhị phân (BRNARY TREES)

Định nghĩa

Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. Ví dụ các cây trong hình III.12.

Hình III.12: Hai cây có thứ tự giống nhau nhưng là hai cây nhị phân khác nhau

Chú ý rằng, trong cây nhị phân, một nút con chỉ có thể là nút con trái hoặc nút con phải, nên có những cây có thứ tự giống nhau nhưng là hai cây nhị phân khác nhau. Ví dụ hình III.12 cho thấy hai cây có thứ tự giống nhau nhưng là hai cây nhị phân khác nhau. Nút 2 là nút con trái của cây a/ nhưng nó là con phải trong cây b/. Tương tự nút 5 là con phải trong cây a/ nhưng nó là con trái trong cây b/.

Duyệt cây nhị phân

Ta có thể áp dụng các phép duyệt cây tổng quát để duyệt cây nhị phân. Tuy nhiên vì cây nhị phân là cấu trúc cây đặc biệt nên các phép duyệt cây nhị phân cũng đơn giản hơn. Có ba cách duyệt cây nhị phân thường dùng (xem kết hợp với hình III.13):

• Duyệt tiền tự (Node-Left-Right): duyệt nút gốc, duyệt tiền tự con trái rồi duyệt tiền tự con phải.

• Duyệt trung tự (Left-Node-Right): duyệt trung tự con trái rồi đến nút gốc sau đó là duyệt trung tự con phải.

Hình III.13

• Duyệt hậu tự (Left-Right-Node): duyệt hậu tự con trái rồi duyệt hậu tự con phải sau đó là nút gốc.

Chú ý rằng danh sách duyệt tiền tự, hậu tự của cây nhị phân trùng với danh sách duyệt tiền tự, hậu tự của cây đó khi ta áp dụng phép duyệt cây tổng quát. Nhưng danh sách duyệt trung tự thì khác nhau.

Ví dụ

Hình III.14

Cài đặt cây nhị phân

Tương tự cây tổng quát, ta cũng có thể cài đặt cây nhị phân bằng con trỏ bằng cách thiết kế mỗi nút có hai con trỏ, một con trỏ trỏ nút con trái, một con trỏ trỏ nút con phải, trường Data sẽ chứa nhãn của nút.

typedef … TData;

typedef struct TNode{TData Data;

TNode* left,right;

};

typedef TNode* TTree;

Với cách khai báo như trên ta có thể thiết kế các phép toán cơ bản trên cây nhị phân như sau :

Tạo cây rỗng

Cây rỗng là một cây là không chứa một nút nào cả. Như vậy khi tạo cây rỗng ta chỉ cần cho cây trỏ tới giá trị NULL.

void MakeNullTree(TTree *T){

(*T)=NULL;

}

Kiểm tra cây rỗng

int EmptyTree(TTree T){

return T==NULL;

}

Xác định con trái của một nút

TTree LeftChild(TTree n){

if (n!=NULL) return n->left;

else return NULL;

}

Xác định con phải của một nút

TTree RightChild(TTree n){

if (n!=NULL) return n->right;

else return NULL;

}

Kiểm tra nút lá:

Nếu nút là nút lá thì nó không có bất kỳ một con nào cả nên khi đó con trái và con phải của nó cùng bằng nil

int IsLeaf(TTree n){

if(n!=NULL)

return(LeftChild(n)==NULL)&&(RightChild(n)==NULL);

else return NULL;

}

Xác định số nút của cây

int nb_nodes(TTree T){

if(EmptyTree(T)) return 0;

else return 1+nb_nodes(LeftChild(T))+

nb_nodes(RightChild(T));

}

Tạo cây mới từ hai cây có sẵn

TTree Create2(Tdata v,TTree l,TTree r){

TTree N;

N=(TNode*)malloc(sizeof(TNode));

N->Data=v;

N->left=l;

N->right=r;

return N;

}

Các thủ tục duyệt cây: tiền tự, trung tự, hậu tự

Thủ tục duyệt tiền tự

void PreOrder(TTree T){

printf("%c ",T->Data);

if (LeftChild(T)!=NULL) PreOrder(LeftChild(T));

if (RightChild(T)!=NULL)PreOrder(RightChild(T));

}

Thủ tục duyệt trung tự

void InOrder(TTree T){

if (LeftChild(T)=!NULL)InOrder(LeftChild(T));

printf("%c ",T->data);

if (RightChild(T)!=NULL) InOrder(RightChild(T));

}

Thủ tục duyệt hậu tự

void PosOrder(TTree T){

if (LeftChild(T)!=NULL) PosOrder(LeftChild(T));

if (RightChild(T)!=NULL)PosOrder(RightChild(T));

printf("%c ",T->data);

}