(Added an additional set of notes)
Line 665: Line 665:
  
 
}
 
}
 +
 +
== 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

Revision as of 08:59, 25 April 2012

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


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

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <string.h>
  4. 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

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=Lecture27ECE264Spring2012&oldid=51275"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Ph.D. on Applied Mathematics in Aug 2007. Involved on applications of image super-resolution to electron microscopy

Francisco Blanco-Silva