# Data Structures and Other Objects Using C++

Complete Binary Trees Data Structures and Other Objects Using C++ Chapter 10 introduces trees. This presentation illustrates the

simplest kind of trees: Complete Binary Trees. Binary Trees

A binary tree has nodes, similar to nodes in a linked list structure. Data of one sort or another may be stored at each node. But it is the connections between the nodes which characterize a binary tree. Binary Trees

A binary tree has nodes, similar to nodes in a linked list structure. Data of one sort or another may be stored at each node. But it is the connections between the nodes which characterize a binary tree.

An example can illustrate how the connections work A Binary Tree of States In this example, the data contained at each node is one of the 50

states. A Binary Tree of States Each tree has a special node called its root, usually drawn at the top. A Binary Tree of States

Each tree has a special node called its root, usually drawn at the top. The example tree has Washington as its root.

A Binary Tree of States Each node is permitted to have two links to other nodes, called the left child and the right child. A Binary Tree of States

Each node is permitted to have two links to other nodes, called the left child and the right child. A Binary Tree of States Children are

usually drawn below a node. The left child of Washington is Arkansas. The right child of Washington is Colorado.

A Binary Tree of States Some nodes have only one child. Arkansas has a left child, but no right child. A Quiz

Some nodes have only one child. Which node has only a right child? A Quiz

Some nodes have only one child. Florida has only a right child. A Binary Tree of States A node with no children is

called a leaf. A Binary Tree of States Each node is called the parent of its children. Washington is the parent of Arkansas and Colorado.

A Binary Tree of States Two rules about parents: The root has no parent. Every other node has exactly one parent. A Binary Tree of States

Two nodes with the same parent are called siblings. Arkansas and Colorado are siblings. Complete Binary Trees A complete

binary tree is a special kind of binary tree which will be useful to us. Complete Binary Trees A complete binary tree is a special kind of

binary tree which will be useful to us. When a complete binary tree is built, its first node must be the root. Complete Binary Trees

The second node of a complete binary tree is always the left child of the root... Complete Binary Trees The second node of a complete binary tree is always the left child of the root...

... and the third node is always the right child of the root. Complete Binary Trees The next nodes must always fill the next level from left to

right. Complete Binary Trees The next nodes must always fill the next level from left to right.

Complete Binary Trees The next nodes must always fill the next level from left to right. Complete Binary Trees The next

nodes must always fill the next level from left to right. Complete Binary Trees The next nodes must always fill

the next level from left to right. Complete Binary Trees The next nodes must always fill the next level from left to

right. Is This Complete? Is This Complete? Is This Complete? Is This Complete?

Is This Complete? Yes! It is called the empty tree, and it has no nodes, not even a root. Implementing a Complete Binary Tree

We will store the date from the nodes in a partially-filled array. 3 An integer to keep track of how many nodes are in the tree An array of data We don't care what's in

this part of the array. Implementing a Complete Binary Tree We will store the date from the nodes in a partially-filled array. 3

An integer to keep track of how many nodes are in the tree Read Section 10.2 to see details of how An array of datathe entries are stored. We don't care what's in this part of the array. Summary

Binary trees contain nodes. Each node may have a left child and a right child.

If you start from any node and move upward, you will eventually reach the root. Every node except the root has one parent. The root has no parent. Complete binary trees require the nodes to fill in each level from left-to-right before starting the next level. Presentation copyright 2004 Addison Wesley Longman, For use with Data Structures and Other Objects Using Java

by Michael Main. Some artwork in the presentation is used with permission from Presentation Task Force (copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright Corel Corporation, 3G Graphics Inc, Archive Arts, Cartesia Software, Image Club Graphics Inc, One Mile Up Inc, TechPool Studios, Totem Graphics Inc). Students and instructors who use Data Structures and Other Objects Using C++ are welcome to use this presentation however they see fit, so long as this copyright notice remains intact. THE END

## Recently Viewed Presentations

• *Taxable Compensation = Income that is subject to federal income, social security, Medicare and FUTA taxes and remitted to the proper tax authority. Many types of compensation can be subject to one or more of these taxes. Income and Employment...
• Based on these measurements, is it likely that the metal you found is gold? (A = 5) 13) Draw Bohr-Rutherford diagrams for the following: (A = 12) a) Phosphorus b) An element which has 3 electrons in the third orbital...
• Igneous Rocks Chapter 14 - Section 2 Where do igneous rocks come from? Magma cools and then solidifies (hardens). Igneous rocks are known as "fire rocks". Composition: When fluids such as water combine with rock, the composition of the rock...
• Professor Myra Hunter ... in line with these needs, from low to high levels of intensity. In our service we offer a range of interventions, including psycho-education sessions for all patients attending rehab, to group workshops and brief therapy for...
• Using Altera FPGAs to Implement Wide Dynamic Range (WDR) Image Sensor Pipelines (ISP) and Video Analytics 2010 Technology Roadshow This slide show the IP pilpeline from headend/ sensor side to the backend side Displays from left to the right We...
• Christ's Appearance To John. Revelation 1:9-20. ... to break bread, Paul, ready to depart the next day, spoke to them and continued his message until midnight." ... He comforts him with the "meaning" of the symbols (v. 20) These things...
• Formerly a part of the kingdom monera Name means "true bacteria" These are the kind of bacteria likely to make us sick, live in our gut to help us digest food, or be used in the making of cheese Bacilli...
• Thenet income of a company that uses LIFO is less likely to be affected by decline in price in future. Usually, the companies using LIFO method do not have much inventory at current higher prices because, under this method, most...