CSC 311      DATA STRUCTURES

Definitions of tree

1. A tree is an acyclic and connected graph. If it's non-empty then one of its 
nodes is designated as the root.

2. A tree is a set of sequences closed under operation of taking a begining 
subsequence. (This is sometimes refered to as a "tree of paths".)

Example: {<1,1,0>, <1,1>, <0,1>, <1>, <0>, <>}

3. A finite tree is any of the following:

(i) the empty set

(ii) the root (a node) with some number of subtrees attached to it. (If the 
attached subtree is non-empty then the attachment has a form of an edge that 
goes from the root of the tree to the root of the subtree in question.)

Note: Also, consult your textbook for definition of finite tree.



Properties of trees

4. A tree is an acyclic graph with n nodes and n-1 edges.

5. A tree is a connected graph with n nodes and n-1 edges.

6. A tree is an acyclic graph that becomes cyclic if an edge is added.

7. A tree is a connected graph that becomes disconnected if an edge is removed.



Definition of binary tree

1. A binary tree is an acyclic and connected graph of degree 3 (each node has no more than 3 edges incident on it). If it's non-empty then one of its nodes is designated as the root and it has no more than 2 incident edges on it.

2. A binary tree is a set of binary sequences closed under operation of taking a begining 
subsequence. (This is sometimes refered to as a "binary tree of paths".)

Example: {<1,1,0>, <1,1>, <0,1>, <1>, <0>, <>}

2a. A binary tree binary is a set of positive integers closed under operation of positive integer division by 2.

Example: {14, 7, 5, 3, 2, 1}

2b. A complete tree binary is a set of first n positive integers.

Example: {14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

3. A finite binary tree is any of the following:

(i) the empty set

(ii) the root (a node) with 2 subtrees attached to it. (If the 
attached subtree is non-empty then the attachment has a form of an edge that 
goes from the root of the tree to the root of the subtree in question.)

Note: Also, consult your textbook for definitions of finite binary tree and finite complete binary tree.