DSA09 - LINKED LIST​ 2

Homework 01​ 2
Code​ 2
Output​ 5
Homework 02​ 5
Code​ 6
Output​ 9
Homework 03​ 9
Code 3.1​ 9
Code 3.2​ 11
Homework 04​ 14
Code​ 14
Output​ 16
Homework 05​ 18
Code​ 18
Output​ 24
DSA10 - Binary Tree​ 30
Homework 01​ 30
Code​ 30
Output​ 34
Homework 02​ 35
Code​ 35
Output​ 41
Homework 03​ 41
Code​ 42
Output​ 47
DSA09 - LINKED LIST

Homework 01

Code
#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *next;
} Node;

typedef struct LinkedListType

{
Node *head;
} LinkedList;

void init(LinkedList *list)

{
list->head = NULL;
}
Node *makeNode(int data)
{
Node *node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
void insertHead(LinkedList *list, int data)
{
Node *node = makeNode(data);
node->next = list->head;
list->head = node;
}

void insert(LinkedList *list, Node *node, int pos)

{
if (list->head == NULL && pos > 1)
{
printf("List is empty\n");
return;
}
if (pos <= 0)
return;
if (pos == 1)
{
node->next = list->head;
list->head = node;
return;
}
int count = 1;
Node *curNode = list->head;
while (count + 1 < pos && curNode->next != NULL)
{
curNode = curNode->next;
count++;
}
if (count + 1 != pos)
return;
node->next = curNode->next;
curNode->next = node;
}
void printList(LinkedList *list)
{
 Node *node = list->head;
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
void deleteNode(LinkedList *list, int pos)
{
if (list->head == NULL)
{
printf("List is empty\n");
return;
}
if (pos <= 0)
return;
if (pos == 1)
{
Node *node = list->head;
list->head = node->next;
free(node);
return;
}
int count = 1;
Node *node = list->head;
while (count + 1 < pos && node->next != NULL)
{
node = node->next;
count++;
}
if (node->next == NULL)
return;
Node *temp = node->next;
node->next = temp->next;
free(temp);
}
int main()
{
LinkedList list;
init(&list);
for (int i = 7; i >= 2; i--)
{
 insertHead(&list, i);
}
printList(&list);
Node *node = makeNode(1);
printf("Insert Node at position 2nd\n");
insert(&list, node, 2);
printList(&list);
printf("Delete Node at position 2nd\n");
deleteNode(&list, 2);
printList(&list);
return 0;
}

Output
234567
Insert Node at position 2nd
2134567
Delete Node at position 2nd
234567

Homework 02
Code
#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *next;
} Node;

typedef struct LinkedListType

{
Node *head;
} LinkedList;

void init(LinkedList *list)

{
list->head = NULL;
}
Node *makeNode(int data)
{
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
void insertHead(LinkedList *list, int data)
{
Node *node = makeNode(data);
node->next = list->head;
list->head = node;
}

void insert(LinkedList *list, int value)

{
if (list == NULL)
return;

Node *node = makeNode(value);

if (list->head == NULL || value > list->head->data)

{
// Insert head
 node->next = list->head;
list->head = node;
return;
}

Node *curNode = list->head;

while (curNode->next != NULL && curNode->next->data > value)
{
curNode = curNode->next;
}

node->next = curNode->next;
curNode->next = node;
}

void printList(LinkedList *list)

{
Node *node = list->head;
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
void delete(LinkedList *list, int value)
{
if (list->head == NULL)
{
printf("List is empty\n");
return;
}
Node *node = list->head;
if (node->data == value)
{
list->head = node->next;
free(node);
return;
}
while (node->next != NULL && node->next->data < value)
{
node = node->next;
}
 if (node->next == NULL)
{
printf("Value not found\n");
return;
}
if (node->next->data == value)
{
Node *temp = node->next;
node->next = temp->next;
free(temp);
}
else
{
printf("Value not found\n");
return;
}
}
int main()
{
LinkedList list;
init(&list);
for (int i = 2; i <= 7; i++)
{
insertHead(&list, i);
}
printList(&list);
printf("Insert a node in a descending linked list\n");
insert(&list, 4);
printList(&list);
printf("Delete a node in an ascending linked list\n");
LinkedList newList;
init(&newList);
for (int i = 7; i >= 2; i--)
{
insertHead(&newList, i);
}
delete(&newList, 2);
printList(&newList);
return 0;
}
Output
765432
Insert a node in a descending linked list
7654432
Delete a node in a ascending linked list
34567

Homework 03

Code 3.1

#include <stdio.h>
#include <stdlib.h>
typedef struct NodeType
{
int data;
struct NodeType *next;
} Node;

typedef struct StackType

{
Node *top; // top as head in linked list
} Stack;
void initStack(Stack *s)
{
s->top = NULL;
}
int isEmpty(Stack *s)
{
return (s->top == NULL);
}

// insertHead = push
void push(Stack *s, int value)
{
Node *newNode = malloc(sizeof(Node));
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
}

// DeleteHead = pop
int pop(Stack *s)
{
if (isEmpty(s))
{
printf("Stack is empty\n");
return -1;
}
int value = s->top->data;
Node *nodeDel = s->top;
s->top = nodeDel->next;
free(nodeDel);
return value;
}

void printStack(Stack *s)

{
Node *node = s->top;
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}

void freeStack(Stack *s)

{
while (!isEmpty(s))
pop(s);
}
int main()
{
Stack s;
initStack(&s);

push(&s, 1);
push(&s, 2);
push(&s, 3);

printf("%d\n", pop(&s)); // 3
printf("%d\n", pop(&s)); // 2
printf("%d\n", pop(&s)); // 1
printf("%d\n", pop(&s)); // Stack empty

freeStack(&s);
return 0;
}

3
2
1
Stack is empty
-1

Code 3.2
#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *next;
} Node;
typedef struct QueueType
{
Node *head;
Node *tail;
} Queue;

void init(Queue *q)

{
q->head = NULL;
q->tail = NULL;
}
int isEmpty(Queue *q)
{
return (q->head == NULL);
}

// InsertTail = put
void put(Queue *q, int value)
{
Node *newNode = malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q))
{
q->head = newNode;
q->tail = newNode;
}
else
{
q->tail->next = newNode;
q->tail = newNode;
}
}

