Trees

Test yourself

Trees

Unlike other data structures in computer science, trees represent data hierarchically.

Roots and branches

Trees begin with a ‘root’ node, with one or more ‘branches’ beneath it.
Each branch, in turn, can have one or more sub-branches connected to it.

Tree construction

The rules for creating a tree are:
- Each node must only be connected to one ‘parent’ node and one or more ‘children’.
- There should be no connections directly between nodes on the same level of the hierarchy.

Tree traversal

There are three ways to navigate, or ‘traverse’ a tree data structure:
- Pre-order.
- In-order.
- Post-order.

Pre-order traversal

Pre-order traversal starts with the root node, then visits each of the other nodes from left to right.
In the example shown, the nodes are visited in the following order:
- Tiger, Zebra, Lion, Gazelle, Giraffe, Rhino, Hippo, Elephant

In-order traversal

In-order traversal starts with the nodes in the left subtree, then visits the root node followed by the nodes in the right subtree.
In this case, the nodes above are visited in the following order:
- Lion, Zebra, Gazelle, Giraffe, Tiger, Elephant, Hippo, Rhino.

Post-order traversal

Post-order traversal starts by visiting the nodes in the left subtree from bottom to top, then the right subtree bottom to top, before finishing with a visit to the root node. - The nodes in the example above are therefore visited in the following order:
- Lion, Gazelle, Giraffe, Zebra, Elephant, Hippo, Rhino, Tiger.

Binary Search Trees

A binary search tree is a tree data structure used for efficient searching of data.

Binary search trees

Binary search trees share the same properties as trees, with the exception that each node can have no more than two ‘child’ nodes.
Binary search trees are very quick to search.

Storing data

After storing the first piece of data in the root node:
- The second entry is stored in a child node to the left of the root if it has a lesser value.
- The second entry is stored in a child node to the right if it has a greater value.

Example

The procedure for storing ‘Tiger’, ‘Zebra’, ‘Lion’, ‘Gazelle’ and ‘Rhino’ in the order given is as follows:
'Tiger’ takes the root node.
‘Zebra’ is greater than ‘Tiger’ alphabetically, so is stored as a child node to the right of the root.

Step 2

‘Lion’ comes before ‘Tiger’ and so is stored as a child node to the left of the root.

Step 3

‘Gazelle’ comes before ‘Tiger’ and before ‘Lion’, so is stored as a left child to the ‘Lion’ node.
‘Rhino’ also comes before ‘Tiger’, but after ‘Lion’ so is stored on the right of this node.

1Components of a Computer

1.1Structure & Function of the Processor

1.1.1Structure of the CPU

1.1.2Fetch, Decode, Execute Cycle

1.1.3Factors Affecting CPU Performance

1.1.4CPU Architecture

1.2Types of Processors

1.2.1CISC & RISC

1.2.2Multicore & Parallel Cores

1.3Input, Output & Storage

1.3.1Computer Systems

1.3.2Magnetic Storage

1.3.3Optical Storage

1.3.4Types of Optical Storage

1.3.5Types of Memory

1.3.6Flash Memory

1.3.7Virtual Memory

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

4.1Data Types

4.1.1Data Types

4.1.2Arrays & Strings

4.1.3Representing Numbers

4.1.4Binary Arithmetic

4.1.5Hexadecimal

4.1.6Converting Binary Numbers

4.1.7Floating Points in Binary

4.1.8Floating Point Arithmetic

4.1.9Bitwise Manipulation

4.1.10Character Sets

4.2Data Structures

4.2.1Arrays, Linked Lists & Queues

4.2.2Graphs, Hash Tables & Stacks

4.2.3Trees

4.3Boolean Algebra

4.3.1Computational Logic

4.3.2Boolean Logic

4.3.3Karnaugh Maps

4.3.4Boolean Identities

4.3.5Flip Flops & Adder Circuits

5Legal, Moral, Cultural & Ethical Issues

5.1Computing Related Legislation

5.1.1Data Protection Act (1998)

5.1.2Computer Misuse Act (1990)

5.1.3Copyright Designs and Patents Act (1988)

5.1.4Regulation of Investigatory Powers Act (2000)

5.2Moral & Ethical Issues

5.2.1Online Activity Tracking

5.2.2Censorship

5.2.3Cultural Issues

5.2.4Environmental Issues

5.2.5Layout, Colour Paradigms & Character Sets

6Elements of Computational Thinking

6.1Thinking Abstractly

6.1.1Abstraction

6.2Thinking Procedurally

6.2.1Decomposition

6.3Thinking Logically

6.3.1Pseudocode & Flow Diagrams

7Problem Solving & Programming

7.1Programming Techniques

7.1.1Programming Fundamentals

7.1.2Modularity

7.2Programming Construction

7.2.1Integrated Development Environments

7.2.2Testing

8Algorithms

8.1Algorithms

8.1.1Interpreting, Correcting & Completing Algorithm

8.1.2Sort Algorithms

8.1.3Insertion & Merge Sort

8.1.4Search Algorithms

Jump to other topics