Skip to main content
ICT
Lesson AB30 - Binary Search Trees
 
Main Previous Next
Title Page >  
Summary >  
Lesson A1 >  
Lesson A2 >  
Lesson A3 >  
Lesson A4 >  
Lesson A5 >  
Lesson A6 >  
Lesson A7 >  
Lesson A8 >  
Lesson A9 >  
Lesson A10 >  
Lesson A11 >  
Lesson A12 >  
Lesson A13 >  
Lesson A14 >  
Lesson A15 >  
Lesson A16 >  
Lesson A17 >  
Lesson A18 >  
Lesson A19 >  
Lesson A20 >  
Lesson A21 >  
Lesson A22 >  
Lesson AB23 >  
Lesson AB24 >  
Lesson AB25 >  
Lesson AB26 >  
Lesson AB27 >  
Lesson AB28 >  
Lesson AB29 >  
Lesson AB30 >  
Lesson AB31 >  
Lesson AB32 >  
Lesson AB33 >  
Vocabulary >  
 

A. Binary Tree Vocabulary page 3 of 15

  1. A binary tree is a data structure where each node has two pointers, each pointing to another node or containing a null value.

  2. The following binary tree terms will be defined and applied to the above example.

    1. Root node - the top node in the tree; the node whose value is 52.

    2. Parent node - a node that points to one or two nodes below it.

    3. Child node - the node being pointed to by a parent; every node in the tree is a child to another node, except for the root node.

    4. Leaf - a node that has no children

    5. Level - the distance from the root, calculated by counting the shortest distance from the root to that node. Examples: 29 is stored in a node at level 1, 62 is stored in a node at level 2, 17 is stored at level 3, etc.

    6. Edge - an edge joins two nodes. In the above diagram, each arrow represents an edge.

  3. This tree is an example of an ordered binary tree that has the following property. For every parent node, a child to the right will have a larger value, while a child to the left will have a smaller value.

  4. A subtree is the entire left branch or right branch of a node. For example, the left subtree of the node containing 52 has 4 nodes. The right subtree of node containing 75 has only 1 node.

  5. A leaf will have two null pointers.

 

Main Previous Next
Contact
 © ICT 2006, All Rights Reserved.