Data Storage-Trees & Binary Trees

There are 2 major ways to store data in the memory of the computer
-arrays

• use subscripts to immediately access elements
• fast access but may consume more memory

-linked list

• each noderefers to the next in the collection.To go to one often travels sequentially
• may be slower,but may be manage memory better

.tree-also a data storage way
-one implementation of a binary tree has nodes with left and right link field
-a tree has a set of nodes and directed edges that connects them
  -a directed edge connects a parent to its child


.tree properties
-one node is distinguished as the root
-every node(except the root) is connected by an edge from exactly one other node
-a unique path traverses from the root to each node
-a tree store data in a hierarchical manner
 -trees have layers of nodes,where some are higher,others are lower


.some tree terminology
 -NODE--an element in the tree references data and other nodes
 -ROOT--the node at the top-it is upside down
 -PARENT--the node directly above another node
 -SIZE--the number of descendants plus one for the node itself
 -LEAVES--nodes with no children
 -LEVELS--the roots at A is at level 0,E and F are at level 2


.some applications of trees
 -File systems
  -hierarchical files systems include Unix and DOS
  -in DOS,each \ represents an edge(In Unix,its /)
  -each directory is a file with a list f all its children
 -Store large volumes of data
  -data can be quickly inserted,removed and found
 -data structure used in a variety of situtions
  -implement data vase management systems
  -compilers-expression tree,symbol tree
 -the computer science
  -departments new logo(when not ready then use of a binary tree is done)


.Binary Tree
 -N-ary tree has N children max from each node
 -a inary tree is a tree where all nodes have zero,one or two children
 -each node is a leaf,has a right child,has a left child,or has both a left and right child


.Binary tree defined
 -a binary tree is either
  -an empty tree
  -consist of a node,called a root, and a zero,one or two children(left or right),each of which are themselves a binary tree
 -this recursive definition uses the term "empty tree" as the base case
 -every non-empty node has two children,either of which may be empty


.Applications of binary tree
 -binary tree can represent arithmetic expression
 -an infix expression willl have a parent operator and two children operands:
  -The expression:
   ((3+(7*2))-1)
   Each parenthesized expression becomes a tree. Each operand is a leaf,each operator is an internal node
  -to evaluate the expression tree:
   -take any two leaves
   -apply the parent's operator to them
   -replace that operator with the value of the subexpression.