Data Structes 2 Cheat Sheet

Tree data structure a hierar­chical data model in which data is linked together to form a repres­ent­ative tree.
Binary Trees are a type of tree where each node can have at most two children.
Binary Trees Example Code:
typedef struct TreeNode {
int data;
struct TreeNode left;
struct TreeNode right;
} TreeNode;

TreeNode create­Nod­e(int x) {
TreeNode* t = (TreeNode) malloc­(si­zeo­f(T­ree­Node));
t->data = x;
t->left = NULL;
t->­right = NULL;
return t;
}

void printT­ree­(Tr­eeNode root) {
if(root != NULL) {
printf(“%d “, root->­data);
printT­ree­(ro­ot-­>left);
printT­ree­(ro­ot-­>ri­ght);
}}

int main(void) {
TreeNode root = create­Nod­e(5);
root->left = create­Nod­e(6);
root->­right = create­Nod­e(8);
printT­ree­(root);
getch();

Methods for navigating binary trees:
Preorder: Root-L­eft­-Right
Inorder: Left-R­oot­-Right
Postorder: Left-R­igh­t-Root

Methods for navigating Example Code:
void preord­er(­Tre­eNode root) {
if(root != NULL) {
printf(“%d “, root->­data);
preord­er(­roo­t->­left);
preord­er(­roo­t->­right);
}}

void inorde­r(T­reeNode root) {
if(root != NULL) {
inorde­r(r­oot­->l­eft);
printf(“%d “, root->­data);
inorde­r(r­oot­->r­ight);
}}

void postor­der­(Tr­eeNode *root) {
if(root != NULL) {
postor­der­(ro­ot-­>left);
postor­der­(ro­ot-­>ri­ght);
printf(“%d “, root->­data);
}}

A stack tree is a data structure that allows to quickly find the smallest element in a data set. In this data structure, finding the smallest element, deleting the smallest element and adding elements to the tree can be done quickly.A binary tree that satisfies the following two properties is classified as a chunk tree data structure:
1. Tree integrity: All levels of the tree, except the last level, must be complete in terms of the nodes they contain. The nodes in the last level of the tree must also be full from left to right.
2. Heap property: The value of a node must be less than or equal to the values of its children.

It is a data structure that stores data in the form of a key and data pair, allowing insertion, deletion and search operations to be performed very quickly. The general working logic is to store data in an N dimens­ional array and use a key consisting of a number or string to access the data. For a data to be stored, a key value is sent to the hash function, the value calculated by the function becomes the index where the data will be stored in the array.
Example of a hash function that takes a numeric value as the key:
int hash(int key, int N) {
return key % N;
}
Example of a hash function that takes a string value as the key:
int hash(char key[], int M, int N) {
int i, sum = 0;
for(i=0; i<M; i++) {
sum += key[i];
}
return sum % N;
}

Binary search trees are a special type of binary tree. In this data structure, in addition to the binary tree proper­ties, there is a size-m­inority relati­onship between the data in the nodes.
In order for a tree with binary tree properties to be a binary search tree, each node in the tree node must be greater than all values in its left subtree and less than or equal to all values in its right subtree.
Binary search tree structure and node insertion function example:
typedef struct TreeNode {
int data;
struct TreeNode left;
struct TreeNode right;
} TreeNode;

TreeNode* insert­Nod­e(T­reeNode node, int x) {
if(node == NULL) {
TreeNode *t = (TreeNode ) malloc­(si­zeo­f(T­ree­Node));
t -> data = x;
t -> left = t -> right = NULL;
return t;
}
else if(x > node->­data) {
node->­right = insert­Nod­e(n­ode­->r­ight, x);
}
else {
node->left = insert­Nod­e(n­ode­->left, x);
}}

Example of node extraction function from binary search tree:
typedef struct TreeNode {
int data;
struct TreeNode left;
struct TreeNode right;
} TreeNode;

TreeNode* findMi­n(T­reeNode node) {
if(node == NULL)
return NULL;
if(nod­e->­left)
return findMi­n(n­ode­->l­eft);
else
return node;
}

TreeNode* insert­Nod­e(T­reeNode node, int x) {
if(node == NULL) {
TreeNode *t = (TreeNode ) malloc­(si­zeo­f(T­ree­Node));
t -> data = x;
t -> left = t -> right = NULL;
return t;
}
else if(x > node->­data) {
node->­right = insert­Nod­e(n­ode­->r­ight, x);
}
else {
node->left = insert­Nod­e(n­ode­->left, x);
}}

TreeNode* delete­Nod­e(T­reeNode node, int x) {
TreeNode *temp;

if(node == NULL) {
printf(“No node found to delete.\n”);
}
else if(x < node->­data) {
node->left = delete­Nod­e(n­ode­->left, x);
}
else if(x > node->­data) {
node->­right = delete­Nod­e(n­ode­->r­ight, x);
}
else {
if(nod­e->­right && node->­left) {
temp = findMi­n(n­ode­->r­ight);
node -> data = temp->­data;
node -> right = delete­Nod­e(n­ode­->r­ight, temp->­data);
}
else {
temp = node;
if(nod­e->left == NULL)
node = node->­right;
else if(nod­e->­right == NULL)
node = node->­left;
free(t­emp);
}}

return node;
}