(9 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
[[Category:ECE264]] [[Category:Programming]] [[Category:C]] [[Category:lecture notes]]
 +
 +
=Lecture 27, [[ECE264]], Spring 2012, Prof. Lu=
 +
----
 +
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
  
Line 350: Line 418:
 
return n;
 
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;
 +
}
 +
 +
 +
=================
 +
Rohan Khante
 +
===================
 +
 +
 +
 +
      NODE
 +
    /    \
 +
    Left  Right
 +
This is how a node looks like
 +
All the values on the left side are smaller than the node and the ones on the right are greater than the node. This is a binary search tree. The efficiency of a binary tree depends on how "messy" it is. If all sorted data is entered into a tree then the it becomes like a linked list since all the values on one side become equal to NULL(NOT zero.)
 +
 +
Example
 +
 +
Binary search tree will be like
 +
            8
 +
          /  \
 +
        3      10
 +
        / \    /  \ 
 +
        1  6    9    14
 +
          /\      /  \
 +
          4 7    13    16       
 +
 +
Ordering of lists
 +
There are three types of ordering of lists: PREORDER, INORDER and POSTORDER
 +
Some properties
 +
If a tree is null or has a single node, then the empty list/node is the preorder, inorder, and postorder listing of T
 +
ELSE
 +
The preorder listing of T is the root of T, followed by the nodes of T1 in preorder and the other nodes in preorder
 +
The inorder listing of T is the nodes of T1 in inorder, followed by the root r, followed by the nodes of T2 in inorder, . . . , and the nodes of Tk in inorder.
 +
The postorder listing of T is the nodes of T1 in postorder, . . . , the nodes of Tk in postorder, all followed by the root r.
 +
 +
The reason why BST is preferred when it comes to large searching is because
 +
For insertion its faster than linked list
 +
Selection sort insertion into linked list: O(N^2)
 +
-Sort insertion into BST: O(Nlog2(N))
 +
where O denotes the complexity of insertion
 +
O(N^2) means the time it takes to the sort is dependent on the square of the number of elements
 +
O(Nlog2(N)) means the time is dependent on N log2(N)
 +
N > log2(N)is an easily verifiable fact
 +
Multiplying by N on both sides we get
 +
N^2 > Nlog2(N)
 +
O(N^2) > O(Nlog2(N))
 +
 +
Analogous to BST we have file structure in OSes
 +
Root:- C Drive(any drive)
 +
Sub Nodes:- Directories/Folders that you made inside them
 +
Leafs- Files inside the folders
 +
 +
How parser works
 +
 +
2+3*5/6
 +
assume BODMAS and left-to-right rule
 +
 +
    +
 +
  /  \
 +
  2    *
 +
    /  \
 +
    3  /
 +
        /  \
 +
      5    6
 +
A parser creates a binary tree and then implements the functions. Parsing is one if the first things that a compiler does.
 +
----
 +
[[2012_Spring_ECE_264_Lu|Back to ECE264, Spring 2012, Prof. Lu]]

Latest revision as of 04:28, 11 July 2012


Lecture 27, ECE264, Spring 2012, Prof. Lu

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


==========================================================================

Huayi Guo section-1 Professor Niklas

  • /
  1. include<stdio.h>
  2. include<stdlib.h>
  3. 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; }


=====

Rohan Khante

=======
     NODE
    /     \
   Left   Right

This is how a node looks like All the values on the left side are smaller than the node and the ones on the right are greater than the node. This is a binary search tree. The efficiency of a binary tree depends on how "messy" it is. If all sorted data is entered into a tree then the it becomes like a linked list since all the values on one side become equal to NULL(NOT zero.)

Example

Binary search tree will be like 

           8
         /   \
        3       10
       / \     /   \   
       1  6    9    14
          /\       /  \
          4 7     13    16

Ordering of lists There are three types of ordering of lists: PREORDER, INORDER and POSTORDER Some properties If a tree is null or has a single node, then the empty list/node is the preorder, inorder, and postorder listing of T ELSE The preorder listing of T is the root of T, followed by the nodes of T1 in preorder and the other nodes in preorder The inorder listing of T is the nodes of T1 in inorder, followed by the root r, followed by the nodes of T2 in inorder, . . . , and the nodes of Tk in inorder. The postorder listing of T is the nodes of T1 in postorder, . . . , the nodes of Tk in postorder, all followed by the root r.

The reason why BST is preferred when it comes to large searching is because For insertion its faster than linked list Selection sort insertion into linked list: O(N^2) -Sort insertion into BST: O(Nlog2(N)) where O denotes the complexity of insertion O(N^2) means the time it takes to the sort is dependent on the square of the number of elements O(Nlog2(N)) means the time is dependent on N log2(N) N > log2(N)is an easily verifiable fact Multiplying by N on both sides we get N^2 > Nlog2(N) O(N^2) > O(Nlog2(N))

Analogous to BST we have file structure in OSes Root:- C Drive(any drive) Sub Nodes:- Directories/Folders that you made inside them Leafs- Files inside the folders

How parser works

2+3*5/6 assume BODMAS and left-to-right rule 

    +
  /   \
 2    *
    /  \
    3   /
       /  \
      5    6

A parser creates a binary tree and then implements the functions. Parsing is one if the first things that a compiler does.

Back to ECE264, Spring 2012, Prof. Lu

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=Lecture27ECE264Spring2012&oldid=51940"
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