Chapter 10. Data Abstraction & Problem Solving with C++, Fifth Edition. by Frank M.
Carrano
Trees are composed of nodes and edges Trees are hierarchical
Parent-child relationship between two nodes Ancestor-descendant relationships among nodes
Subtree of a tree: Any node and its descendants
Figure 10-2 Figure 10-1 A general tree A subtree of the tree in Figure 10-1
General tree
A general tree T is a set of one or more nodes such that T is partitioned into disjoint subsets:
A single node r, the root Sets that are general trees, called subtrees of r
Parent of node n
The node directly above node n in the tree
A node directly below node n in the tree The only node in the tree with no parent A tree that consists of a child (if any) of node n and the childs descendants
Child of node n
Root
Subtree of node n
Leaf
A node with no children
Nodes with a common parent A node on the path from the root to n A node on a path from n to a leaf
Siblings
Ancestor of node n
Descendant of node n
A binary tree is a set T of nodes such that either
T is empty, or T is partitioned into three disjoint subsets:
A single node r, the root Two possibly empty sets that are binary trees, called
the left subtree of r and the right subtree of r
Figure 10-3 (a) An organization chart; (b) a family tree
Figure 10-4 Binary trees that represent algebraic expressions
A binary search tree
A binary tree that has the following properties for each node n
ns value is > all values in ns left subtree TL ns value is < all values in ns right subtree TR Both TL and TR are binary search trees
Figure 10-5 A binary search tree of names
Height of a tree
Number of nodes along the longest path from the root to a leaf
Height 3 Height 5 Height 7
Figure 10-6 Binary trees with the same nodes but different heights
Level of a node n in a tree T
If n is the root of T, it is at level 1 If n is not the root of T, its level is 1 greater than the level of its parent
Height of a tree T defined in terms of the levels of its nodes
If T is empty, its height is 0 If T is not empty, its height is equal to the maximum level of its nodes
A recursive definition of height
If T is empty, its height is 0 If T is not empty, height(T) = 1 + max{height(TL), height(TR)} r / \ TL TR
A binary tree of height h is full if
Nodes at levels < h have two children each
Recursive definition
If T is empty, T is a full binary tree of height 0 If T is not empty and has height h > 0, T is a full binary tree if its roots subtrees are both full binary trees of height h 1
Figure 10-7 A full binary tree of height 3
A binary tree of height h is complete if
It is full to level h 1, and Level h is filled from left to right
Figure 10-8 A complete binary tree
Another definition: A binary tree of height h is complete if
All nodes at levels <= h 2 have two children each, and When a node at level h 1 has children, all nodes to its left at the same level have two children each, and When a node at level h 1 has one child, it is a left child
A binary tree is balanced if the heights of any nodes two subtrees differ by no more than 1 Complete binary trees are balanced Full binary trees are complete and balanced
The balance factor of a binary tree is the difference in height between it left and right sub-trees. Let :
height of left sub-tree be HL and height of right sub-tree be HR Then the Balance factor (B) = HL -HR
General: Operations that
Insert data into a data collection Delete data from a data collection Ask questions about the data in a data collection
Position-oriented ADTs: Operations that
Insert data into the ith position Delete data from the ith position Ask a question about the data in the ith position Examples: list, stack, queue, binary tree
Value-oriented ADTs: Operations that
Insert data according to its value Delete data knowing only its value Ask a question about data knowing only its value Examples: sorted list, binary search tree
A full binary tree of height h 0 has 2h 1 nodes The maximum number of nodes that a binary tree of height h can have is 2h 1 The minimum height of a binary tree with n nodes is log2(n+1) Complete trees and full trees have minimum height The maximum height of a binary tree with n nodes is n
Figure 10-32 Counting the nodes in a full binary tree of height h
In the following recursive definition of the maximum number of nodes based on the height of a binary tree. Replace the question mark with the proper value.
What information is needed to represent a binary tree? What is it composed of?
For every node in the tree we should keep track of:
Data Left sub-tree Right sub-tree
Write a C++ structure that could represent a binary tree node
Some array-based representations for binary trees exists. can you think of any?
Tree traversal requires that each node of the tree gets examined (processed or visit) once in a pre-defined sequence. Two general approaches are:
Depth first search (DFS) Breadth first search (BFS)
Process all the descendents of a child before going to the next child. There are three tasks that are performed when traversing:
Visit (V) Traverse Left (L) Traverse Right (R)
Preorder traversal (VLR) Inorder Traversal (LVR) Postorder Traversal (LRV)
Preorder (node* root) if(root != NULL) visit(root->data) Preorder(root->left) Preorder(root->right)
Inorder (node* root) if(root != NULL) Inorder (root->left) visit(root->data) Inorder (root->right)
Postorder (node* root) if(root != NULL) Postorder (root->left) Postorder (root->right) visit(root->data)
Visit each node level by level What data structure can be used?
Level-order (node* root) queue Q Enqueue(root) while( Q is not empty) enqueue(children of root) dequeue(head) visit(head->data)
