Sukhyun Hong Notes on Binary Trees / April 25
typedef struct TreeNode_t {
int value;
struct TreeNode_t *left, *right;
}TreeNode;
TreeNode *TreeNode_create(int value) {
TreeNode *node = malloc(sizeof(TreeNode)); node->value = value; node->left = NULL; node->right = NULL; return node;
}
TreeNode *Tree_insert(TreeNode *node, int value) {
if (node == NULL) return TreeNode_create(value);
if (node->value >= value)
node->left = Tree_insert(node->left, value);
else
node->right = Tree_insert(node->right, value);
return node;
}
void Tree_inorder(TreeNode *node) {
if (node == NULL) return;
Tree_inoder(node->left);
printf("%d\", node->value);
Tree_inorder(node->right);
}
void Tree_destroy(TreeNode *node) {
if (node == NULL) return;
Tree_destroy(node->left);
Tree_destroy(node->right);
fere(node);
}
int main(int argc, char *argv[]) {
if (argc != 3){
return EXIT_FAILURE;
}
FILE *f = fopen(argv[1], "r");
if (f == NULL){
return EXIT_FAILURE;
}
int num;
TreeNode *root = NULL;
while (fscanf(f, "%d\n", &num) == 1){
root = Tree_insert(root, num);
}
fclose(f);
Tree_inorder(root);
return EXIT_SUCCESS;
}
Hanye Xu April 20 Lecture 27
264 exam
outcome 1.file
2.structure
3.dynamic structure (linked list)
binary search tree
typedef struct treenode { struct treenode *left; struct treenode *right; int value; }Node;
int Tree_search(Node *n, int v) { /*return 0 if not found,1 if found*/ if(n == NULL){return 0;} if((n->value)==v){return 1;} if((n->value)>v) { return Tree_search(n->left,v); } return Tree_search(n->right,v); }
void Tree_destroy(Node *n) { if(n == NULL){return;} Tree_destroy(n->left); Tree_destroy(n->right); free(n); }
void Tree_print(Node *n) { if(n==NULL){return;} (1)printf("%d",n->value); 1 2 3 -> preorder 6 2 0 4 9 7 (2)Tree_print(n->left); 2 1 3 -> inorder sorting 0 2 4 6 7 9 (3)Tree_print(n->right); 2 3 1 -> postorder 0 4 2 7 9 6 }
Node *Node_construct(int v) { Node *n; n = malloc(sizeof(Node)); n->value = v; n->left = NULL; n->right = NULL; return n; }
Node *Tree_construct(Node *n, int v) { if(n==NULL){return Node_construct(v);} if((n->value)==v){return n;} if((n->value)>v) { n->left = Node_construct(n->left,v); } else { n->right= Node_construct(n->right,v); } return n; }
insert 6,2,4,0,9,7
Node *n =NULL;
n=Tree_insert(n,6);
n-> 6 (root) / \
GRD
n=Tree_insert(n,2);
n-> 6 / \ 2 GRD
/ \
GRD
n=Tree_insert(n,4)
n-> 6
/ \
2 GRD
/ \
GRD 4 / \ GRD
Finally n-> 6
/ \
2 9
/ \ / \
0 4 7 GRD
parser
int y = 3+2; int t = 3 + "ece";
Contents
James Chen Notes
Binary search tree
A binary search tree has an initial root and left and right subtrees. Each subtree starts with a node and has left and right children It is possible that the left or right may be NULL if a node has a value v: everything in the left subtree < v everything in the right subtree > v
notes: insert 6, 2, 4 Node *n = NULL;
n=Tree_insert(n, 6);//creates root of 6, its left and right subtrees are NULL
n=Tree_insert(n, 2);
//creates node with value 2, since it is < 6 and the left child of 6 is NULL, 2 becomes the left child
n=Tree_insert(n,4);
//value 4, it is <6 but, the left child is not NULL, the insert function is called using the left child (2). Since 4 > 2, and the right child of 2 is NULL, 4 becomes the right child
each search checks value against node value, and moves left and right as appropriate
binary search tree works best when balanced
typedef struct treenode
{
struct treenode *left;
struct treenode *right;
int value;
}Node;
int Tree_search(Node* n, int v) // or Node* Tree_search, returns n or NULL
{
/*return 0 if not found, 1 if found */
if (n==NULL) {return 0;}
if ((n->value) == v) {return 1;}
if ((n->value) > v)
{
return Tree_search(n->left,v);
}
return Tree_search(n->right,v);
}
void Tree_destroy(Node *n)
{
if(n==NULL)
{return;}
Tree_destroy(n->left); // destroy left child
Tree_destroy(n->right); // destroy right child
free(n); // destroy itself
}
void Tree_print(Node *n) // prints least to greatest
{
if(n==NULL)
{return;}
printf(“%d”,n->value); // (1)
Tree_print(n->left);// (2)
Tree_print(n->right);// (3) }
/*
sample tree;
6 2 9 0 4 7
1, 2, 3 → preorder
2, 1, 3 → in order // prints tree in order of least to greatest ( 0 2 4 6 7 9 )
3, 1, 2 → for greatest to least ( 9 7 6 4 2 0 )
2, 3, 1 → post order (hierarchy operation; like PEMDAS)
parser → the very first thing a compiler does. Analyze source code, breaks into smaller units, decides if the units can be put together
- /
Node* Node_construct(int v)
{
Node *n;
n=malloc(sizeof(Node));
n->value = v;
n->left = NULL;
n->right = NULL;
return n; }
Node *Tree_construct(Node *n, int v) {
if(n==NULL)
{
return Node_construct(v);}
}
if((n->value) == v)
{
return n;
}
if((n->value)>n)
{
n->left = Node_construct(n->left,n);
}
else
{
n->right = Node_construct(n->right, v);
}
return n;
}
===================
Kevin Tan(0023987592), section#2 notes 04/19
binary search tree
typedef struct treenode {
struct treenode *left; struct treenode *right; int value;
}Node;
int tree_search(Node *n, int v) {
if (n == NULL) {
return 0;
}
if ((n->value == v)) {
return 1;
}
if (n->value>v) {
return tree_search(n->left, v);
}
return tree_search(n->right, v);
}
void tree_destory(Node *n) {
if (n==NULL) {
return;
}
tree_destory(n->left);
tree_destory(n->right);
free(n);
}
void tree_print(Node *n) {
if(n==NULL){return 1;}
printf("%d",n->value);
tree_print(n->left);
tree_print(n->right);
}
Node* Node_construct(int v) {
Node *n; n=malloc(sizeof(Node)); n->value = v; n->left = NULL; n->right = NULL; return n; }
Node *Tree_construct(Node *n, int v) {
if(n==NULL)
{
return Node_construct(v);}
} if((n->value) == v) {
return n;
} if((n->value)>n) {
n->left = Node_construct(n->left,n);
} else {
n->right = Node_construct(n->right, v);
} return n; }
___________________________________________
Shiyu Wang Lec27 April 22nd
binary search tree typedef struct tree node {
struct tree node*left; struct tree node*right; int value;
}Node;
Node * tree_search(Node *n, int v)
{
/*return 0 if not found,1 if found */
if (n==NULL)
{
return NULL;
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
return tree_search(n->left, v);
}
return tree_search(n->right,v);
}
Void tree_destory(Node*n) {
if(n==NULL)
{
return n;
}
tree_destory(n->left);
tree_destory(n->right);
free(n);
}
Void Tree_print(node*n) {
if(n== NULL)
{
return ;
}
printf("%d", n->value);
Tree_print(n->left);
Tree_print(n->right);
}
Node *node_construct(int v) {
Node *n; n=malloc(sizeof(Node)); n->value=v; n->left=NULL; n->right = NULL; return n;
}
Node *Tree_construct(Node *n, int v) {
if(n==NULL)
{
return Node_construct(v);
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
n->left=Node_construct(tree->left,v);
}
else
{
n->right=Node_construct(tree->right, v);
}
return n;
}
=============================
Wudi Zhou Lecture 27, Prof Lu's section, April 23
Topic: Binary search tree.
typedef struct tree node {
struct treenode * left; struct treenode * right; int value;
}Node;
Node * tree_search(Node *n, int v)
{ /*return 0 if not found,1 if found */
if (n == NULL)
{
return NULL;
}
if((n -> value)== v)
{
return n;
}
if((n -> value)> v)
{
return tree_search(n -> left, v);
}
return tree_search(n -> right, v);
}
void tree_destory(Node*n) {
if(n == NULL)
{
return n;
}
tree_destory(n -> left);
tree_destory(n -> right);
free(n);
}
void Tree_print(node*n) {
if( n== NULL)
{
return ;
}
printf("%d", n->value);
Tree_print(n->left);
Tree_print(n->right);
}
Node *node_construct(int v) {
Node *n; n=malloc(sizeof(Node)); n->value=v; n->left=NULL; n->right = NULL; return n;
}
Node *Tree_construct(Node *n, int v) {
if(n==NULL)
{
return Node_construct(v);
}
if((n->value)==v)
{
return n;
}
if((n->value)>v)
{
n->left=Node_construct(tree -> left,v);
}
else
{
n->right=Node_construct(tree -> right, v);
}
return n;
}
Post order: first right Node Pre order: Node left right
==============================================================================
ece264 Professor Niklas's section Huayi Guo
- include <stdio.h>
- include <stdlib.h>
- include <string.h>
- include "IPA2-5print.h"
void print_partition(int size,int *partition) {
printf("[");
int i;
for (i=0;i<size;i++)
{
printf("%d",partition[i]);
}
printf("]\n");
}
int emptyFirstColumn(char *data,int dim) {
int empty=1;
int i;
for (i=0;i<dim;i++)
{
if (data[i*dim]!='0')empty=0; } return empty;
}
Blokus *gen_row(int row,int prevCol, int size,int *partition, char *data,int dim) {
//base case:gone through all rows
if(row==size)
{if(emptyFirstColumn(data,dim))return NULL;
return Blokus_create(data,dim);
}
// recursive case: we stil have not assigned all blocks in
// this partition
int col;
int start=0;
int stop =dim-partition[row]+1;
if(row!=0)
{
start=prevCol - partition[row]+1;
if(start<0)start=0;
stop=prevCol+partition[row-1];
if (stop + partition[row]>dim)
stop=dim-partition[row]+1;
}
Blokus *head =NULL;
for (col=start;col<stop;col++)
{
memset(data+row*dim,'0',sizeof(char)* dim);
memset(data+row*dim+col,'1',sizeof(char)*partition[row]);
Blokus *list= gen_row(row+1,col,size,partition,data,dim);
head=BlokusL_append(head,list);
} return head;
}
Blokus *gen_shifts(int *partition,int size, int dim)
{
char *data=malloc(sizeof(char)*dim*dim); memset(data,'0',sizeof(char)*dim*dim); Blokus *list= gen_row(0,0,size,partition,data,dim);
free(data); return list;
}
Blokus *gen_partition(int budget, int pos, int *partition,int dim)
{
//base case:no more budget spin spin everything
if(budget==0)
{print_partition(pos,partition);
Blokus *list=gen_shifts(partition,pos,dim);
return list;
}
//recursive case:we have budget
Blokus *head =NULL;
int spending;
for (spending=1;spending<=budget;spending++)
{
partition[pos]=spending;
Blokus *list= gen_partition(budget-spending,pos+1,partition,dim);
head =BlokusL_append(head,list);
}
return head;
} Blokus *make_unique(Blokus*head) {
return head;
}
Blokus *generate_pieces(int n)
{
int *partition=malloc(sizeof(int)*n); // step 1+2:partition+shift valid Blokus *head =gen_partition(n,0,partition,n); // step 3:uniqueness
head =make_unique(head);
free(partition);
return head;
}
int main(int argc, char *argv[])
{
if(argc !=2)
{
return EXIT_FAILURE;
}
int n=strtol(argv[1],NULL,10); Blokus *head = generate_pieces(n); BlokusL_print(head); BlokusL_destroy(head);
return EXIT_SUCCESS;
}
Steven Ellis 4/25 Lecture Notes, Binary Trees
ADT = Abstract Data Types
Lists -> -sequential data access (but no random access) -efficient insertion anywhere in the list
Arrays -> -random access -insertion is costly (must allocate new array, copy array, insert)
Trees-> -hierarchal data structure -Consists of nodes (items in the tree) -root node:top node, has no parents -tree grows downwards -leaf node: has no children -internal node: has both parents and children
0 <-root node
/ \ <-links/edges(connect nodes) 0 0 <-internal node / \ / \ 0 0 0 0 <-leaf nodes
Tree Example: File hierarchy ->
-Root node = C: -Internal nodes = Folders -Leaf nodes = Files Binary Trees -> Each node has 0, 1, or 2 children -BSP = Binary Space Partition (method of storing 3D maps) -Special Case: Binary Search Tree (BST)
-For each node N: value(N)>=value(Nleft) and value(N)<value(Nright) -For tree below: B, D, E is left subtree of A. C, F, G, is right subtree of A.
A
/ \ B C / \ / \
D E F G
Ex. Fill BST with 3, 9, 1, 8, 3, 5
5 / \
1 9
\ / 3 8
-Reason for Binary Search Tree: More efficient than linked lists for inserting sorted items -Selection sort insertion into linked list: O(N^2) -Sort insertion into BST: O(Nlog2(N))
-Traversal of trees: -In order traversal results in sorted list for BST -visit left, visit this node, visit right
==========================================================================
Huayi Guo section-1 Professor Niklas
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
typedef struct TreeNode_t{
int value; struct TreeNode_t *left, *right;
}TreeNode;
TreeNode *Tree_create(int value) {
TreeNode *node = malloc(sizeof(Treenode));
node->value = value;
node->left = NULL;
node->right= NULL;
return node;
}
TreeNode *Tree_insert(TreeNode * node, int value) {
if(node == NULL) return TreeNode_create(value);
if(node->value >=value){
node->left = Tree_insert(node->left,value); } else node->right = Tree_insert(node->right,value);
return node;
} void *Tree_inorder(TreNode *node) {
if(node==NULL)return ;
Tree_inorder(node->left);
printf("%d\n",node->value);
Tree_inoder(node->right);
}
void *Tree_preorder(TreNode *node) {
if(node==NULL)return node;
printf("%d\n",node->value);
Tree_inorder(node->left);
Tree_inoder(node->right);
}
TreeNode *Tree_search(TreeNode *node,int value) {
if(node == NULL)return NULL; if(node->value ==)return node; if(node->value < value)return Tree_search(node->left,value); else return Tree_search(node->right,value);
}
/*void *Tree_postorder(TreNode *node) {
if(node==NULL)return node;
Tree_inorder(node->left);
Tree_inoder(node->right);
printf("%d\n",node->value);
}*/
void Tree_destroy(TreNode *node)
{
if(node==NULL)return; Tree_destroy(node->left);
Tree_destroy(node->right); free(node); }
int main(int argc, char *argv[]) {
if(argc != 3){
return EXIT_FAILURE; }
FILE *f = fopen(argv[1],"r");
if(f ==NULL){ return EXIT_FAILURE; }
int num;
while(fscanf(f, "%d",&num) == 1){ root = Tree_insert(root, num); }
fclose(f);
Tree_inorder(root); Tree_destroy(root);
return EXIT_SUCCESS; }
