csintro unit12 examples

bst.py

class BSTNode:

    def __init__(self,key):
    
        self.key = key
        self.left = None
        self.right = None
        
        
class BST:

    def __init__(self):
    
        self.root = None
        
    
    def insert(self,key):
    
        new_node = BSTNode(key)
    
        if self.root is None:
            self.root = new_node
            
        else:
            node = self.root
            while node is not None:
                
                if node.key == key:
                    return
        
                parent = node
                if node.key < key:
                    node = node.right
                else:
                    node = node.left
            
            if parent.key < key:
                parent.right = new_node
            else:
                parent.left = new_node


    def delete(self,key):
    
        node = self.root
        parent = None
        
        while node is not None:
        
            if node.key == key:
                break
            
            parent = node
            if node.key < key:
                node = node.right
            else:
                node = node.left
            
        if node is None:
            return False
            
        if node.left is None or node.right is None:
        
            if node.left is None:
                child = node.right            
            else:
                child = node.left
                
            if parent is None:
                self.root = child
                return True
                
            if node == parent.left:
                parent.left = child
            else:
                parent.right = child
                            
        else:
            succ_parent = None
            succ_node = node.right
            while succ_node.left is not None:
                succ_parent = succ_node
                succ_node = succ_node.left
                
            node.key = succ_node.key    
                
            if succ_parent is None:
                node.right = succ_node.right 
            else:
                succ_parent.left = succ_node.right

        return True


    def search(self,key):
                    
        node = self.root
        while node is not None:
                
            if node.key == key:
                return True
        
            if node.key < key:
                node = node.right
            else:
                node = node.left
            
        return False


    def minimum(self):
    
        if self.root is None:
            return None
            
        node = self.root
        while node.left is not None:                
                node = node.left
            
        return node.key


    def maximum(self):
    
        if self.root is None:
            return None
            
        node = self.root
        while node.right is not None:                
                node = node.right
            
        return node.key        


    def inorder(self):
    
        self._inorder(self.root)
        print()
        
        
    def _inorder(self,node):
    
        if node is not None:
            self._inorder(node.left)
            print(node.key,end=' ')
            self._inorder(node.right)    


    def __str__(self):
        
        return self._dump(self.root,0,'root')
        
        
    def _dump(self,node,level,prefix):
        
        indent = '\t'*level
        
        if node is None:
            return f'{indent}[{prefix}] <empty>'
            
        else:
            return '\n'.join([f'{indent}[{prefix}] key={node.key}',
                              self._dump(node.left,level+1,'left '),
                              self._dump(node.right,level+1,'right')])
            


t = BST()
keys = [8,3,6,3,23,11,2,-7,1,33,-27,49,4,-67]
for key in keys:
    t.insert(key)
    
print(t)
print(t.inorder())
print('11 in tree: ',t.search(11))
print('7 in tree: ',t.search(7))
print(all(map(t.search,keys)))
print(t.minimum())
print(t.maximum())

from random import shuffle
shuffle(keys)
for key in keys:
    print(f'Deleting {key} -> {t.delete(key)}')
print(t)
    

circular-fifo.c

#include <stdio.h>
#include <stdlib.h>

#define QSIZE 3

int queue[QSIZE];
int qlen = 0;
int write_ix = 0;
int read_ix = 0;


int enqueue(int item) {
  if (qlen==QSIZE) return -1;
  queue[write_ix] = item;
  write_ix++;
  qlen++;
  if (write_ix==QSIZE) {
    write_ix = 0;
  }
  return 0;
}

int dequeue(int *dest) {
  if (qlen==0) return -1;
  *dest = queue[read_ix];
  read_ix++;
  qlen--;
  if (read_ix==QSIZE) {
    read_ix = 0;
  }
  
  return 0;
}

int main() {
  for (int i=0;i<10;i++) {
    printf("%d\n",enqueue(i));
  }

  int item;
  while (dequeue(&item)==0) {
    printf("%d\n",item);
  }
  
  return 0;
}

dfs-arithmetic.py

# sample tree as a list of (node,children) pairs
tree = ('*',[
             ('+',[
                   (8,[]),
                   (2,[])
                  ]),
             ('-',[
                   (3,[])
                  ])
            ]
       ) 
             

# processing function
def process(typ,values):
    if typ=='*':
        return values[0]*values[1]
    elif typ=='/':
        return values[0]/values[1]
    elif typ=='+':
        if len(values)==1:
            return values[0]
        return values[0]+values[1]
    elif typ=='-':
        if len(values)==1:
            return -values[0]
        return values[0]-values[1]
    else:
        return typ
        

# DFS traversal with postorder processing of nodes                    
def DFS_postorder(node):   
    values = []
    for child in node[1]:
        values.append(DFS_postorder(child))
        
    return process(node[0],values)



# print value of total arithmetic tree        
print(DFS_postorder(tree))

dfs-processing.py

# sample tree as a list of (node,children) pairs
tree = ('*',[
             ('+',[
                   (8,[]),
                   (2,[])
                  ]),
             ('-',[
                   (3,[])
                  ])
            ]
       ) 
             

# test processing function
def process(node):
    print(node[0])
    

def DFS_preorder(node):
    process(node)
    for child in node[1]:
        DFS_preorder(child)

                
def DFS_postorder(node):    
    for child in node[1]:
        DFS_postorder(child)        
    process(node)


def DFS_inorder(node):
    kids = node[1]
    num_kids = len(kids)
    if num_kids>0:
        DFS_inorder(kids[0])
    process(node)
    if num_kids>1:
        DFS_inorder(kids[1])
    
    

        
print('preorder:')        
DFS_preorder(tree)
print('postorder:')
DFS_postorder(tree)
print('inorder:')
DFS_inorder(tree)

traversals.py

# sample graph as adjacency list
graph = { 'A':['B','C'],
          'B':['A','C','D'],
          'C':['A','B','D','E'],
          'D':['B','C'],
          'E':['C']
        }

# DFS traversal (iterative, with stack)
print('DFS traversal')        
visited = set()
stack = []

stack.append('A')
while len(stack)>0:
    node = stack.pop()
    if node not in visited:
        print('visiting:',node)
        visited.add(node)
        stack.extend(graph[node])
        

# BFS traversal (iterative, with queue)
print('BFS traversal')
from collections import deque
visited = set()
queue = deque()

queue.append('A')
while len(queue)>0:
    node = queue.popleft()
    if node not in visited:
        print('visiting:',node)
        visited.add(node)
        queue.extend(graph[node])