pert 5 - Tree & Binary Tree - 2101680123 - Milliady Kusnadi The Bu Hiap

Tree & Binary Tree

Binary Tree Concept

A sample of binary tree

of 9 nodes, rooted on

node which contains 18.

Leaves are nodes which

contain 9, 12, 10 and 23.

Type of Binary Tree

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

•         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. A perfect binary tree is a complete binary tree.

•         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”).

PERFECT Binary Tree

COMPLETE Binary Tree

A perfect binary tree is also a complete binary tree.

SKEWED Binary Tree

Property of Binary Tree

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

In some literatures, level of binary tree starts with 1 (root).

Maximum number of nodes on a binary tree of height h is

2^h+1 - 1.

Maximum nodes of a binary tree of height 3 = 1 + 2 + 4 + 8 = 2⁰ + 2¹ + 2² + 2³ = 2⁴ – 1 = 15

Minimum height of a binary tree of n nodes is ²log(n).

Maximum height of a binary tree of n nodes is n - 1.

Skewed binary trees have maximum height

Representation of Binary Tree

•         Implementation using array

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

•         Implementation using linked list

struct node {

          int data;

          struct node *left;

          struct node *right;

          struct node *parent;

};

struct node *root = NULL;

Threaded Binary Tree Concept

A threaded binary tree is same as that of a binary tree but with a difference in storing NULL pointers.

Binary Tree:

Binary Tree without threading

Linked representation of the binary tree

Binary tree with one-way threading

Binary tree with two-way threading