Binary Tree

Binary Tree

A binary tree is a rooted tree where each vertex has zero, one or two children.

Isomorphic binary trees

Let T1 be a binary tree with root r1 and let T2 be a binary tree with root r2. 

The binary trees T1 and T2 are isomorphic if there is one-to-one, onto function f from the vertex set of T1 to the vertex set of T2 satistying the following:

(a) T1 and T2 are isomorphic as rooted trees through an isomorphism f.

(b) v is a left (right) child of w in T1 if and only if f(v) is a left (right) child of f(w) in T2.

Terminal vertices and Height

If a binary tree of height h has t terminal vertices, then

t<=2^h

Full binary tree

A full binary tree is a binary tree in which each vertex has two or no children.

If T is a full binary tree with i internal vertices, then T has i+1 terminal vertices and 2i+1 total vertices.

---

Binary Search Tree

A binary search tree is a binary tree T in which data are associated with the vertices. for each vertex v in T, each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

---

Decision Tree

Decision Tree is a rooted tree If we begin at the root, answer each question, and follow the appropriate edge, so that we eventually arrive at a  deciding terminal vertex . 

Theorem

when a problem has t number of all possible result , if the decision tree has n possible answering number per one vertex and h height, then   

t<=n^h