[go: up one dir, main page]
Scribd
Upload
57 views6 pages

General Tree: 1 Mitra Kabir, Dept. of CSE, DU

The document defines and describes general trees. A general tree is a finite set of nodes with one root node and zero or more subtrees. It can differ from a binary tree in that nodes can have any number of children rather than just two, and children are not designated as left or right. The document also describes how general trees are represented in memory using three parallel arrays to store node information, child pointers, and sibling pointers. Finally, it notes how a general tree can correspond to a binary tree with children ordered as first child then next sibling.

Uploaded by

MD.ASHADUZZAMAN Ayon
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
57 views6 pages

General Tree: 1 Mitra Kabir, Dept. of CSE, DU

The document defines and describes general trees. A general tree is a finite set of nodes with one root node and zero or more subtrees. It can differ from a binary tree in that nodes can have any number of children rather than just two, and children are not designated as left or right. The document also describes how general trees are represented in memory using three parallel arrays to store node information, child pointers, and sibling pointers. Finally, it notes how a general tree can correspond to a binary tree with children ordered as first child then next sibling.

Uploaded by

MD.ASHADUZZAMAN Ayon
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 6

General Tree

Mitra Kabir,Dept. of CSE, DU 1


General Tree

A general tree (a tree) is defined to be a nonempty finite set T of elements, called nodes
such that

(1) T contains a distinguished element R, called the root of T.

(2) The remaining elements of T form an ordered collection of zero or more disjoint trees
T1, T2,…..Tm.

• The trees T1, T2,….Tm are called subtrees of root R and the roots of T1, T2,…Tm are
called successors of R.
A
• Example:

B C D

E F G H I J
Figure: General Tree
K
Mitra Kabir,Dept. of CSE, DU 2
Difference between General Tree and Binary Tree

(1) A binary tree T’ is not a special case of a general tree T.

(2) Suppose a node N has only one child. Then the child is identified as a left child or
right child in binary tree T’, but no such distinction exists in a general tree T.

Example:

Tree T1 Tree T2

Mitra Kabir,Dept. of CSE, DU 3


Memory Representation of General Tree
• Suppose T is a general tree. T is maintained in memory by means of a linked
representation that uses following three parallel arrays:
1. INFO[K] = Information at node N
INFO CHILD SIBL
2. CHILD[K] = location of the first child of N. C 3 13
1
3. SIBL[K] = location of next sibling of N 2
B 5 1

3 G 0 0
• Here K is the location of node N of T. K 0 0
4
5 E 0 9
• Here ROOT is used as the root of T.
6 A 2 0
• Example: 7 I 0 12
A
8

B 9 F 0 0
C D
10

E F G H I J 11 H 4 7
ROOT 6
12 J 0 0
K
13 D 11 0
Figure: General Tree and Its Memory Representation
Mitra Kabir,Dept. of CSE, DU 4
Correspondence between General Tree and Binary Tree
(1) The root of T’ will be the root of T.

(2) The left child of N’ in T’ will be the first child of node N in T and the right child of
N’ in T’ will be the next sibling of N in T.

General Tree T Binary Tree T’


A
A
B
B C D
E C
E F G H I J
F G D
K
H

K I

J
Mitra Kabir,Dept. of CSE, DU 5
END!!!

Mitra Kabir,Dept. of CSE, DU 6

You might also like