Lecture - 10 �on �Data Structures�

TREES

*

2

A binary tree T is defined as a finite set of elements, called nodes, such that:

a)         T is empty (called the null tree or empty tree), or

b)         T contains a distinguished node R, called the root of T, and the remaining nodes of T form an ordered pair of disjoint binary trees T1  and T2.

​

If T does contain a root R, then the two trees T1   and  T2 are called, respectively, the left and right subtrees of R. If T1    is nonempty, then its root is called the left successor of R; similarly, if T2  is nonempty, then its root is called the right successor of R.

​

TREES

Any node N in a binary tree T has either 0, 1 or 2 successor. The nodes A, B, C and H have two successors, the nodes E and J have only one successor, and the nodes D, F, G, L and K have no successors. The nodes with no successors are called terminal nodes.

​

• The above definition of the binary tree T is recursive since T is defined in terms of the binary subtrees trees T1   and  T2. This means, in particular, that every node N of T contains a left and a right subtree. Moreover, if N is a terminal node, then both its left and right subtree are empty.
• Binary tree T and T ́́́́ are said to be similar if they have the same structure or, in other words, if they have the same shape. The trees are said to be copies if they are similar and if they have the same contents at corresponding nodes.

​

*

3

TREES

*

4

Observe that;

(a)                B is a left successor and C is a right successor of the node A.

(b)               The left subtree of the root A consists of the nodes B, D, E and F, and the right subtree of A consists of the nodes C, G, H, J, K and L.

TREE

Example 7.1:

Consider the four binary trees in fig. 7.2. The three trees (a), (c) and (d) are similar. In particular, the trees (a) and (c) are copies since they also have the same data at corresponding nodes. The tree (b) is neither similar nor a copy of the tree.

*

5

Fig. 7.2

Difference Between a Tree & a Binary Tree

• A binary tree may be empty; a tree cannot be empty.
• No node in a binary tree may have a degree more than 2, whereas there is no limit on the degree of a node in a tree.
• The sub trees of a binary search tree are ordered; those of a tree are not ordered.

*

6

6

*

7

Arithmetic Expressions as trees(cont.)

*

8

8

Figure 11.5 Expression Trees

*

9

TERMINOLOGY

        Terminology describing family relationships is frequently used to describe relationships between the nodes of a tree T. Specifically, suppose N is a node in T with left successor S₁ and right successor S₂ . Then N is called the parent or father of  S₁ and S₂. Analogously, S₁  is called the left child or son of N, and S₂ is called the right child or son of N. Furthermore,   S₁ and S₂  are said to be siblings or brother. Every node N in a binary tree , except the root, has a unique parent, called the predecessor of N.

*

10

Complete Binary Trees

          The tree T is said to be complete if all its levels, except possibly the last, have the maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible.

*

11

Fig. Complete tree T₂₆

The left and right children of the node K are , respectively, 2 * K and 2 * K + 1, and the parent of K is the node [K/2].

The children of node 9 are the nodes 18, 19, and its parent is the node [9/2] =4.

The depth d_n of the complete tree T_n with n nodes is given by

D_n =[log₂ n +1]

This is relatively small number. For example if the complete tree T_n has n =1000000 nodes, then its depth D_n =21.

Complete Binary tree

Extended Binary trees: 2 trees

A binary tree T is said to be a 2 – tree or extended binary tree if each node N has either 0 or 2 children. The nodes with two children are called internal nodes, and the nodes with 0 children are called external nodes.

• Circles for internal nodes.
• Squares for external nodes.

Start with any binary tree and add an external node wherever there is an empty subtree.

Result is an extended binary tree.

*

12

A Binary Tree

An Extended Binary Tree

*

13

Sequential Representation of binary Trees uses only a single linear array TREE together with a pointer variable END as follows:

(a) The root R of T is stored in TREE[1].

(b) If a node occupies TREE[k], then its left child is stored in TREE[2 * K] and its right child is stored in TREE[2*k+1]

(c) END contains the location of the last node of T.

Binary Trees: Array representation

Linked Representation of Binary Tree

• The most popular way to present a binary tree
• Each element is represented by a node that has two link fields ( leftChild and rightChild ) plus an Info field
• The space required by an n node binary tree is�n * sizeof(binaryTreeNode)

*

14

14

*

15

Fig : 7-6

Linked Representation of Binary trees

1. INFO[K] contains the data at the node N
2. LEFT[K] contains the location of the left child of node N
3. RIGHT[K] contains the location of the right child of node N.

*

16

Fig:7-7

Linked Representation of Binary trees

Linked representation of a binary tree

Linked representation uses explicit links to connect the nodes. Example:

​

​

​

2 5

​

3 4 6 7

​

​

8 9

​

​

​

Nodes in this tree can be viewed as positions in a sequence (numbered 1 through 9).

*

17

Linear representation of a binary tree

Advantages of linear representation:

1. Simplicity.

2. Given the location of the child (say, k), the location of the parent is easy to determine (k / 2).

​

Disadvantages of linear representation:

1. Additions and deletions of nodes are inefficient, because of the data movements in the array.

2. Space is wasted if the binary tree is not complete. That is, the linear representation is useful if the number of missing nodes is small.

​

​

*

18

Linear representation of a binary tree can be implemented by means of a linked list instead of an array

This way the above mentioned disadvantages of the linear representation is resolved.

​

Binary Tree Traversal

• Many binary tree operations are done by performing a traversal of the binary tree
• In a traversal, each element of the binary tree is visited exactly once

​

*

19

19

*

20

*

21

*

22

Also see example 7.7, 7.9, 7.10

Binary Tree Traversal Methods

*

23

23

Binary Tree Traversal Methods

*

24

Preorder Example (visit = print)

a b d g h e i c f j

*

25

25

Preorder of Expression Tree

/ * + a b - c d + e f

Gives prefix form of expression.

*

26

26

Inorder Example (visit = print)

*

27

27

g d h b e i a f j c

Postorder Example (visit = print)

*

28

28

g h d i e b j f c a

Postorder of Expression Tree

​

​

​

​

​

​

a b + c d - * e f + /

Gives postfix form of expression.

*

29

29

*

30

*

31

*

32

*

33

*

34

*

35

*

36

*

37

*

38

*

39

*

40

*

41

*

42

*

43