5 - Tree and Binary Tree - 2101702130 - Andrean

Pertemuan ke - 5
27-03-2018

Binary Tree Concept

is a rooted tree data structure in which each node has at most two children.

•Those two children usually distinguished as left child and right child.

•Node which doesn’t have any child is called leaf.

 Type of Binary Tree

•PERFECT binary tree is a binary tree in which every level are at the same depth.A perfect binary tree is a complete binary tree.

•COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. 

•SKEWED binary tree is a binary tree in which each node has at most one child.

•BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Property of Binary Tree

Maximum number of nodes on level k of a binary tree is 2k.

Maximum number of nodes on a binary tree of height h is 2h+1 - 1.

Binary Tree Using Linked List

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

}root=NULL;

Threaded Binary Tree Concept

Linked representation of the binary tree

Binary tree with one-way threading

Binary tree with two-way threading

A threaded binary tree defined as follows:

"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node."

It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).

To see how this is possible, consider a node k that has a right child r. Then the left pointer of r must be either a child or a thread back to k. In the case that r has a left child, that left child must in turn have either a left child of its own or a thread back to k, and so on for all successive left children. So by following the chain of left pointers from r, we will eventually find a thread pointing back to k. The situation is symmetrically similar when q is the left child of p—we can follow q's right children to a thread pointing ahead to p.

note:
Graph Tree had looping.
Tree not had looping.
Binary Search Tree had 1 smaller value child and 1 bigger value child.


2101702130 - Andrean