Data Structure

There is a relationship between internal nodes and external nodes i.e. If the number of internal nodes is N, the number of external nodes will be N+1. Let us discuss another property of the binary trees. Property A binary tree with N internal nodes has 2N links, N-1 links to internal nodes and N+1 links to external nodes. Please recall that the first property dealt with the relationship between internal and external nodes. This property is dealing with the relationship of links to the internal nodes. Now, what is a link? As you might already have understood, a link is that line, which we draw between two nodes in a tree. Internally we use pointers in C++ to realize links. In pictorial sketches, however, we use a line to show a link between the two nodes. The property defines, that if you have a binary tree with Nodes, how many links, it will have between the internal nodes (remember, it includes the leaf nodes), and how many links it will have between the external nodes. We h

Binary Tree In  computer science , a  binary tree  is a  tree   data structure  in which each node has at most two  children , which are referred to as the  left child  and the  right child . A  recursive definition  using just  set theory  notions is that a (non-empty) binary tree is a  tuple  ( L ,  S ,  R ), where  L  and  R  are binary trees or the  empty set  and  S  is a  singleton set . [1]  Some authors allow the binary tree to be the empty set as well. Types of binary tree ·          A  rooted ·          A  full  binary tree ·          A  perfect  binary tree ·          In a  complete  binary tree every level ·          In the  infinite complete  binary tree ·          A  balanced  binary tree ·          A  degenerate  (or  pathological ) tree Full binary tree Complete binary tree Binary Expression tree A  binary expression tree  is a specific kind of a  binary tree  used to represent expressions. Two common types of expressions th

Infix, Postfix and Prefix Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands. Infix notation: X + Y Operators are written in-between their operands. This is the usual way we write expressions. An expression such as  A * ( B + C ) / D  is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer." Postfix notation (also known as "Reverse Polish notation"): X Y + Operators are written after their operands. The infix expression given above is equivalent to  A B C + * D / The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.