Một số Cấu trúc dữ liệu và giải thuật cơ bản | Đại học Bách Khoa Hà Nội

Một số Cấu trúc dữ liệu và giải thuật cơ bản | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!

26 13 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

19 trang 6 tháng trước

Tác giả:

Profile Thùy Dương
1
Mục l c ụ
1 T h p ổ ợ ........................................................................ 3
2 Tháp Hà N i 3 ộ ...............................................................
3 Quay lui hoán v ị ......................................................... 3
4 n th Hiể ị ngoặc đúng................................................... 3
5 X p h u ế ậ ...................................................................... 4
6 Danh sách móc nối đơn ............................................. 4
6.1 Xóa ph n t i ầ ử cuố ................................................ 5
6.2 Xóa ph n t u 5 ầ ử đầ ................................................
6.3 Chèn vào gi a ữ .................................................... 5
6.4 Chèn vào cu i ố ..................................................... 5
6.5 u Chèn vào đầ ..................................................... 5
6.6 n th danh sách Hiể ị ............................................. 6
6.7 T o m i m t nút ạ ớ ộ ................................................ 6
6.8 o chi u danh sách Đả ề .......................................... 6
6.9 n thành 1 ds gi m d n Trộn 2 ds sx tăng dầ ả ầ ....... 6
6.10 n 2 ds sx giTrộ ảm d n thành 1 ds giầ ảm d n ầ ....... 7
7 Danh sách dùng m ảng................................................ 7
7.1 T o m i m t nút ạ ớ ộ ................................................ 7
7.2 Thêm nút m i 8 ớ ....................................................
7.3 Xóa nút ............................................................... 8
7.4 Locate ................................................................. 8
7.5 n th Hiể ị ds .......................................................... 8
8 Stack ds móc n– ối đơn .............................................. 8
8.1 T o m i m t stack ạ ớ ộ ............................................. 8
8.2 Ds r ng tr vỗ ả ề true ............................................. 9
8.3 Push 9 ...................................................................
8.4 Pop..................................................................... 9
8.5 L y ra các ph n t trong stack ấ ầ ử ........................... 9
9 Stack m – ảng.............................................................. 9
9.1 T o m i m t stack ạ ớ ộ ............................................. 9
9.2 N u stack r ng tr v true ế ỗ ả ề ................................. 9
9.3 Push 9 ...................................................................
9.4 Pop..................................................................... 9
9.5 L y ra các ph n t trong stack ấ ầ ử ........................... 9
10 Queue ds móc n– ối đôi ......................................... 9
10.1 T o m i m t queue ạ ớ ộ ......................................... 10
10.2 N u queue rế ỗng tr vả ề true ............................. 10
10.3 Thêm m t phộ ầ ửn t vào queue ......................... 10
10.4 L y ra m t phấ ộ ần t c a queue ử ủ ......................... 10
10.5 L y h t các ph n t trong queue ấ ế ầ ử ..................... 10
11 Cây ....................................................................... 10
11.1 T o m i m t nút ạ ớ ộ .............................................. 10
11.2 Duy t cây theo th t c ệ ứ ự trướ ...........................11
11.3 Duy t cây theo th t sau ệ ứ ự ............................... 11
11.4 Duy t cây theo th t a ệ ứ ự giữ .............................11
11.5 m s nút cây Đế ố ................................................ 11
11.6 Chi u sâu cây ề ................................................... 11
11.7 Cây nhị phân đầy đủ ........................................ 12
11.7.1 T o cây nhạ ị phân đầy đủ .......................... 12
11.7.2 m tra cây nh Kiể ị phân đầy đủ.................. 12
11.8 Cây nh phân hoàn ch ị ỉnh ................................. 12
11.8.1 T o cây nh phân hoàn ch ạ ị ỉnh................... 12
11.8.2 S nút c a cây hoàn ch ố ủ ỉnh....................... 12
11.9 Cây nh phân cân bị ằng ..................................... 13
12 Kiểm tra cây nh phân ị đầy đủ .............................. 13
13 Phản xạ gương cây ............................................... 13
14 S lá ch n c a cây ố ẵ ủ ................................................ 13
15 S nút có info lố ớn hơn k ....................................... 13
16 Kiểm tra đẳng cấu hai cây .................................... 13
17 S p x p ắ ế ................................................................. 13
17.1 n th Hiể ị ds........................................................ 13
17.2 Swap ................................................................13
17.3 SelectionSort .................................................... 14
17.4 InsertionSort .................................................... 14
17.5 BubleSort ......................................................... 14
17.6 MergSort .......................................................... 14
17.7 QuickSort ......................................................... 15
2
17.8 HeapSort .......................................................... 15
17.8.1 Max-heap ................................................. 15
17.8.2 Min-heap .................................................. 16
17.8.3 Khôi ph c tính chụ ất đống ......................... 16
17.8.4 Xây d ựng đống......................................... 16
17.8.5 S p x ắ ếp đống............................................ 16
18 Tìm ki m nh phân ế ị ...............................................16
18.1 Tìm ki m nh phân ế ị ...........................................16
18.2 Cây nh phân tìm kiị ếm (BST) ............................ 16
18.2.1 Thu t toán tìm kiậ ếm (Search) .................. 17
18.2.2 Thu t toán b sung (Insertion) ậ ổ ................ 17
18.2.3 Thu t toán lo i b (delete) ậ ạ ỏ ...................... 17
18.3 Cây AVL ............................................................ 17
18.3.1 Cây con trái cao hơn cây con phải do cây
con trái c a con trái ủ ................................................. 18
18.3.2 Cây con phải cao hơn cây con trái do cây
con ph i c a con ph i ả ủ ả .............................................. 18
18.3.3 Cây con trái co hơn cây con phải do cây
con ph i c a con trái ả ủ ................................................ 18
18.3.4 Cây con phải cao hơn cây con trái do cây
con trái c a con ph i ủ ả ................................................ 19
3
1 Tổ hợp
int C(int n, int k){
if ((k==0)||(k==n))
return 1;
else
return C(n-1,k-1)+C(n-1,k );
}
C(9, 5) = 126
2 Tháp Hà N i ộ
int solanchuyen = 0;
void thapHN(int n, char a, char b, char c){
if (n==1)
printf("%d:Chuyen 1 dia tu %c sang
%c\n",++solanchuyen,a,c);
else {
thapHN(n-1,a,c,b);
thapHN(1,a,b,c);
thapHN(n-1,b,a,c);
}
}
3 Quay lui hoán v ị
int n, count;
int a[20];
int m[5];
void Ghinhan() {
int i;
count++; printf("%i. ",count);
for (i=1; i<=n;i++) printf("%i ",a[i]);
printf("\n");
}
int UCV(int i, int k){
int j;
for(j=1;j<k;j++)
if(m[i]==a[j])
return 0;
return 1;
}
void hienhoanvi(int k){
int i;
for(i=1;i<=n;i++) {
if(UCV(i,k)==1) {
a[k] = m[i];
if(k==n) Ghinhan();
else hienhoanvi(k+1);
}
}
}
4 Hiển th ngoị ặc đúng
int n, count;
char a[20];
int Ghinhan() {
int i;
count++; printf("%i. ",count);
for (i=1; i<=n;i++) printf("%c ",a[i]);
printf("\n");
}
int UCV(char c, int k){
int t=0;
int i;
for(i=1;i<k;i++) {
if(a[i]=='(') t++;
4
else t ; --
if(t<0) return 0;
}
if(c=='(') t++;
else t ; --
if(k<n) {
if(t<0) return 0;
else return 1;
}
else if(k==n) {
if(t!=0) return 0;
else return 1;
}
}
void hienthingoacdung(int k){
if(UCV('(',k)==1) {
a[k] = '(';
if(k==n) Ghinhan();
else hienthingoacdung(k+1);
}
if(UCV(')',k)==1) {
a[k] = ')';
if(k==n) Ghinhan();
else hienthingoacdung(k+1);
}
}
5 X ếp hậu
int n, count;
int a[20];
int Ghinhan() {
int i;
count++; printf("%i. ",count);
for (i=1; i<=n;i++) printf("%i ",a[i]);
printf("\n");
}
int abs(int x){
if(x<0) return - x;
return x;
}
int UCV(int i, int k){
int j;
for(j=1;j<k;j++) {
if((a[j]==i)||(abs(a[j]-i)==abs(j-k)))
return 0;
}
return 1;
}
void xephau(int k){
int i;
for(i=1;i<=8;i++) {
if(UCV(i,k)==1) {
a[k] = i;
if(k==n) Ghinhan();
else xephau(k+1);
}
}
}
6 Danh sách móc n ối đơn
typedef int elementtype;
typedef struct _newNodeType {
5
elementtype Inf;
struct _newNodeType *Next;
} NodeType;
6.1 Xóa ph n tầ ử cuối
NodeType *delete_Last(NodeType *First){
if(First==NULL) return NULL;
NodeType *t2 = First;
NodeType *t1 = NULL;
if(t2->Next==NULL) {
free(t2);
return NULL;
}
while(t2->Next!=NULL) {
t1 = t2;
t2 = t2->Next;
}
t1->Next = NULL;
free(t2);
return First;
}
6.2 Xóa ph n tầ ử đầu
NodeType *delete_Head(NodeType *First){
if(First==NULL) return NULL;
NodeType *p = First;
First = First->Next;
free(p);
return First;
}
6.3 Chèn vào gi a ữ
void insertToMiddle(NodeType *pred, elementtype
datum) {
NodeType *newNode = (NodeType *)
malloc(sizeof(NodeType));
if(newNode == NULL) {
printf("Khong the cap phat bo nho\n");
return;
}
newNode->Inf = datum;
newNode->Next = pred->Next;
pred->Next = newNode;
return;
}
6.4 Chèn vào cuối
void insertToLast(NodeType *head, elementtype datum) {
NodeType *newNode = (NodeType *)
malloc(sizeof(NodeType));
if(newNode == NULL) {
printf("Khong the cap phat bo nho\n");
return NULL;
}
newNode->Inf = datum;
newNode->Next = NULL;
while(head->Next != NULL)
head = head->Next;
head->Next = newNode;
return;
}
6.5 Chèn vào đầu
NodeType *insertToHead(NodeType *head, elementtype
datum) {
NodeType *newNode = (NodeType *)
malloc(sizeof(NodeType));
if(newNode == NULL) {
6
printf("Khong the cap phat bo nho\n");
return NULL;
}
newNode->Inf = datum;
newNode->Next = head;
return newNode;
}
6.6 Hiển th danh sách ị
void printList(NodeType *head) {
while(head != NULL) {
printf("%d\t", head->Inf);
head = head->Next;
}
printf("\n");
return;
}
6.7 Tạo mới một nút
NodeType *createNewNode(elementtype datum) {
NodeType *newNode = (NodeType *)
malloc(sizeof(NodeType));
if(newNode == NULL) {
printf("Khong the cap phat bo nho\n");
return NULL;
}
newNode->Inf = datum;
newNode->Next = NULL;
return newNode;
}
6.8 Đảo chi u danh sách ề
NodeType *daoChieuDS_pp1(NodeType *header){
if(header==NULL) return NULL;
NodeType *dsmoi = NULL;
NodeType *p = header;
while(p!=NULL) {
dsmoi = Insert_ToHead(dsmoi,p->Inf);
p = p->Next;
}
return dsmoi;
}
6.9 Trộn 2 ds sx tăng dần thành 1 ds giảm
dần
ListNode *sortInsert(ListNode *head1, ListNode *head2) {
if(head1 == NULL || head2 == NULL)
return NULL;
ListNode *head = NULL, *compare = NULL;
do {
compare = head;
if(head1->Inf > head2->Inf) {
head = head2;
head2 = head2->next;
head->next = compare;
} else {
head = head1;
head1 = head1->next;
head->next = compare;
}
} while(head1 != NULL && head2 != NULL);
while(head1 != NULL) {
compare = head;
head = head1;
7
head1 = head1->next;
head->next = compare;
}
while(head2 != NULL) {
compare = head;
head = head2;
head2 = head2->next;
head->next = compare;
}
return head;
}
6.10 Trộn 2 ds sx giảm dần thành 1 ds giảm
dần
ListNode *sortInsert2(ListNode *head1, ListNode *head2)
{
if(head1 == NULL || head2 == NULL)
return NULL;
ListNode *compare = NULL, *insertNode = NULL;
if(head2->Inf > head1->Inf) {
compare = head1;
head1 = head2;
head2 = head2->next;
head1->next = compare;
}
insertNode = head1;
compare = head1->next;
do {
if(head2->Inf > compare->Inf) {
insertNode->next = head2;
head2 = head2->next;
insertNode = insertNode->next;
insertNode->next = compare;
} else {
insertNode = compare;
compare = compare->next;
}
}while(head2 != NULL && compare != NULL);
if(head2 != NULL)
insertNode->next = head2;
return head1;
}
7 Danh sách dùng m ảng
# define maxlength 1000
typedef int elementtype; /* elements are integers */
typedef struct list_tag {
elementtype elements [maxlength]; // khai báo mảng
1000 ph n t ầ ử
int last;
} list_type;
7.1 T ạo mới một nút
list_type *create() {
list_type* lp = (list_type*)malloc(sizeof(list_type));
lp->last = -1;
return lp;
}
int end (list_type *lp){
return (lp->last +1);
}
8
7.2 Thêm nút mới
void insert (elementtype x , int p , list_type * lp){
int v; // running position
if (lp -> last >= maxlength - 1) {
printf("\n%s ","list is full");
return;
}
if ((p < 0) || (p > lp -> last + 1)) {
printf("\n%s ","position does not exist");
return;
}
else {
int q;
for (q = lp -> last; q >= p; q ) --
lp -> elements [q+1] = lp -> elements [q];
lp -> last = lp -> last +1 ;
lp -> elements[p] = x;
}
}
7.3 Xóa nút
void deleteL(int p , list_type * lp){
int q; /* running position */
if ((p > lp-> last) || (p < 0)) {
printf("\n%s ","position does not exist");
return;
}
else /* shift elements */ {
lp -> last ; --
int q;
for (q = p; q <= lp ->last; q++)
lp -> elements [q] = lp -> elements [q+1];
}
}
7.4 Locate
int locate (elementtype x , list_type * lp){
int q;
for (q = 0; q <= lp ->last; q++)
if (lp -> elements [q] == x)
return (q);
return (lp -> last + 1); /* if not found */
}
7.5 Hi ển th ị ds
void hienthi(list_type *lp){
int i;
if(lp==NULL) return;
printf("Cac ptu co trong danh sach: \n");
for(i=0;i<lp->last+1;i++)
printf("%d ",lp->elements[i]);
printf("\n");
}
8 Stack – ds móc n ối đơn
typedef int Item;
typedef struct _StackNode {
Item item;
struct _StackNode *next;
} StackNode;
typedef struct _Stack {
StackNode *top;
} Stack;
8.1 T ạo mới một stack
Stack *StackInit(){
9
Stack *s = (Stack*)malloc(sizeof(Stack));
if(s==NULL) return NULL;
s->top = NULL;
return s;
}
8.2 Ds rỗng tr vả ề true
int StackEmpty(Stack *s){
return (s->top==NULL);
}
8.3 Push
void StackPush(Stack *s, Item x){
StackNode *newnode =
(StackNode*)malloc(sizeof(StackNode));
if(newnode==NULL) return;
newnode->item = x;
newnode->next = s->top;
s->top = newnode;
}
8.4 Pop
Item StackPop(Stack *s){
if(s->top == NULL) return NULL;
Item X = s->top->item;
StackNode *t = s->top;
s->top = s->top->next;
free(t);
return X;
}
8.5 L ấy ra các ph n t trong sta ầ ử ck
while(!StackEmpty(st))
printf("%d\t",StackPop(st));
9 Stack – mảng
typedef int Item;
static Item *s;
static int N;
9.1 T ạo mới một stack
void STACKinit(int maxN){
s = (Item *) malloc(maxN*sizeof(Item));
N = 0;
}
9.2 N ếu stack r ng tr vỗ ả ề true
int STACKempty() {
return N==0;
}
9.3 Push
void STACKpush(Item item) {
s[N++] = item;
}
9.4 Pop
Item STACKpop() {
return s[ N]; --
}
9.5 L ấy ra các ph n t trong stack ầ ử
while(!STACKempty())
printf("%d\n",STACKpop());
10 Queue ds móc n i – ố đôi
typedef int Item;
typedef struct _QueueNode {
Item item;
struct _QueueNode *next;
} QueueNode;
typedef struct _Queue {
QueueNode *front;
QueueNode *back;
} Queue;
10
10.1 Tạo m i m t queue ớ ộ
Queue *QueueInit() {
Queue *q = (Queue*)malloc(sizeof(Queue));
if(q==NULL) return NULL;
q->front = NULL;
q->back = NULL;
return q;
}
10.2 Nếu queue rỗng tr vả ề true
int QueueEmpty(Queue *q) {
return (q->front==NULL);
}
10.3 Thêm m t ph n t vào queue ộ ầ ử
void enqueue(Queue *q, Item x){
QueueNode *newnode =
(QueueNode*)malloc(sizeof(QueueNode));
if(newnode==NULL) return;
newnode->item = x;
newnode->next = NULL;
if((q->front==NULL)&&(q->back==NULL)) {
q->front = newnode;
q->back = newnode;
}
else {
q->back->next = newnode;
q->back = newnode;
}
}
10.4 Lấy ra m t ph n t cộ ầ ử ủa queue
Item dequeue(Queue *q){
if(QueueEmpty(q)) return NULL;
QueueNode *temp;
Item X;
if(q->front==q->back) {
temp = q->front;
X = temp->item;
free(temp);
q->front = NULL;
q->back = NULL;
return X;
}
else {
temp = q->front;
X = temp->item;
q->front = q->front->next;
free(temp);
return X;
}
}
10.5 Lấy h t các ph n t trong queue ế ầ ử
while(!QueueEmpty(q)) {
printf("%d\n",dequeue(q));
11 Cây
typedef struct _Tnode{
char word; // D u c t giữ liệ ấ ữ ở nút
struct _Tnode *leftmost_child;
struct _Tnode *right_sibling;
} treeNode;
11.1 Tạo mới một nút
treeNode *maketreenode(char w){
treeNode *temp =
(treeNode*)malloc(sizeof(treeNode));
if(temp==NULL) return NULL;
11
temp->leftmost_child = NULL;
temp->right_sibling = NULL;
temp->word = w;
return temp;
}
11.2 Duyệt cây theo th tứ ự trước
void preOrder(treeNode *r){
if(r==NULL)
return;
printf("%c ",r->word);
treeNode *p = r->leftmost_child;
while(p!=NULL) {
preOrder(p);
p = p->right_sibling;
}
}
11.3 Duyệt cây theo th t sau ứ ự
void postOrder(treeNode *r){
if(r==NULL)
return;
treeNode *p = r->leftmost_child;
while(p!=NULL) {
postOrder(p);
p = p->right_sibling;
}
printf("%c ",r->word);
}
11.4 Duyệt cây theo th t a ứ ự giữ
void inOrder(treeNode *r) {
if(r==NULL) return;
treeNode *p ->leftmost_child; = r
inOrder(p);
printf("%c ",r->word);
if(p!=NULL) p = p->right_sibling;
while(p!=NULL) {
inOrder(p);
p = p->right_sibling;
}
}
11.5 Đế ốm s nút cây
int CountNodes(treeNode *tree) {
if(tree==NULL) return 0;
int sonut = 1;
treeNode *p = tree->leftmost_child;
while(p!=NULL) {
sonut += CountNodes(p);
p = p->right_sibling;
}
return sonut;
}
11.6 Chiều sâu cây
int depth(treeNode *tree){
if(tree==NULL) return 0;
treeNode *p = tree->leftmost_child;
int k,dosaumax = 0;
while(p!=NULL) {
k = depth(p);
if(k>dosaumax)
dosaumax = k;
p = p->right_sibling;
}
12
return dosaumax + 1;
}
11.7 Cây nh ị phân đầy đủ
Cây nhị phân đầy đủ là cây nh phân: ị
Mỗi nút lá đều có cùng độ sâu
Các nút trong có đúng hai con
11.7.1 Tạo cây nh ị phân đầy đủ
treeNode *taocaynhiphandaydu(int n, char X)
{
if(n==0) return NULL;
treeNode *r = maketreenode(X);
treeNode *left = taocaynhiphandaydu(n-1,X);
treeNode *right = taocaynhiphandaydu(n-1,X);
r->left = left;
r->right = right;
return r;
}
11.7.2 Kiểm tra cây nh ị phân đầy đủ
int kiemtramotcaynhiphandaydu(treeNode *tree)
{
if(tree==NULL) return 0;
if((tree->left==NULL)&&(tree->right==NULL))
return 1;
int i = kiemtramotcaynhiphandaydu(tree->left);
int j = kiemtramotcaynhiphandaydu(tree->right);
int hi = depth(tree->left);
int hj = depth(tree->right);
if((i==1)&&(j==1)&&(hi==hj))
return 1;
else return 0;
}
11.8 Cây nh phân hoàn ch ị ỉnh
Cây nh phân hoàn ch nh là cây nhị ỉ ị phân độ sâu n thỏa
mãn:
Là cây nhị phân đầy đủ ếu không tính đế n n các
nút sâu n ở độ
Tấ ảt c các nút sâu n l ch sang trái nh t có ở độ ệ ấ
thể được
11.8.1 Tạo cây nh phân hoàn ch ị ỉnh
treeNode *taocaynhiphanhoanchinh(int n, char X) {
int k = somuccuacayhc(n);
treeNode *r = taocaynhiphandaydu(k);
}
11.8.2 S ố nút c a cây hoàn chủ ỉnh
int somuccuacayhc(int n) {
int k=0;
while(power(2,k)-1<=n)
k++;
return k-1;
13
}
11.9 Cây nh phân cân b ị ằng
Cây nh phân cân b ng là cây có chi u cao cây con trái và ị ằ ề
chiều cao cây con ph i c a m i nút chênh lả ủ ọ ệch nhau
không quá 1 đơn vị
12 Kiểm tra cây nhị phân đầy đủ
int kiemtramotcaynhiphandaydu(treeNode *tree){
if(tree==NULL) return 0;
if((tree->left==NULL)&&(tree->right==NULL))
return 1;
int i = kiemtramotcaynhiphandaydu(tree->left);
int j = kiemtramotcaynhiphandaydu(tree->right);
int hi = depth(tree->left);
int hj = depth(tree->right);
if((i==1)&&(j==1)&&(hi==hj))
return 1;
else return 0;
}
13 Phản xạ gương cây
treeNode *mirror(treeNode *nodePrt) {
if (nodePrt == NULL)
return NULL;
treeNode *tmp = mirror(nodePrt->left);
nodePrt->left = mirror(nodePrt->right);
nodePrt->right = tmp;
return nodePr t;
}
14 Số lá chẵn của cây
Int EvenLeaf(treeNode *RootTree) {
If(RootTree == null)
Return 0;
If(RootTree-left==null && RootTree->right ==null) {
If(RootTree->key % 2)
Return 0;
Return 1;
}
Return EvenLeaf(RootTree->left) + EvenLeaf(RootTree-
>right);
}
15 Số nút có info l ớn hơn k
Giống bài duy t cây ệ
16 Kiểm tra đẳng cấu hai cây
17 Sắp xếp
17.1 Hiển thị ds
void Print(int p[], int len) {
int i;
for(i = 0; i < len;)
printf("%d\t", p[i++]);
printf("\n");
}
17.2 Swap
void Swap(int *a, int *b) {
int tmp = *a;
*a = *b;
14
*b = tmp;
}
17.3 SelectionSort
void SelectionSort(int p[], int len) {
int i, j, jmin;
for(i = 0; i < len - 1; ++i) {
jmin = i;
for(j=i+1; j < len; ++ j)
if(p[j] < p[jmin])
jmin = j;
if(jmin != i)
Swap(&p[jmin], &p[i]);
}
}
17.4 InsertionSort
void InsertionSort(int a[], int len) {
int i, j, tmp;
for(i = 0; i < len-1; ++i) {
tmp = a[i];
j = i - 1;
while(j > 0 && tmp < a[j]) {
a[j+1] = a[j];
--j;
}
a[j+1] = tmp;
}
return;
}
17.5 BubleSort
void BubbleSort(int a[], int len) {
int i, j, tmp;
for(i = 0; i < len - 1; ++i)
for(j = i; j < len; ++j)
if(a[i] > a[j]) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
17.6 MergSort
void MergeSort(int a[], int first, int last) {
if(first < last) {
int mid = (first + last)/2;
MergeSort(a, first, mid);
MergeSort(a, mid+1, last);
Merge(a, first, mid, last);
} else
return;
15
}
void Merge(int a[], int first, int mid, int last) {
int tmpA[MAX_SIZE]; // mang phu
int first1 = first; int last1 = mid;
int first2 = mid + 1; int last2 = last;
int index = first1;
for(; (first1 <= last1) && (first2 <= last2); ++index) {
if(a[first1] < a[first2]) {
tmpA[index] = a[first1];
++first1;
} else {
tmpA[index] = a[first2];
++first2;
}
}
for(; first1 <= last1; ++first1, ++index)
tmpA[index] = a[first1]; // sao not day con 1
for(; first2 <= last2; ++first2, ++index)
tmpA[index] = a[first2]; // sao not day con 2
for(index = first; index <= last; ++index)
a[index] = tmpA[index]; // sao tra mang ket qua
return;
}
17.7 QuickSort
void QuickSort(int a[], int first, int last) {
if(first < last) {
int pivot = Partition(a, first, last);
if(first < pivot)
QuickSort(a, first, pivot - 1);
else
QuickSort(a, pivot + 1, last);
}
return;
}
int Partition(int a[], int first, int last) {
int i = first, j = last + 1, p = a[first];
while(i < j) {
++i;
while((i <= last) && (a[i] < p))
++i;
--j;
while((j >= first) && (a[j] > p))
--j;
Swap(&a[i], &a[j]);
}
Swap(&a[i], &a[j]);
Swap(&a[j], &a[first]);
return j;
}
17.8 HeapSort
Đố ịng là cây nh phân g n hoàn ch nh có 2 tính ch ầ ỉ ất:
Tính c u trúc: t t c các mấ ấ ả ức đều là đầy trừ mức
cuối cùng. M c cu n y t trái sang ứ ối được điề đầ ừ
phải
Tính ch ng: v i m i nút ta luôn có con ất đố ớ ỗ ≥ hoặc
≤ cha.
17.8.1 Max-heap
Với m i nút I ta luôn có A[parent(i)] ọ ≥ A[ i]
16
17.8.2 Min-heap
Với m i nút I ta luôn có A[parent(i)] ọ ≤ A[ i]
17.8.3 Khôi ph c tính ch ụ ất đống
17.8.4 Xây dựng đống
17.8.5 S ắp xếp đống
18 Tìm ki m nh phân ế ị
18.1 Tìm ki m nh phân ế ị
Điều ki tìm ki m nh phân là: ện để ế ị
Ds ph c s p xải đượ ắ ếp theo th t không giứ ự ảm
Phải cho phép tr c truy (tự ức là không áp dụng
đượ ớc v i ds móc n ối)
18.2 Cây nh phân tìm ki m (BST) ị ế
Cây nh phân tìm kiị ếm là cây nh phân: ị
Left tr n con trái ỏ đế
Right tr n con ph i ỏ đế ả
Parent trỏ đến cha
Info
Tính ch t BST: m i nút thu c cây con trái có giá tr ấ ọ ộ ị
nhỏ hơn cha. Mọi nút thu c cây con ph i có giá ộ ả
trị lớn hơn cha.
17
Duyệt cây theo thứ tự giữa s ẽ đượ ắc dãy s p xếp
18.2.1 Thu ật toán tìm ki m (Search) ế
Nếu khóa cần tìm nhỏ hơn khóa của nút hiện tại
thì ti p t c tìm ki cây con trái. ế ụ ếm ở
Nếu khóa cần tìm l a c a nút hi n tớn hơn khó ủ ệ ại
thì ti p t c tim ki cây con ph ế ụ ếm ở ải.
Nếu tìm thấy thì trả l i con trạ ở đên nút chứa khóa
cần tìm, ngược lại trả về Null.
18.2.2 Thu ật toán bổ sung (Insertion)
Tạ ớ ứo nút m i ch a ph n t chèn ầ ử
Di chuyển trên cây để tìm cha của nút m i: so ớ
sách khóa c a ph n t c n chèn v i khóa c a nút ủ ầ ử ầ ớ ủ
đang xét, nếu khóa c a ph n t c n chèn lủ ầ ử ầ ớn hơn
(nhỏ hơn) khóa của nút đang xét thì rẽ theo con
phải ( con trái) của nút đang xét. Nếu gặp Null thì
dừng, nút đang xét là cha cần tìm.
Gắn nút mới vào cha vừa tìm được.
18.2.3 Thu ật toán loại b (delete) ỏ
Nếu nút cần xóa là lá
Nếu nút cần xóa ch có con trái ỉ
Nếu nút cần xóa ch có con phỉ ải
Nếu nút cần xóa có hai con :
18.3 Cây AVL
Là cây nh phân tìm ki m th a mãn tính ch t AVL: chiị ế ỏ ấ ều
cao c a cây con trái và cây con ph i c a m c ch sai ủ ả ủ ột gố ỉ
khác nhau không quá 1 và c cây con trái và cây con phả ải
đều là cây AVL.
Có 4 trường hợp khôi ph c tính cân b ng c a cây: ụ ằ ủ
18
18.3.1 Cây con trái cao hơn cây con phải do cây con
trái c a con trái ủ
Thự ằc hiện cân b ng:
18.3.2 Cây con phải cao hơn cây con trái do cây con
phải c a con phủ ải
Thự ằc hiện cân b ng:
18.3.3 Cây con trái co hơn cây con phải do cây con
phải của con trái
Thự ằc hiện cân b ng:
19
18.3.4 Cây con phải cao hơn cây con trái do cây con
trái c a con ph i ủ ả
Thự ằc hiện cân b ng:
| 1/19
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Mục lục 9.5
Lấy ra các phần tử trong stack ........................... 9 1
Tổ hợp ........................................................................ 3 10
Queue – ds móc nối đôi ......................................... 9 2
Tháp Hà Nội .............................................................. .3 10.1
Tạo mới một queue ......................................... 10 3
Quay lui hoán vị ......................................................... 3 10.2
Nếu queue rỗng trả về true ............................. 10 4
Hiển thị ngoặc đúng ................................................... 3 10.3
Thêm một phần tử vào queue ......................... 10 5
Xếp hậu ...................................................................... 4 10.4
Lấy ra một phần tử của queue ......................... 10 6
Danh sách móc nối đơn ............................................. 4 10.5
Lấy hết các phần tử trong queue ..................... 10 6.1
Xóa phần tử cuối ................................................ 5 11
Cây ....................................................................... 10 6.2
Xóa phần tử đầu ............................................... .5 11.1
Tạo mới một nút .............................................. 10 6.3
Chèn vào giữa .................................................... 5 11.2
Duyệt cây theo thứ tự trước .......................... .11 6.4
Chèn vào cuối ..................................................... 5 11.3
Duyệt cây theo thứ tự sau ............................... 11 6.5
Chèn vào đầu ..................................................... 5 11.4
Duyệt cây theo thứ tự giữa ............................ .11 6.6
Hiển thị danh sách ............................................. 6 11.5
Đếm số nút cây ................................................ 11 6.7
Tạo mới một nút ................................................ 6 11.6
Chiều sâu cây ................................................... 11 6.8
Đảo chiều danh sách .......................................... 6 11.7
Cây nhị phân đầy đủ ........................................ 12 6.9
Trộn 2 ds sx tăng dần thành 1 ds giảm dần ....... 6 11.7.1
Tạo cây nhị phân đầy đủ .......................... 12 6.10
Trộn 2 ds sx giảm dần thành 1 ds giảm dần ....... 7 11.7.2
Kiểm tra cây nhị phân đầy đủ .................. 12 7 Danh sách dùng mản
g................................................ 7 11.8 Cây nhị phân hoàn chỉn
h ................................. 12 7.1
Tạo mới một nút ................................................ 7 11.8.1
Tạo cây nhị phân hoàn chỉn h................... 12 7.2
Thêm nút mới ................................................... .8 11.8.2
Số nút của cây hoàn chỉn h ....................... 12 7.3
Xóa nút ............................................................... 8 11.9
Cây nhị phân cân bằng ..................................... 13 7.4
Locate ................................................................. 8 12
Kiểm tra cây nhị phân đầy đủ .............................. 13 7.5 Hiển thị d
s .......................................................... 8 13
Phản xạ gương cây ............................................... 13 8
Stack – ds móc nối đơn .............................................. 8 14
Số lá chẵn của cây ................................................ 13 8.1
Tạo mới một stack ............................................. 8 15
Số nút có info lớn hơn k ....................................... 13 8.2
Ds rỗng trả về true ............................................. 9 16
Kiểm tra đẳng cấu hai cây .................................... 13 8.3
Push .................................................................. .9 17
Sắp xếp ................................................................. 13 8.4
Pop ..................................................................... 9 17.1 Hiển thị d
s........................................................ 13 8.5
Lấy ra các phần tử trong stack ........................... 9 17.2
Swap ............................................................... .13 9 Stack – mản
g.............................................................. 9 17.3
SelectionSort .................................................... 14 9.1
Tạo mới một stack ............................................. 9 17.4
InsertionSort .................................................... 14 9.2
Nếu stack rỗng trả về true ................................. 9 17.5
BubleSort ......................................................... 14 9.3
Push .................................................................. .9 17.6
MergSort .......................................................... 14 9.4
Pop ..................................................................... 9 17.7
QuickSort ......................................................... 15 1 17.8
HeapSort .......................................................... 15 17.8.1
Max-heap ................................................. 15 17.8.2
Min-heap .................................................. 16 17.8.3
Khôi phục tính chất đống ......................... 16 17.8.4 Xây dựng đốn
g ......................................... 16 17.8.5 Sắp xếp đốn
g............................................ 16 18
Tìm kiếm nhị phân .............................................. .16 18.1
Tìm kiếm nhị phân .......................................... .16 18.2
Cây nhị phân tìm kiếm (BST) ............................ 16 18.2.1
Thuật toán tìm kiếm (Search) .................. 17 18.2.2
Thuật toán bổ sung (Insertion) ................ 17 18.2.3
Thuật toán loại bỏ (delete) ...................... 17 18.3
Cây AVL ............................................................ 17 18.3.1
Cây con trái cao hơn cây con phải do cây
con trái của con trái ................................................. 18 18.3.2
Cây con phải cao hơn cây con trái do cây
con phải của con phải .............................................. 18 18.3.3
Cây con trái co hơn cây con phải do cây
con phải của con trái ................................................ 18 18.3.4
Cây con phải cao hơn cây con trái do cây
con trái của con phải ................................................ 19 2
1 Tổ hợp int j; int C(int n, int k){
for(j=1;j if ((k==0)||(k==n)) if(m[i]==a[j]) return 1; return 0; else return 1; return C(n-1,k-1)+C(n-1,k) ; } } void hienhoanvi(int k){ C(9, 5) = 126 int i;
2 Tháp Hà Nội for(i=1;i<=n;i++) { int solanchuyen = 0; if(UCV(i,k)==1) {
void thapHN(int n, char a, char b, char c){ a[k] = m[i]; if (n==1) if(k==n) Ghinhan();
printf("%d:Chuyen 1 dia tu %c sang %c\n",++solanchuyen,a,c); else hienhoanvi(k+1); else { } thapHN(n-1,a,c,b); } thapHN(1,a,b,c); } thapHN(n-1,b,a,c);
4 Hiển thị ngoặc đúng int n, count; } char a[20]; } int Ghinhan() {
3 Quay lui hoán vị int n, count; int i; int a[20];
count++; printf("%i. ",count); int m[5];
for (i=1; i<=n;i++) printf("%c ",a[i]); void Ghinhan() { printf("\n"); int i; }
count++; printf("%i. ",count); int UCV(char c, int k){
for (i=1; i<=n;i++) printf("%i ",a[i]); int t=0; printf("\n"); int i; }
for(i=1;iint UCV(int i, int k){ if(a[i]=='(') t++; 3 else t- ; - int i; if(t<0) return 0;
count++; printf("%i. ",count); }
for (i=1; i<=n;i++) printf("%i ",a[i]); if(c=='(') t++; printf("\n"); else t- ; - } if(kint abs(int x){ if(t<0) return 0; if(x<0) return -x; else return 1; return x; } } else if(k==n) { int UCV(int i, int k){ if(t!=0) return 0; int j; else return 1; for(j=1;j }
if((a[j]==i)||(abs(a[j]-i)==abs(j-k))) } return 0; void hienthingoacdung(int k){ } if(UCV('(',k)==1) { return 1; a[k] = '('; } if(k==n) Ghinhan(); void xephau(int k){ else hienthingoacdung(k+1); int i; } for(i=1;i<=8;i++) { if(UCV(')',k)==1) { if(UCV(i,k)==1) { a[k] = ')'; a[k] = i; if(k==n) Ghinhan(); if(k==n) Ghinhan(); else hienthingoacdung(k+1); else xephau(k+1); } } } }
5 Xếp hậu } int n, count;
6 Danh sách móc nối đơn int a[20]; typedef int elementtype; int Ghinhan() { typedef struct _newNodeType { 4 elementtype Inf;
NodeType *newNode = (NodeType *) malloc(sizeof(NodeType)); struct _newNodeType *Next; if(newNode == NULL) { } NodeType;
printf("Khong the cap phat bo nho\n");
6.1 Xóa phần tử cuối
NodeType *delete_Last(NodeType *First){ return; if(First==NULL) return NULL; } NodeType *t2 = First; newNode->Inf = datum; NodeType *t1 = NULL;
newNode->Next = pred->Next; if(t2->Next==NULL) { pred->Next = newNode; free(t2); return; return NULL; } }
6.4 Chèn vào cuối
void insertToLast(NodeType *head, elementtype datum) { while(t2->Next!=NULL) {
NodeType *newNode = (NodeType *) t1 = t2; malloc(sizeof(NodeType)); t2 = t2->Next; if(newNode == NULL) { }
printf("Khong the cap phat bo nho\n"); t1->Next = NULL; return NULL; free(t2); } return First; newNode->Inf = datum; } newNode->Next = NULL;
6.2 Xóa phần tử đầu while(head->Next != NULL)
NodeType *delete_Head(NodeType *First){ head = head->Next; if(First==NULL) return NULL; head->Next = newNode; NodeType *p = First; return; First = First->Next; } free(p);
6.5 Chèn vào đầu return First;
NodeType *insertToHead(NodeType *head, elementtype datum) { }
NodeType *newNode = (NodeType *)
6.3 Chèn vào giữa malloc(sizeof(NodeType));
void insertToMiddle(NodeType *pred, elementtype datum) { if(newNode == NULL) { 5
printf("Khong the cap phat bo nho\n"); NodeType *dsmoi = NULL; return NULL; NodeType *p = header; } while(p!=NULL) { newNode->Inf = datum;
dsmoi = Insert_ToHead(dsmoi,p->Inf); newNode->Next = head; p = p->Next; return newNode; } } return dsmoi;
6.6 Hiển thị danh sách }
void printList(NodeType *head) {
6.9 Trộn 2 ds sx tăng dần thành 1 ds giảm while(head != NULL) { dần
ListNode *sortInsert(ListNode *head1, ListNode *head2) {
printf("%d\t", head->Inf);
if(head1 == NULL || head2 == NULL) head = head->Next; return NULL; }
ListNode *head = NULL, *compare = NULL; printf("\n"); return; do { } compare = head;
6.7 Tạo mới một nút
NodeType *createNewNode(elementtype datum) {
if(head1->Inf > head2->Inf) {
NodeType *newNode = (NodeType *) head = head2; malloc(sizeof(NodeType)); head2 = head2->next; if(newNode == NULL) { head->next = compare;
printf("Khong the cap phat bo nho\n"); } else { return NULL; head = head1; } head1 = head1->next; newNode->Inf = datum; head->next = compare; newNode->Next = NULL; } return newNode;
} while(head1 != NULL && head2 != NULL); } while(head1 != NULL) {
6.8 Đảo chiều danh sách compare = head;
NodeType *daoChieuDS_pp1(NodeType *header){ head = head1;
if(header==NULL) return NULL; 6 head1 = head1->next; head2 = head2->next; head->next = compare;
insertNode = insertNode->next; }
insertNode->next = compare; while(head2 != NULL) { } else { compare = head; insertNode = compare; head = head2; compare = compare->next; head2 = head2->next; } head->next = compare;
}while(head2 != NULL && compare != NULL); } if(head2 != NULL) return head; insertNode->next = head2; }
6.10 Trộn 2 ds sx giảm dần thành 1 ds giảm return head1; dần }
ListNode *sortInsert2(ListNode *head1, ListNode *head2) {
7 Danh sách dùng mảng # define maxlength 1000
if(head1 == NULL || head2 == NULL)
typedef int elementtype; /* elements are integers */ return NULL; typedef struct list_tag {
ListNode *compare = NULL, *insertNode = NULL;
elementtype elements [maxlength]; // khai báo mảng
if(head2->Inf > head1->Inf) { 1000 phần tử int last; compare = head1; } list_type; head1 = head2;
7.1 Tạo mới một nút head2 = head2->next; list_type *create() { head1->next = compare;
list_type* lp = (list_type*)malloc(sizeof(list_type)); } lp->last = -1; insertNode = head1; return lp; compare = head1->next; } int end (list_type *lp){ do { return (lp->last +1);
if(head2->Inf > compare->Inf) { } insertNode->next = head2; 7
7.2 Thêm nút mới
lp -> elements [q] = lp -> elements [q+1];
void insert (elementtype x , int p , list_type * lp){ } int v; // running position }
if (lp -> last >= maxlength - 1) { 7.4 Locate
printf("\n%s ","list is full");
int locate (elementtype x , list_type * lp){ return; int q; }
for (q = 0; q <= lp ->last; q++)
if ((p < 0) || (p > lp -> last + 1)) {
if (lp -> elements [q] == x)
printf("\n%s ","position does not exist"); return (q); return;
return (lp -> last + 1); /* if not found */ } } else {
7.5 Hiển thị d s void hienthi(list_type *lp){ int q; int i;
for (q = lp -> last; q >= p; q- ) - if(lp==NULL) return;
lp -> elements [q+1] = lp -> elements [q];
printf("Cac ptu co trong danh sach: \n");
lp -> last = lp -> last +1 ; for(i=0;ilast+1;i++) lp -> elements[p] = x;
printf("%d ",lp->elements[i]); } printf("\n"); } } 7.3 Xóa nút
void deleteL(int p , list_type * lp){
8 Stack – ds móc nối đơn typedef int Item;
int q; /* running position */ typedef struct _StackNode {
if ((p > lp-> last) || (p < 0)) { Item item;
printf("\n%s ","position does not exist"); struct _StackNode *next; return; } StackNode; } typedef struct _Stack { else /* shift elements */ { StackNode *top; lp -> last - ; - } Stack; int q; ạ
for (q = p; q <= lp ->last; q++)
8.1 T o mới một stack Stack *StackInit(){ 8
Stack *s = (Stack*)malloc(sizeof(Stack)); static Item *s; if(s==NULL) return NULL; static int N; s->top = NULL;
9.1 Tạo mới một stack void STACKinit(int maxN){ return s;
s = (Item *) malloc(maxN*sizeof(Item)); } N = 0;
8.2 Ds rỗng trả về true int StackEmpty(Stack *s){ } return (s->top==NULL);
9.2 Nếu stack rỗng trả về true int STACKempty() { } return N==0; 8.3 Push
void StackPush(Stack *s, Item x){ } StackNode *newnode = 9.3 Push
(StackNode*)malloc(sizeof(StackNode)); void STACKpush(Item item) { if(newnode==NULL) return; s[N++] = item; newnode->item = x; }
newnode->next = s->top; 9.4 Pop Item STACKpop() { s->top = newnode; return s[- N - ]; } } 8.4 Pop Item StackPop(Stack *s){
9.5 Lấy ra các phần tử trong stack while(!STACKempty())
if(s->top == NULL) return NULL; printf("%d\n",STACKpop()); Item X = s->top->item; StackNode *t = s->top;
10 Queue – ds móc nối đôi typedef int Item;
s->top = s->top->next; typedef struct _QueueNode { free(t); Item item; return X; struct _QueueNode *next; } } QueueNode;
8.5 Lấy ra các phần tử trong stack typedef struct _Queue { while(!StackEmpty(st)) QueueNode *front; printf("%d\t",StackPop(st)); QueueNode *back;
9 Stack – mảng typedef int Item; } Queue; 9
10.1 Tạo mới một queue Item X; Queue *QueueInit() {
if(q->front==q->back) {
Queue *q = (Queue*)malloc(sizeof(Queue)); temp = q->front; if(q==NULL) return NULL; X = temp->item; q->front = NULL; free(temp); q->back = NULL; q->front = NULL; return q; q->back = NULL; } return X;
10.2 Nếu queue rỗng trả về true } int QueueEmpty(Queue *q) { else { return (q->front==NULL); temp = q->front; } X = temp->item;
10.3 Thêm một phần tử vào queue
void enqueue(Queue *q, Item x){
q->front = q->front->next; QueueNode *newnode = free(temp);
(QueueNode*)malloc(sizeof(QueueNode)); return X; if(newnode==NULL) return; } newnode->item = x; } newnode->next = NULL;
10.5 Lấy hết các phần tử trong queue
if((q->front==NULL)&&(q->back==NULL)) { while(!QueueEmpty(q)) { q->front = newnode; printf("%d\n",dequeue(q)); q->back = newnode; 11 Cây } typedef struct _Tnode{
char word; // Dữ liệu cất giữ ở nút else {
q->back->next = newnode;
struct _Tnode *leftmost_child; q->back = newnode; struct _Tnode *right_sibling; } } treeNode; }
11.1 Tạo mới một nút
treeNode *maketreenode(char w){
10.4 Lấy ra một phần tử của queue Item dequeue(Queue *q){ treeNode *temp =
(treeNode*)malloc(sizeof(treeNode));
if(QueueEmpty(q)) return NULL; if(temp==NULL) return NULL; QueueNode *temp; 10
temp->leftmost_child = NULL; inOrder(p);
temp->right_sibling = NULL; printf("%c ",r->word); temp->word = w;
if(p!=NULL) p = p->right_sibling; return temp; while(p!=NULL) { } inOrder(p);
11.2 Duyệt cây theo thứ tự trước p = p->right_sibling; void preOrder(treeNode *r){ } if(r==NULL) } return;
11.5 Đếm số nút cây printf("%c ",r->word);
int CountNodes(treeNode *tree) {
treeNode *p = r->leftmost_child; if(tree==NULL) return 0; while(p!=NULL) { int sonut = 1; preOrder(p);
treeNode *p = tree->leftmost_child; p = p->right_sibling; while(p!=NULL) { } sonut += CountNodes(p); } p = p->right_sibling;
11.3 Duyệt cây theo thứ tự sau } void postOrder(treeNode *r){ return sonut; if(r==NULL) } return;
11.6 Chiều sâu cây
treeNode *p = r->leftmost_child; int depth(treeNode *tree){ while(p!=NULL) { if(tree==NULL) return 0; postOrder(p);
treeNode *p = tree->leftmost_child; p = p->right_sibling; int k,dosaumax = 0; } while(p!=NULL) { printf("%c ",r->word); k = depth(p); } if(k>dosaumax)
11.4 Duyệt cây theo thứ tự giữa dosaumax = k; void inOrder(treeNode *r) { p = p->right_sibling; if(r==NULL) return; }
treeNode *p = r->leftmost_child; 11 return dosaumax + 1;
int j = kiemtramotcaynhiphandaydu(tree->right); }
int hi = depth(tree->left);
11.7 Cây nhị phân đầy đủ
int hj = depth(tree->right);
Cây nhị phân đầy đủ là cây nhị phân:
if((i==1)&&(j==1)&&(hi==hj))
 Mỗi nút lá đều có cùng độ sâu
 Các nút trong có đúng hai con return 1; else return 0 ; }
11.8 Cây nhị phân hoàn chỉnh
Cây nhị phân hoàn chỉnh là cây nhị phân độ sâu n thỏa mãn: n n các
 Là cây nhị phân đầy đủ ếu không tính đế nút ở độ sâu n
11.7.1 Tạo cây nhị phân đầy đủ
 Tất cả các nút ở độ sâu n lệch sang trái nhất có
treeNode *taocaynhiphandaydu(int n, char X) thể được { if(n==0) return NULL;
treeNode *r = maketreenode(X);
treeNode *left = taocaynhiphandaydu(n-1,X);
treeNode *right = taocaynhiphandaydu(n-1,X); r->left = left;
11.8.1 Tạo cây nhị phân hoàn chỉnh r->right = right;
treeNode *taocaynhiphanhoanchinh(int n, char X) { return r; int k = somuccuacayhc(n); }
treeNode *r = taocaynhiphandaydu(k);
11.7.2 Kiểm tra cây nhị phân đầy đủ }
int kiemtramotcaynhiphandaydu(treeNode *tree)
11.8.2 Số nút của cây hoàn chỉnh { int somuccuacayhc(int n) { if(tree==NULL) return 0; int k=0;
if((tree->left==NULL)&&(tree->right==NULL)) while(power(2,k)-1<=n) return 1; k++;
int i = kiemtramotcaynhiphandaydu(tree->left); return k-1; 12 } return nodePrt ;
11.9 Cây nhị phân cân bằn g }
Cây nhị phân cân bằng là cây có chiều cao cây con trái và
14 Số lá chẵn của cây
chiều cao cây con phải của mọi nút chênh lệch nhau
Int EvenLeaf(treeNode *RootTree) { không quá 1 đơn vị If(RootTree == null) Return 0;
If(RootTree-left==null && RootTree->right ==null) { If(RootTree->key % 2) Return 0; Return 1; }
12 Kiểm tra cây nhị phân đầy đủ
Return EvenLeaf(RootTree->left) + EvenLeaf(RootTree-
int kiemtramotcaynhiphandaydu(treeNode *tree){ >right); if(tree==NULL) return 0; }
if((tree->left==NULL)&&(tree->right==NULL))
15 Số nút có info lớn hơn k return 1; Giống bài duyệt cây
int i = kiemtramotcaynhiphandaydu(tree->left);
16 Kiểm tra đẳng cấu hai cây
int j = kiemtramotcaynhiphandaydu(tree->right);
17 Sắp xếp
int hi = depth(tree->left);
int hj = depth(tree->right);
17.1 Hiển thị ds
void Print(int p[], int len) {
if((i==1)&&(j==1)&&(hi==hj)) int i; return 1 ; for(i = 0; i < len;) else return 0; } printf("%d\t", p[i++]);
13 Phản xạ gương cây printf("\n");
treeNode *mirror(treeNode *nodePrt) { } if (nodePrt == NULL) 17.2 Swap return NULL; void Swap(int *a, int *b) {
treeNode *tmp = mirror(nodePrt->left); int tmp = *a;
nodePrt->left = mirror(nodePrt->right); *a = *b; nodePrt->right = tmp; 13 *b = tmp; 17.5 BubleSort
void BubbleSort(int a[], int len) { } int i, j, tmp; 17.3 SelectionSort
void SelectionSort(int p[], int len) {
for(i = 0; i < len - 1; ++i) int i, j, jmin; for(j = i; j < len; ++j)
for(i = 0; i < len - 1; ++i) { if(a[i] > a[j]) { jmin = i; tmp = a[i]; for(j=i+1; j < len; ++ j) a[i] = a[j]; if(p[j] < p[jmin]) a[j] = tmp; jmin = j; } if(jmin != i) }
Swap(&p[jmin], &p[i]); 17.6 MergSort } } 17.4 InsertionSort
void InsertionSort(int a[], int len) { int i, j, tmp;
for(i = 0; i < len-1; ++i) { tmp = a[i]; j = i - 1 ;
while(j > 0 && tmp < a[j]) {
void MergeSort(int a[], int first, int last) { a[j+1] = a[j]; if(first < last) { --j ; int mid = (first + last)/2; } MergeSort(a, first, mid); a[j+1] = tmp; MergeSort(a, mid+1, last); } Merge(a, first, mid, last); return; } else } return; 14 }
QuickSort(a, first, pivot - 1);
void Merge(int a[], int first, int mid, int last) { else
int tmpA[MAX_SIZE]; // mang phu
QuickSort(a, pivot + 1, last);
int first1 = first; int last1 = mid; }
int first2 = mid + 1; int last2 = last; return; int index = first1; }
for(; (first1 <= last1) && (first2 <= last2); ++index) {
int Partition(int a[], int first, int last) {
if(a[first1] < a[first2]) {
int i = first, j = last + 1, p = a[first]; tmpA[index] = a[first1]; while(i < j) { ++first1; ++i; } else {
while((i <= last) && (a[i] < p)) tmpA[index] = a[first2]; ++i; ++first2; --j ; }
while((j >= first) && (a[j] > p)) } --j ;
for(; first1 <= last1; ++first1, ++index) Swap(&a[i], &a[j]);
tmpA[index] = a[first1]; // sao not day con 1 }
for(; first2 <= last2; ++first2, ++index) Swap(&a[i], &a[j]);
tmpA[index] = a[first2]; // sao not day con 2
Swap(&a[j], &a[first]);
for(index = first; index <= last; ++index) return j;
a[index] = tmpA[index]; // sao tra mang ket qua } return; 17.8 HeapSort
Đống là cây nhị phân gần hoàn chỉnh có 2 tính chất : }
 Tính cấu trúc: tất cả các mức đều là đầy trừ mức 17.7 QuickSort
cuối cùng. Mức cuối được điền đầy từ trái sang
void QuickSort(int a[], int first, int last) { phải if(first < last) {
 Tính chất đống: với mỗi nút ta luôn có con ≥ hoặc ≤ cha.
int pivot = Partition(a, first, last); 17.8.1 Max-heap if(first < pivot)
Với mọi nút I ta luôn có A[parent(i)] ≥ A[ i] 15
17.8.4 Xây dựng đống
17.8.5 Sắp xếp đống 17.8.2 Min-heap
Với mọi nút I ta luôn có A[parent(i)] ≤ A[ i]
18 Tìm kiếm nhị phân
17.8.3 Khôi phục tính chất đốn g
18.1 Tìm kiếm nhị phân
Điều kiện để tìm kiếm nhị phân là:
 Ds phải được sắp xếp theo thứ tự không giảm
 Phải cho phép trực truy (tức là không áp dụng được với ds móc nối )
18.2 Cây nhị phân tìm kiếm (BST)
Cây nhị phân tìm kiếm là cây nhị phân:
 Left trỏ đến con trái
 Right trỏ đến con phải  Parent trỏ đến cha  Info
 Tính chất BST: mọi nút thuộc cây con trái có giá trị
nhỏ hơn cha. Mọi nút thuộc cây con phải có giá trị lớn hơn cha. 16
 Nếu nút cần xóa chỉ có con trái
 Nếu nút cần xóa chỉ có con phải
Duyệt cây theo thứ tự giữa sẽ được dãy sắp xếp
18.2.1 Thuật toán tìm kiếm (Search)
 Nếu khóa cần tìm nhỏ hơn khóa của nút hiện tại
thì tiếp tục tìm kiếm ở cây con trái.
 Nếu khóa cần tìm lớn hơn khóa của nút hiện tại
thì tiếp tục tim kiếm ở cây con phải .
 Nếu tìm thấy thì trả lại con trở đên nút chứa khóa
cần tìm, ngược lại trả về Null.
 Nếu nút cần xóa có hai con:
18.2.2 Thuật toán bổ sung (Insertion)
 Tạo nút mới chứa phần tử chèn
 Di chuyển trên cây để tìm cha của nút mới: so
sách khóa của phần tử cần chèn với khóa của nút
đang xét, nếu khóa của phần tử cần chèn lớn hơn
(nhỏ hơn) khóa của nút đang xét thì rẽ theo con
phải ( con trái) của nút đang xét. Nếu gặp Null thì
dừng, nút đang xét là cha cần tìm.
 Gắn nút mới vào cha vừa tìm được.
18.2.3 Thuật toán loại bỏ (delete)
 Nếu nút cần xóa là lá 18.3 Cây AVL
Là cây nhị phân tìm kiếm thỏa mãn tính chất AVL: chiều
cao của cây con trái và cây con phải của một gốc chỉ sai
khác nhau không quá 1 và cả cây con trái và cây con phải đều là cây AVL.
Có 4 trường hợp khôi phục tính cân bằng của cây: 17
18.3.1 Cây con trái cao hơn cây con phải do cây con Thực hiện cân bằng:
trái của con trái Thực hiện cân bằng:
18.3.3 Cây con trái co hơn cây con phải do cây con
phải của con trái
18.3.2 Cây con phải cao hơn cây con trái do cây con Thực hiện cân bằng:
phải của con phải 18
18.3.4 Cây con phải cao hơn cây con trái do cây con
trái của con phải Thực hiện cân bằng: 19