Show Menu
Cheatography

Data Structes 2 Cheat Sheet by

Continuation of data structures 1

Binary Trees

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 = (TreeN­ode*) 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);
}}

Stack Trees

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.

Hash Tables

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

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;
}
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          C Reference Cheat Sheet
          C program Cheat Sheet

          More Cheat Sheets by alicanpayasli

          Data Structes 1 Cheat Sheet