Binary Tree

Chapter 5: Binary Trees • Basic tree concepts • Binary trees • Binary search trees • AVL trees • Heaps

1

Basic Tree Concepts • Trees are used for: – Representing algebraic formulas – Searching large and dynamic lists

2

Basic Tree Concepts • A tree consists of: – nodes: finite set of elements – branches: directed lines connecting the nodes

• For a node: – degree: number of branches associated with the node – indegree: number of branches towards the node – outdegree: number of branches away from the node

• For a tree: – root: node with indegree 0 3 – nodes different from the root must have indegree 1

Terminology • Leaf: node with outdegree 0 • Internal node: not a root or a leaf • Parent: node with outdegree greater than 0 • Child: node with indegree greater than 0 • Siblings: nodes with the same parent • Path: sequence of adjacent nodes

4

Terminology • Ancestor: node in the path from the root to the node • Descendent: node in a path from the node to a leaf • Level: the node's distance from the root (at level 0) • Height (Depth): the level of the leaf in the longest path from the root plus 1 • Sub-tree: connected structure below the root 5

Tree Representation General tree Case

Controller

Computer

CPU

ALU

3.5" Disk

CD-ROM

ROM

6

Tree Representation Indented list Computer Case CPU Controller ALU ROM ... 3.5" Disk CD-ROM

7

Tree Representation Parenthetical listing Computer (Case CPU (Controller ALU ROM ...) 3.5" Disk CDROM)

8

Binary Trees • A node cannot have more than two subtrees: A

B C

E D

left subtree

F

right subtree 9

Binary Tree Properties • Height of binary trees: Hmax = N Hmin = log2N + 1

10

Binary Tree Properties • Height of binary trees: Hmax = N Hmin = log2N + 1 Nmin = H Nmax = 2H − 1

11

Binary Tree Properties • Balance: – Balance factor: B = HL − HR – Balanced tree:

balance factor is 0, -1, or 1

sub-trees are balanced

12

Binary Tree Properties • Completeness: – Complete tree:

A

Nmax = 2H − 1 (last level is full)

B D

C E

– Nearly complete tree:

G

A

Hmin = log2N + 1 nodes in the last level are on the left

F

B D

C E

13

Expression Trees • Each leaf is an operand • The root and internal nodes are operators • Sub-trees are sub-expressions

14

Expression Trees + *

d +

a b

c

a * (b + c) + d 15

Binary Tree Structure Node leftSubTree <nodePointer> data rightSubTree <nodePointer> End Node

16

Binary Tree Traversal • Each node is processed once and only once in a predetermined sequence.

17

Depth-First Traversal 1

2

2

3

PreOrde r NLR

1

InOrder LNR

3

3

1

2

PostOrd er LRN

18

PreOrder Traversal A

B C

A

E D

B C

F

D

Processing order

E

F

19

PreOrder Traversal A

A

B C

A

B

E D

B C

F

D

Processing order

E

F

C

E D

F

Walking order

20

PreOrder Traversal Algorithm preOrder (val root <nodePointer>) Traverses a binary tree in node-left-right sequence Pre Post

root is the entry node of a tree/subtree each node has been processed in order

1 if (root is not null) 1 process (root) 2 preOrder (root −> leftSubTree) 3 preOrder (root −> rightSubTree) 4 return End preOrder 21

InOrder Traversal A

B C

E D

C B D

F

A

Processing order

E F

22

InOrder Traversal A

A

B C

B

E D

C B D

F

A

Processing order

E F

C

E D

F

Walking order

23

InOrder Traversal Algorithm inOrder (val root <nodePointer>) Traverses a binary tree in left-node-right sequence Pre Post

root is the entry node of a tree/subtree each node has been processed in order

1 if (root is not null) 1 inOrder (root −> leftSubTree) 2 process (root) 3 inOrder (root −> rightSubTree) 4 return End inOrder 24

InOrder Traversal + *

d a*b+c+d

+

a b

c

25

InOrder Traversal ( (

*

+

)

) (

a b

d +

((a * (b + c)) + d)

)

c

26

PostOrder Traversal A

B C

C

E D

D B

Processing order

F

F E

A

27

PostOrder Traversal A

A

B C

C

B

E D

D B

Processing order

C

F

F E

A

E D

F

Walking order

28

PostOrder Traversal Algorithm postOrder (val root <nodePointer>) Traverses a binary tree in left-node-right sequence Pre Post

root is the entry node of a tree/subtree each node has been processed in order

1 if (root is not null) 1 postOrder (root −> leftSubTree) 2 postOrder (root −> rightSubTree) 3 process (root) 4 return End preOrder 29

Breadth-First Traversal A

B C

E D

F

A B E C D F

Processing order

30

Breadth-First Traversal A

A

B C

B

E D

F

A B E C D F

Processing order

C

E D

F

Walking order

31

Breadth-First Traversal Algorithm 1

breadthFirst (val root <nodePointer>)

pointer = root

2 while (pointer not null) 1

process (pointer)

2

if (pointer −> left not null) 1

3

if (pointer −> right not null) 1

4

dequeue (pointer)

else 1

3

enqueue (pointer −> right)

if (not emptyQueue) 1

5

enqueue (pointer −> left)

pointer = null

return

End

breadthFirst

32