(Added an additional set of notes)
Line 1: Line 1:
 +
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
 
Hanye Xu April 20 Lecture 27
  

Revision as of 14:09, 25 April 2012

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


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=51297"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett