A tree is a collection of nodes. The collection can be empty; otherwise a tree consists of a specially designed node called root, and one or more non empty sub trees T1, T2, â€¦, Tk, each of whose roots are connected by a directed edge from root.

__TREE
INTRODUCTION__

**Tree**

A tree is
a collection of nodes. The collection can be empty; otherwise a tree consists
of a specially designed node called **root**,
and one or more non empty sub trees T_{1}, T_{2}, â€¦, T_{k},
each of whose roots are connected by a directed edge from root.

**Root**

The root is the first and top most nodes in the
hierarchical arrangement of data items. A node which does not have a parent
node is called root node. In the above tree, the root is A.

**Node**

Each data item present in the tree is called a **node.** It is the basic data structures
that specifies the data information and have links to other data items. Example
node A, B, â€¦..,,

Q.

**Leaf**

A node
which doesnâ€Ÿt have children is called **leaf
or Terminal node**. In the above tree B, C, H, I, K, L, M, N, P, Q are leaf
node.

**Siblings**

Children of the same parents are said to be **siblings.** In the above tree B, C, D, E,
F ,G are siblings, I,J are siblings, K, L, M are siblings, P, Q are siblings.

**Path**

A **path** from node *n*_{1} to *n _{k}*
is defined as a sequence of nodes

There is
exactly only one path from the root to each node. In the above tree the path
from A to P is A, E, J, P. Where A is the parent for E, E is the parent of J,
and J is the parent of P.

**Length**

The **length** is defined as the number of
edges on the path. The length for the path A to P is 3.

**Degree**

**i. Degree of a node**

The number of sub trees of a node is called its **degree**. In the above tree, degree of A
is 6, degree of F is 3, and degree of B is 0.

**ii. Degree of a tree**

The degree of the tree is the maximum degree of any
node in the tree. In the above tree, the degree of the tree is 6.

**Level**

The level of a node is defined by initially letting
the root be at level one. If a node is at level L then its children are at
level L+1.

In the previous tree, the level of A is 1, level of
B, C, D, E, F, G is 2, level of H, I, J, K, L, M, N is 3, and the level of P, Q
is 4.

**Depth**

For any node n, the depth of n is the length of the
unique path from root to n. For example, the depth of root A is 0, depth of c
is 1, depth of H is 2, and the depth of P is 3

**Height**

For any node n, the heig ht of the node n is the
length of the longest path from n to the leaf. The height of the leaf is zero.
For example, the height of node F is 1, and the height of E is 2.

**Note**

^{Ã˜ }The
height of the tree is equal to the height of the root.^{}

^{ }

^{Ã˜ }Depth of
the tree is equal to the height of the tree.^{}

**Terminal node**

A node with degree zero is called a **terminal node.** Leaf is called the
terminal node because it has the degree 0. In the previous tree node B, C, H,
I, K, L, M, N, P, Q are terminal nodes.

**Non â€“ Terminal Node**

Any node whose degree is non zero is called **Non** **â€“** **Terminal node.** In the
previous tree node A, D, E, F, G, J are non terminal nodes.

**Edge**

An edge is a condition line which connects two
adjacent node of a tree. The line drawn from one node to another node is called
**edge.** If a tree has N nodes, then
there are N-1 edges. For example, the previous tree has 13 nodes and 12 edges.

**Interior node**

A node is said to be an interior node only if it is
between root and leaves. All non terminal nodes except the root is called
interior node. For example, D, E, F, G, J are interior nodes.

**Ancestor node**

A node is said to be an ancestor of another node
only if it is the parent of that node or the parent of same ancestor of that
node. For example, the ancestor of node H are A and D, and the ancestor of node
F is A.

**Descendent node**

A node is said to be a descendent of another node
if it is the child of that node or the child of some other descendent of that
node. For example, the descendent of F are K, L, M, and the descendent of E are
I, J, P, Q.

**Forest**

A forest is a set of disjoint trees. If the root is
removed, then each node becomes a separate tree to become a forest.

__Implementation of Trees__

One way
to implement a tree would be to have in each node, besides its data, a pointer
to each child of the node. However, since the number of children per node can
vary so greatly and is not known in advance, it might be infeasible to make the
children direct links in the data structure, because there would be too much
wasted space. The solution is simple: Keep the children of each node in a
linked list of tree nodes.

typedef
struct tree_node *tree_ptr;

struct
tree_node

{

element_type
element;

tree_ptr
first_child;

tree_ptr
next_sibling;

};

In the
above fig, arrows that point downward are *first_child*
pointers. Arrows that go left to right are *next_sibling*
pointers.

__Tree Traversals__

Tree
traversal is a method for visiting all the nodes in the tree exactly once.
There are three types of tree traversal techniques, they are

i.
Inorder Traversal

ii. Preorder
Traversal

iii.
Postorder Traversal

**Inorder Traversal**

The
inorder traversal of a binary tree is performed as

^{Ã˜ }Traverse
the left subtree in inorder^{}

^{ }

^{Ã˜ }Visit the
root^{}

^{ }

^{Ã˜ }Traverse
the right subtree in inorder.^{}

**Recursive routine for inorder traversal**

void
inorder(Tree T)

{

if(T!=NULL)

{

inorder(T->left);

printElement(T->Element);

inorder(T->right);

}

}

**Preorder Traversal**

The
preorder traversal of a binary tree is performed as

^{Ã˜ }Visit the
root^{}

^{ }

^{Ã˜ }The left
subtree in preorder^{}

^{ }

^{Ã˜ }Traverse
the right subtree in preorder.^{}

**Recursive routine for preorder traversal**

void
preorder(Tree T)

{

if(T!=NULL)

{

printElement(T->Element);

preorder(T->left);

preorder(T->right);

}

}

**Postorder Traversal**

The
postorder traversal of a binary tree is performed as

^{Ã˜ }Traverse
the left subtree in postorder^{}

^{ }

^{Ã˜ }Traverse
the right subtree in postorder.^{}

^{ }

^{Ã˜ }Visit the
root^{}

**Recursive routine for postorder traversal**

void
postorder(Tree T)

{

if(T!=NULL)

{

postorder(T->left);

postorder(T->right);

printElement(T->Element);

}

}

__Example__

Inorder : 1 2 3 4 5 6 7

Preorder: 4 2 1 3 6 5 7

Postorder: 1 3 2 5 7 6 4

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Advanced Non-Linear Data Structures : Tree Introduction |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.