CS141 Lab 2

Class Webpage:  http://www.cs.ucr.edu/~cs141-p/cs141_03spr/cs141_03spr.html

Lab Review:

• Trees and their properties

1. Tree-ADT.
2. Binary tree.

• From theoretical perspective

• A tree is a connected, acyclic, undirected graph.

G = (V, E)    |E| = |V| - 1

• Prove that in a tree you can always find a node with degree one. 

Pick a random node, if d=1 end, else go to its neighbors.

• Prove by induction that |E| >= |V|-1 for a connected graph. 

Basis trivial for k=2 

Assume G_k=n,    |E_n| >= |V_n| - 1 (1) 

For k=n+1, A tree of n+1 can be made from a tree of n plus a node and edges: 

|Vn+1| = |Vn| + 1 (2) 

For Gn, (1) holds. 

For Gn+1 to be connected, the new node v_n+1 must connect to at least one node with an edge e. 

This edge does not exist in Gn, 

therefore: |En+1| >= |En| + 1 = (1) => |Vn| - 1 + 1 = |Vn+1| - 1 

• Recursive operation in a binary tree

• In lab programming exercise

Write a program to count how many leaves you have in the tree, or generalizing how many nodes of degree k (1,2,3) you can find in the tree, where k an is input parameter.