// DeleteHead = get
int get(Queue *q)
{
if (isEmpty(q))
{
printf("Queue is empty\n");
return -1;
}
Node *nodeDel = q->head;
 int value = nodeDel->data;
// Queue only has an element
if (q->head == q->tail)
{
q->head = NULL;
q->tail = NULL;
}
q->head = nodeDel->next;
free(nodeDel);
return value;
}

void freeQueue(Queue *q)

{
Node *node = q->head;
while (node != NULL)
{
Node *nodeDel = node;
node = node->next;
free(nodeDel);
}
}
int main()
{
Queue q;
init(&q);

put(&q, 10);
put(&q, 20);
put(&q, 30);

printf("%d\n", get(&q)); // 10
printf("%d\n", get(&q)); // 20
printf("%d\n", get(&q)); // 30
printf("%d\n", get(&q)); // Queue empty

freeQueue(&q);
return 0;
}

10
20
30
Queue is empty
-1

Homework 04

Code

#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *next;
} Node;

typedef struct LinkedListType

{
Node *head;
} LinkedList;

void init(LinkedList *list)

{
list->head = NULL;
}
Node *makeNode(int data)
{
Node *node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
void insertHead(LinkedList *list, int data)
{
Node *node = makeNode(data);
node->next = list->head;
list->head = node;
}

Node *insertAtPos(Node *head, Node *node, int pos)

{
if (pos <= 1 || head == NULL)
{
node->next = head;
return node;
}

head->next = insertAtPos(head->next, node, pos - 1);

return head;
}
void insertRecursive(LinkedList *list, Node *node, int pos)
{
if (pos <= 0)
return;
list->head = insertAtPos(list->head, node, pos);
}
void printList(LinkedList *list)
{
Node *node = list->head;
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// Rewrite recursively deleteNode
Node *deleteAtPos(Node *head, int pos)
{
 if (head == NULL || pos <= 0)
return head;

if (pos == 1)
{
Node *tmp = head;
head = head->next;
free(tmp);
return head;
}

head->next = deleteAtPos(head->next, pos - 1);

return head;
}
void deleteRecursive(LinkedList *list, int pos)
{
if (list == NULL)
return;
list->head = deleteAtPos(list->head, pos);
}
int main()
{
LinkedList list;
init(&list);
for (int i = 7; i >= 2; i--)
{
insertHead(&list, i);
}
printList(&list);
Node *node = makeNode(1);
printf("Insert Node at position 2nd\n");
insertRecursive(&list, node, 2);
printList(&list);
printf("Delete Node at position 2nd\n");
deleteRecursive(&list, 2);
printList(&list);
return 0;
}

Output
234567
Insert Node at position 2nd
2134567
Delete Node at position 2nd
234567
Phân tích theo quy trình 4 bước hàm insertRecursive():
B1:
Kiểm tra điều kiện dừng: nếu pos == 1 hoặc danh sách rỗng thì chèn node mới vào
đầu danh sách hiện tại.
B2:
Nếu chưa tới vị trí cần chèn, gọi đệ quy cho node kế tiếp với vị trí giảm đi 1 (pos - 1).
B3:
Sau khi hàm đệ quy chèn node ở danh sách con, nối lại liên kết bằng cách giữ nguyên
node hiện tại.
B4:
Cập nhật lại head của danh sách để hoàn tất thao tác chèn.

Phân tích theo quy trình 4 bước hàm deleteRecursive():

B1:
Kiểm tra điều kiện dừng: nếu danh sách rỗng hoặc pos <= 0 thì kết thúc; nếu pos == 1
thì xóa node đầu danh sách.
B2:
Nếu chưa tới vị trí cần xóa, gọi đệ quy cho node kế tiếp với vị trí giảm đi 1 (pos - 1).
B3:
Sau khi node ở danh sách con bị xóa, nối lại liên kết để giữ nguyên cấu trúc danh
sách.
B4:
Cập nhật lại head của danh sách để hoàn tất thao tác xóa.
Homework 05

Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FLOOR 17
#define ROOM 12
typedef struct RoomAddress
{
int floor;
int room;
} Address;

typedef struct Customer

{
char firstName;
Address address;
struct Customer *next;
} Customer;

typedef struct Group

{
Customer *head;
int size;
} Group;
void printHotel(int hotel[][12])
{
for (int f = 0; f < 17; f++)
{
for (int r = 0; r < 12; r++)
{
printf("%d ", hotel[f][r]);
}
printf("\n");
}
}

void initGroup(Group *group)

{
group->head = NULL;
group->size = 0;
}

Customer *makeCustomer(int hotel[][12], int floor)

{
Customer *customer = malloc(sizeof(Customer));
printf("First name: ");
scanf(" %c", &customer->firstName);
customer->[Link] = floor;
int room;
 do
{
room = rand() % 12;
} while (hotel[floor][room] == 1);
customer->[Link] = room;
hotel[floor][room] = 1;
customer->next = NULL;
return customer;
}
void randomAssign(Group *group, int hotel[][12])
{
int grSize;
printf("Get the number of people in the group: ");
scanf("%d", &grSize);
group->size = grSize;
Customer *head = makeCustomer(hotel, 0);
group->head = head;
Customer *curCus = group->head;
for (int i = 1; i < grSize; i++)
{

Customer *newCus = makeCustomer(hotel, 1 + rand() % 16);

curCus->next = newCus;
curCus = newCus;
}
printf("Complete the group\n");
}

void printGroup(Group group)

{
Customer *node = [Link];
while (node != NULL)
{
printf("First name: %c at ", node->firstName);
printf("Address: P%d.%d\n", node->[Link],
node->[Link]);
node = node->next;
}
}

void deleteCustomer(Group *group, int floor, int room)

{
if (group == NULL || group->head == NULL)
 return;
if (group->head->next == NULL && group->head->[Link] ==
floor && group->head->[Link] == room)
{
group->head = NULL;
return;
}
Customer *curNode = group->head;
Customer *prev = NULL;
while (curNode != NULL)
{
if (curNode->[Link] == floor && curNode->[Link] ==
room)
{
if (prev == NULL)
{
group->head = curNode->next;
}
else
prev->next = curNode->next;
free(curNode);
group->size--;
return;
}
prev = curNode;
curNode = curNode->next;
}
}

void checkOut(Group *group, int hotel[][12])

{
if (group == NULL)
return;
Customer *curNode = group->head;
while (curNode != NULL)
{
Customer *next = curNode->next;
int floor = curNode->[Link];
int room = curNode->[Link];
hotel[floor][room] = 0;
free(curNode);
curNode = next;
}
 group->head = NULL;
group->size = 0;
}
int main()
{
time_t t;
srand((unsigned)time(&t));
int hotel[FLOOR][ROOM] = {
// Tầng 0
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
// Tầng 1
{0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1},
// Tầng 2
{0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0},
// Tầng 3
{1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1},
// Tầng 4
{0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0},
// Tầng 5
{1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1},
// Tầng 6
{1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0},
// Tầng 7
{0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1},
// Tầng 8
{0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1},
// Tầng 9
{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1},
// Tầng 10
{0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0},
// Tầng 11
{1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1},
// Tầng 12
{1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0},
// Tầng 13
{0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1},
// Tầng 14
{0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0},
// Tầng 15
{1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
// Tầng 16
{0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}};
 printHotel(hotel);
printf("Enter the number of groups: ");
int size;
scanf("%d", &size);
Group group[size];
for (int i = 0; i < size; i++)
{
// Problem 1: Assign rooms to each group to fully occupy the
hotel; header must be at the 0th floor
initGroup(&group[i]);
randomAssign(&group[i], hotel);
printGroup(group[i]);
}

// Problem 2: Enter header's address -> printGroup

printf("Enter the header's room: ");
int headerRoom;
scanf("%d", &headerRoom);
for (int i = 0; i < size; i++)
{
if (group[i].head->[Link] == headerRoom)
{
printGroup(group[i]);
}
}
// Problem 3: Insert new customer to a particular group assuming
there are customer not from group check out
printf("Enter the address of customer checked out: ");
int floor, room;
scanf("%d %d", &floor, &room);
hotel[floor][room] = 0;
printf("Enter information for customer in group: ");
int groupID;
scanf("%d", &groupID);
// Insert tail
Customer *newCustomer = (Customer *)malloc(sizeof(Customer));
newCustomer->[Link] = floor;
newCustomer->[Link] = room;
newCustomer->next = NULL;
Customer *node = group[groupID].head;
while (node->next != NULL)
{
node = node->next;
 }
node->next = newCustomer;
printGroup(group[groupID]);

// Problem 4: Delete customer from a particular group

printf("Enter the group ID: ");
scanf("%d", &groupID);
printf("Enter the address of customer to be deleted: ");
scanf("%d %d", &floor, &room);
hotel[floor][room] = 0;
deleteCustomer(&group[groupID], floor, room);
printGroup(group[groupID]);

// Problem 5: Check out all customers from a particular group

printf("Enter the group ID: ");
scanf("%d", &groupID);
checkOut(&group[groupID], hotel);
printHotel(hotel);
return 0;
}

Output:
000000000011
001100100111
010011010010
101000101011
001101000100
111010110011
100100101100
001001010011
010000101101
000100001101
001010100010
100101001001
101000101010
000100001101
001010100010
100001001001
010010010010
Enter the number of groups: 2
Get the number of people in the group: 12
First name: A B S E F J K L S W Q A
First name: First name: First name: First name: First name: First name: First name:
First name: First name: First name: First name: Complete the group
First name: A at Address: P0.3
First name: B at Address: P11.1
First name: S at Address: P2.6
First name: E at Address: P13.7
First name: F at Address: P14.0
First name: J at Address: P15.7
First name: K at Address: P11.10
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Get the number of people in the group: 10
First name: T M K L J S A Q C S
First name: First name: First name: First name: First name: First name: First name:
First name: First name: Complete the group
First name: T at Address: P0.7
First name: M at Address: P11.7
First name: K at Address: P5.5
First name: L at Address: P3.9
First name: J at Address: P4.0
First name: S at Address: P7.9
First name: A at Address: P12.11
First name: Q at Address: P1.4
First name: C at Address: P5.3
First name: S at Address: P10.9
Enter the header's room: 3
First name: A at Address: P0.3
First name: B at Address: P11.1
First name: S at Address: P2.6
First name: E at Address: P13.7
First name: F at Address: P14.0
First name: J at Address: P15.7
First name: K at Address: P11.10
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Enter the address of customer checked out: 1 2
Enter information for customer in group: 1
First name: O
First name: C at Address: P5.3
First name: S at Address: P10.9
Enter the header's room: 3
First name: A at Address: P0.3
First name: B at Address: P11.1
First name: S at Address: P2.6
First name: E at Address: P13.7
First name: F at Address: P14.0
First name: J at Address: P15.7
First name: K at Address: P11.10
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Enter the address of customer checked out: 1 2
Enter information for customer in group: 1
First name: O
First name: E at Address: P13.7
First name: F at Address: P14.0
First name: J at Address: P15.7
First name: K at Address: P11.10
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Enter the address of customer checked out: 1 2
Enter information for customer in group: 1
First name: O
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Enter the address of customer checked out: 1 2
Enter information for customer in group: 1
First name: O
First name: A at Address: P13.2
Enter the address of customer checked out: 1 2
Enter information for customer in group: 1
First name: O
Enter information for customer in group: 1
First name: O
First name: O
First name: T at Address: P0.7
First name: M at Address: P11.7
First name: K at Address: P5.5
First name: L at Address: P3.9
First name: J at Address: P4.0
First name: S at Address: P7.9
First name: A at Address: P12.11
First name: Q at Address: P1.4
First name: C at Address: P5.3
First name: S at Address: P10.9
First name: O at Address: P2.3
Enter the group ID:

First name: T at Address: P0.7

First name: M at Address: P11.7
First name: K at Address: P5.5
First name: L at Address: P3.9
First name: J at Address: P4.0
First name: S at Address: P7.9
First name: A at Address: P12.11
First name: Q at Address: P1.4
First name: C at Address: P5.3
First name: S at Address: P10.9
First name: O at Address: P2.3
First name: T at Address: P0.7
First name: M at Address: P11.7
First name: K at Address: P5.5
First name: L at Address: P3.9
First name: J at Address: P4.0
First name: T at Address: P0.7
First name: M at Address: P11.7
First name: K at Address: P5.5
First name: T at Address: P0.7
First name: T at Address: P0.7
First name: M at Address: P11.7
First name: K at Address: P5.5
First name: L at Address: P3.9
First name: J at Address: P4.0
First name: S at Address: P7.9
First name: A at Address: P12.11
First name: Q at Address: P1.4
First name: C at Address: P5.3
First name: S at Address: P10.9
First name: O at Address: P2.3
Enter the group ID: 0
Enter the address of customer to be deleted: 2 6
First name: A at Address: P0.3
First name: B at Address: P11.1
First name: E at Address: P13.7
First name: F at Address: P14.0
First name: J at Address: P15.7
First name: K at Address: P11.10
First name: L at Address: P1.7
First name: S at Address: P2.9
First name: W at Address: P7.4
First name: Q at Address: P13.1
First name: A at Address: P13.2
Enter the group ID: 1
000100000011
000100110111
010011010110
101000101011
001101000100
111010110011
100100101100
001011010011
010000101101
000100001101
001010100010
110101001011
101000101010
011100011101
101010100010
100001011001
010010010010
DSA10 - Binary Tree

Homework 01

Code
#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *left, *right;
} TreeNode;

typedef struct BinaryTreeType

{
struct NodeType *root;
} BinaryTree;

void init(BinaryTree *tree)

{
tree->root = NULL;
}
TreeNode *makeNode(int data)
{
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
void insert(BinaryTree *tree, int data)
{
if (tree->root == NULL)
{
tree->root = makeNode(data);
return;
}
TreeNode *curNode = tree->root;
while (curNode != NULL)
{
if (data < curNode->data)
{
if (curNode->left == NULL)
{
curNode->left = makeNode(data);
return;
}
else
 curNode = curNode->left;
}
else
{
if (curNode->right == NULL)
{
curNode->right = makeNode(data);
return;
}
else
curNode = curNode->right;
}
}
}
void printTree(TreeNode *node)
{
if (node == NULL)
return;
printTree(node->left);
printf("%d ", node->data);
printTree(node->right);
}

int main()
{
printf("Build tree 1.1\n");
TreeNode *nodes[16];
for (int i = 1; i <= 15; i++)
{
nodes[i] = makeNode(i);
}
BinaryTree tree;
init(&tree);
[Link] = nodes[1];
for (int i = 1; i <= 7; i++)
{
nodes[i]->left = nodes[i * 2];
nodes[i]->right = nodes[i * 2 + 1];
}
printTree([Link]);

printf("\nBuild tree 1.2\n");

BinaryTree tree2;
init(&tree2);
TreeNode *nodes2[12];
int arr2[] = {50, 17, 76, 9, 23, 54, 14, 19, 72, 12, 67};
for (int i = 1; i <= 11; i++)
{
nodes2[i] = makeNode(arr2[i - 1]);
}
[Link] = nodes2[1];
nodes2[1]->left = nodes2[2];
nodes2[1]->right = nodes2[3];

nodes2[2]->left = nodes2[4];
nodes2[2]->right = nodes2[5];

nodes2[3]->left = nodes2[6];

nodes2[4]->right = nodes2[7];
nodes2[5]->left = nodes2[8];
nodes2[6]->right = nodes2[9];

nodes2[7]->left = nodes2[10];
nodes2[9]->left = nodes2[11];

printTree([Link]);

printf("\nBuild tree 1.3\n");

BinaryTree tree3;
init(&tree3);
int arr[] = {15, 11, 26, 8, 12, 20, 30, 6, 9, 14, 35};
TreeNode *nodes3[12];
for (int i = 0; i < 11; i++)
{
insert(&tree3, arr[i]);
}
printTree([Link]);

printf("\nBuild tree 1.4\n");

BinaryTree tree4;
init(&tree4);
int arr4[] = {3, 1, 10, 13, 5, 11, 16, 6, 15, 2, 9, 4};
TreeNode *nodes4[13];
for (int i = 0; i < 12; i++)
 {
nodes4[i + 1] = makeNode(arr4[i]);
}
[Link] = nodes4[1];
nodes4[1]->left = nodes4[2];
nodes4[1]->right = nodes4[3];

nodes4[2]->left = nodes4[4];
nodes4[2]->right = nodes4[5];

nodes4[3]->left = nodes4[6];
nodes4[3]->right = nodes4[7];

nodes4[5]->left = nodes4[8];

nodes4[7]->left = nodes4[9];
nodes4[7]->right = nodes4[10];

nodes4[9]->left = nodes4[11];
nodes4[9]->right = nodes4[12];

printTree([Link]);
return 0;
}

Output
Build tree 1.1
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
Build tree 1.2
9 12 14 17 19 23 50 54 67 72 76
Build tree 1.3
6 8 9 11 12 14 15 20 26 30 35
Build tree 1.4
13 1 6 5 3 11 10 9 15 4 16 2
Homework 02

Code
#include <stdio.h>
#include <stdlib.h>

typedef struct NodeType

{
int data;
struct NodeType *left, *right;
} TreeNode;

typedef struct BinaryTreeType

{
struct NodeType *root;
} BinaryTree;

void init(BinaryTree *tree)

{
tree->root = NULL;
}
TreeNode *makeNode(int data)
{
TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
newNode->data = data;
newNode->left = NULL;
 newNode->right = NULL;
return newNode;
}
// Build tree 1.4
void insertRandom(BinaryTree *tree)
{
tree->root = makeNode(3);
TreeNode *root = tree->root;
TreeNode *n2 = makeNode(1);
root->left = n2;
TreeNode *n3 = makeNode(10);
root->right = n3;
TreeNode *n4 = makeNode(13);
n2->left = n4;
TreeNode *n5 = makeNode(5);
n2->right = n5;
TreeNode *n6 = makeNode(11);
n3->left = n6;
TreeNode *n7 = makeNode(16);
n3->right = n7;
TreeNode *n8 = makeNode(6);
n5->left = n8;

TreeNode *n9 = makeNode(15);

n7->left = n9;
TreeNode *n10 = makeNode(2);
n7->right = n10;
TreeNode *n11 = makeNode(9);
n9->left = n11;
TreeNode *n12 = makeNode(4);
n9->right = n12;
}
// Build tree 1.1
void insertArray(BinaryTree *tree)
{
TreeNode *node[16];
for (int i = 1; i <= 15; i++)
{
node[i] = makeNode(i);
}
tree->root = node[1];
for (int i = 1; i <= 15; i++)
{
 if (2 * i <= 15)
{
node[i]->left = node[2 * i];
}
if (2 * i + 1 <= 15)
{
node[i]->right = node[2 * i + 1];
}
}
}

void insertBST(BinaryTree *tree, int value)

{

if (tree->root == NULL)
{
tree->root = makeNode(value);
return;
}
TreeNode *curNode = tree->root;
while (curNode)
{
if (value < curNode->data)
{
if (curNode->left == NULL)
{
curNode->left = makeNode(value);
return;
}
curNode = curNode->left;
}
if (value > curNode->data)
{
if (curNode->right == NULL)
{
curNode->right = makeNode(value);
return;
}
curNode = curNode->right;
}
}
}
void printTree(TreeNode *root)
{
if (root == NULL)
return;
printTree(root->left);
printf("%d ", root->data);
printTree(root->right);
}
TreeNode *findNode(TreeNode *root, int value)
{
if (root == NULL)
return NULL;
if (root->data == value)
return root;
return findNode(root->left, value) || findNode(root->right, value);
}

// Delete node-> data = 12

int isLeaf(TreeNode *node)
{
return node->left == NULL && node->right == NULL;
}
void delete(TreeNode *prevNode, TreeNode *curNode, int value)
{
if (curNode == NULL)
return; // Not found node to delete
if (value < curNode->data)
delete(curNode, curNode->left, value);
else if (value > curNode->data)
delete(curNode, curNode->right, value);
else
{
// Found at curNode
// Case 1: Leaf node
if (isLeaf(curNode))
{
if (prevNode->left == curNode)
prevNode->left = NULL;
else
prevNode->right = NULL;
free(curNode);
return;
}
// Case 2: Node has a child
 // Left child
if (curNode->left != NULL && curNode->right == NULL)
{
if (prevNode->left == curNode)
prevNode->left = curNode->left;
else
prevNode->right = curNode->left;
free(curNode);
return;
}
// Right child
if (curNode->left == NULL && curNode->right != NULL)
{
if (prevNode->left == curNode)
prevNode->left = curNode->right;
else
prevNode->right = curNode->right;
free(curNode);
return;
}

// Case 3: Node has 2 children

TreeNode *minNode = curNode->right;
TreeNode *parentNode = curNode;
while (minNode->left != NULL)
{
parentNode = minNode;
minNode = minNode->left;
}
curNode->data = minNode->data;
delete(parentNode, minNode, minNode->data);
}
}

void findLevel3(TreeNode *node, int level)

{
if (node == NULL)
return;
if (level == 3)
printf("%d ", node->data);
findLevel3(node->left, level + 1);
findLevel3(node->right, level + 1);
}
int main()
{
TreeNode *root = NULL;
int choice;
BinaryTree tree;
init(&tree);
printf("Enter the case to test (1-4): ");
scanf("%d", &choice);
switch (choice)
{
case 1:
{
insertArray(&tree);
break;
}
case 2:
{
int arr[] = {50, 17, 76, 9, 23, 54, 14, 19, 72, 12, 67};
for (int i = 0; i < 11; i++)
{
insertBST(&tree, arr[i]);
}
break;
}
case 3:
{
int arr[] = {15, 11, 26, 8, 12, 20, 30, 6, 9, 14, 35};
for (int i = 0; i < 11; i++)
{
insertBST(&tree, arr[i]);
}
break;
}
case 4:
{
insertRandom(&tree);
break;
}
default:
printf("Invalid choice\n");
break;
}
 printTree([Link]);
if (findNode([Link], 10))
printf("\nFound");
else
printf("\nNot found");

printf("\nDelete 12\n");
delete([Link], [Link], 12);
printTree([Link]);

printf("\nLevel 3: ");
findLevel3([Link], 0);
return 0;
}

Output
Enter the case to test (1-4): 1
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
Found
Delete 12
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
Level 3: 8 9 10 11 12 13 14 15

Homework 03
Code
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct NodeType
{
int data;
struct NodeType *left, *right;
} TreeNode;

typedef struct BinaryTreeType

{
struct NodeType *root;
} BinaryTree;

void init(BinaryTree *tree)

{
tree->root = NULL;
}
typedef struct QueueNode
{
TreeNode *node;
int depth;
} QNode;
typedef struct QueueType
{
QNode arr[100];
int head, tail;
} Queue;

void initQueue(Queue *q)

{
q->head = 0;
q->tail = -1;
}

void put(Queue *q, TreeNode *node, int depth)

{
q->arr[++q->tail].node = node;
q->arr[q->tail].depth = depth;
}
QNode get(Queue *q)
{
 return q->arr[q->head++];
}

int isLeaf(TreeNode *node)

{
return (node->left == NULL && node->right == NULL);
}
// Đếm số lượng phần tử tại nhánh từ root đến leaf (đường đi từ root
đến leaf) có số phần tử ít nhất trong tất cả các nhánh
int countMinNode(TreeNode *root)
{
if (root == NULL)
return 0;
Queue q;
initQueue(&q);

put(&q, root, 1);

while ([Link] <= [Link])

{
QNode node = get(&q);
if (isLeaf([Link]))
return [Link];

if ([Link]->left != NULL)
put(&q, [Link]->left, [Link] + 1);
if ([Link]->right != NULL)
put(&q, [Link]->right, [Link] + 1);
}
return 0;
}
void printTree(TreeNode *node)
{
if (node == NULL)
return;
printTree(node->left);
printf("%d ", node->data);
printTree(node->right);
}
TreeNode *makeNode(int data)
{
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
 node->left = node->right = NULL;
return node;
}
// 3.2 Cho biết level nào trong cây có số phần tử nhiều nhất
int maxLevel(TreeNode *root)
{
if (root == NULL)
return -1;
Queue q;
initQueue(&q);

int maxCount = 0;
int maxLevel = 0;
int level = 0;

put(&q, root, 0);

while ([Link] <= [Link])
{
int count = [Link] - [Link] + 1;
if (maxCount < count)
{
maxCount = count;
maxLevel = level;
}
for (int i = 0; i < count; i++)
{
TreeNode *node = get(&q).node;
if (node->left != NULL)
[Link][++[Link]].node = node->left;
if (node->right != NULL)
[Link][++[Link]].node = node->right;
}
level++;
}
return maxLevel;
}
// Prob 3.3. Tính tổng các node mà chỉ có node con
int isChild(TreeNode *node)
{
if (node->left == NULL && node->right != NULL)
return 1;
if (node->left != NULL && node->right == NULL)
return 1;
 return 0;
}
int calChildNode(TreeNode *root)
{
if (root == NULL)
return 0;
int sum = 0;
if (isChild(root))
sum += root->data;
return sum + calChildNode(root->left) + calChildNode(root->right);
}
// Probs 3.4 Tìm hiệu của giá trị tìm được ở câu 3.3 trừ đi tổng các
giá trị của các node chỉ có một node con bên trái
int isOnlyLeftChild(TreeNode *node)
{
if (node == NULL)
return 0;
return node->left != NULL && node->right == NULL;
}
int calOnlyLeftChildNode(TreeNode *root)
{
if (root == NULL)
return 0;
int sum = 0;
if (isOnlyLeftChild(root))
sum += root->data;
return sum + calOnlyLeftChildNode(root->left) +
calOnlyLeftChildNode(root->right);
}

// Probs 3.5 Cho biết node gần giá trị hiệu này nhất
void findAdjacentNode(TreeNode *root, int value, int *maxLength)
{
if (root == NULL)
return;
if (abs(value - root->data) > *maxLength)
{
*maxLength = abs(value - root->data);
}
findAdjacentNode(root->left, value, maxLength);
findAdjacentNode(root->right, value, maxLength);
}
int main()
{
BinaryTree tree;
init(&tree);
TreeNode *nodes2[12];
int arr2[] = {50, 17, 76, 9, 23, 54, 14, 19, 72, 12, 67};
for (int i = 1; i <= 11; i++)
{
nodes2[i] = makeNode(arr2[i - 1]);
}
[Link] = nodes2[1];
nodes2[1]->left = nodes2[2];
nodes2[1]->right = nodes2[3];

nodes2[2]->left = nodes2[4];
nodes2[2]->right = nodes2[5];

nodes2[3]->left = nodes2[6];

nodes2[4]->right = nodes2[7];
nodes2[5]->left = nodes2[8];
nodes2[6]->right = nodes2[9];

nodes2[7]->left = nodes2[10];
nodes2[9]->left = nodes2[11];

printTree([Link]);
printf("\nSmallest number of nodes: %d", countMinNode([Link]));
printf("\nMax level: %d", maxLevel([Link]));
printf("\nSum of child node: %d", calChildNode([Link]));
int value = calChildNode([Link]) -
calOnlyLeftChildNode([Link]);
printf("\nOutput 3.4: %d", value);
int maxLength = 0;
findAdjacentNode([Link], value, &maxLength);
printf("\nOutput 3.5: %d", maxLength);
return 0;
}
Output
9 12 14 17 19 23 50 54 67 72 76
Smallest number of nodes: 4
Max level: 2
Sum of child node: 248
Output 3.4: 63
Output 3.5: 54