[Cây] Cây nhị phân sinh viên – Student Binary Tree

Tháng Mười Hai 4, 2014 nguyenvanquan7826 TT Cây Leave a response
Code dưới đây được phát triển từ code tại Một số phép toán trên cây nhị phân tìm kiếm để giải quyết bài toán Xây dựng cây nhị phân tìm kiếm sinh viên (key là mã sinh viên). Mỗi sinh viên có mã sinh viên, họ tên, điểm. Duyệt danh sách sinh viên, thêm sinh viên, xóa sinh viên có điểm nhỏ hơn 4
Code below is extends from Một số phép toán trên cây nhị phân tìm kiếm to create Student Binary Tree (key is id of student). A Student has id, name and scores. Traverse the tree, add a student and remove all student have scores smaller 4
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct item {
	char id[20];
	char name[20];
	double scores;
};
struct Node {
	item key; //truong key cua du lieu
	Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay

int compare(item x, item y) { // so sanh 2 item theo key
	return strcmp(x.id, y.id);
}

item inputItem() {	// nhap 1 item
	item x;
	char id[20];
	printf("Enter id of student (q to quit): ");
	gets(x.id);

	if (strcmp(x.id, "q") == 0 || strcmp(x.id, "Q") == 0) {
		return x;
	}

	printf("Enter name of student: ");
	gets(x.name);

	printf("Enter scores of student:");
	scanf("%lf", &x.scores);

	//fflush(stdin);
	while (getchar() != '\n');

	return x;
}

void outItem(item x) {
	printf("%-20s %-20s %-3.2f \n", x.id, x.name, x.scores);
}

int insertNode(Tree &T, item x) // chen 1 Node vao cay
		{
	if (T != NULL) {
		if (compare(T->key, x) == 0)
			return -1;  // Node nay da co
		if (compare(T->key, x) > 0)
			return insertNode(T->Left, x); // chen vao Node trai
		else if (compare(T->key, x) < 0)
			return insertNode(T->Right, x);   // chen vao Node phai
	}
	T = (Node *) malloc(sizeof(Node));
	if (T == NULL)
		return 0;    // khong du bo nho
	T->key = x;
	T->Left = T->Right = NULL;
	return 1;   // ok
}

void CreateTree(Tree &T)        // nhap cay
		{
	item x;
	while (1) {
		printf("Enter a student: ");
		x = inputItem();
		if (strcmp(x.id, "q") == 0 || strcmp(x.id, "Q") == 0)
			break;  // x = 0 thi thoat
		int check = insertNode(T, x);
		if (check == -1)
			printf("Student is exits!");
		else if (check == 0)
			printf("Memory full");

	}
}

// Duyet theo LNR
void LNR(Tree T) {
	if (T != NULL) {
		LNR(T->Left);
		outItem(T->key);
		LNR(T->Right);
	}
}

Node* searchScores(Tree T, int scores)     // tim nut co diem < 4
		{
	if (T != NULL) {
		if (T->key.scores < scores) {
			Node *P = T;
			return P;
		}
		if (T->key.scores >= scores) {
			Node *node = searchScores(T->Left, scores);
			if (node != NULL)
				return node;
			else {
				return searchScores(T->Right, scores);
			}
		}
	}
	return NULL;
}

int delKey(Tree &T, item x)     // xoa nut co key x
		{
	if (T == NULL)
		return 0;
	else if (compare(T->key, x) > 0)
		return delKey(T->Left, x);
	else if (compare(T->key, x) < 0)
		return delKey(T->Right, x);
	else // T->key == x
	{
		Node *P = T;
		if (T->Left == NULL)
			T = T->Right;    // Node chi co cay con phai
		else if (T->Right == NULL)
			T = T->Left;   // Node chi co cay con trai
		else // Node co ca 2 con
		{
			Node *S = T, *Q = S->Left;
			// S la cha cua Q, Q la Node phai nhat cua cay con trai cua P
			while (Q->Right != NULL) {
				S = Q;
				Q = Q->Right;
			}
			P->key = Q->key;
			S->Right = Q->Left;
			delete Q;
		}
	}
	return 1;
}

int main() {
	Tree T;
	T = NULL; //Tao cay rong

	CreateTree(T); //Nhap cay
	//duyet cay
	printf("LNR: \n");
	LNR(T);
	printf("\n");

	// them sinh vien
	item x;
	printf("Enter id of student to add: ");
	x = inputItem();
	if (insertNode(T, x) == -1) {
		printf("add failt!");
	} else {
		printf("add success:\n");
		printf("LNR after add item: \n");
		LNR(T);
		printf("\n");
	}

	// xoa sinh vien co diem nho hon 4
	int del = 1;
	while (del) {
		Node* node = searchScores(T, 4);
		if (node != NULL) {
			printf("del");
			del = delKey(T, node->key);
		} else {
			printf("null");
			del = 0;
		}
	}
	printf("LNR after delete item: \n");
	LNR(T);
	printf("\n");
	return 0;
}