Transcript Binary trees, binary search trees, and tree sort

Binary Trees 2
Prof. Sin-Min Lee
Department of Computer Science
For each number of nodes, n, there is a
certain number of possible binary tree
configurations. These numbers form a
sequence of integers with respect to n. A
useful way to describe an integer
sequence is to construct a generating
function:
whose coefficients bi are the sequence.
B(x) is power series over a purely
formal variable x.
Apparently, b1 is 1, and b2 is 2. The b0 coefficient
is somewhat artificial, its the no-nodes tree which
is, I guess, the only one. Further analysis gives
the following idea: if a binary tree has n nodes,
then there must be one node as the root and two
subtrees. The total number of nodes in the
subtrees must be n-1, and either of them may be
empty. Assuming k nodes in the left subtree, the
right subtree then has n-k-1 nodes, k going from
0 to n-1. The root node is always there, and
therefore the tree configurations differ only by
the configuration of subtrees.
The total number of possible trees on n nodes
can then be expressed as:
Postorder
Template <class T>
void Postorder ( BinaryTreeNode<T> *t)
{ // Postorder traversal of *t.
If (t){
Postorder ( t->LeftChild);//do left subtree
Postorder(t->RightChild);//do right subtree
visit(t);
// visit tree root
}
}
Each root is visited after its left and right subtrees have
been traversed.
Example
+
*
a
Preorder
Inorder
Postorder
+*ab/cd
a*b+c/d
ab*cd/+
/
b
c
Elements of a binary tree listed in pre-,in-,and postorder.
d
About level order
While loop only if the tree is not empty
Following the addition of the children of t to
the queue,we attempt to delete an element
from the queue.
If the queue is empty,Delete throws an
OutOfBounds exception.
If the queue is not empty,then Delete
returns the deleted element in t.
Sample tree to illustrate tree traversal
1
2
4
8
3
5
9
6
10
11
7
12
Tree after four nodes visited in preorder
traversal
1
2
3
4
8
4
1
2
3
5
9
6
10
11
7
12
Tree after left subtree of root visited
using preorder traversal
1
2
3
4
8
2
3
6
4
9
1
5
5
7
6
10
11
7
12
Tree after completed preorder traversal
1
2
3
4
8
8
2
6
4
9
1
5
9
5
7
10
10
3
12
6
11
12
11
7
Tree visited using inorder traversal
7
4
2
1
8
11
2
5
4
9
1
3
9
5
6
10
8
3
12
6
11
12
10
7
Tree visited using postorder traversal
12
6
3
1
8
11
2
5
4
9
1
2
9
5
4
10
7
3
10
6
11
12
8
7
Here we will work through an example showing how a preorder
traversal can be obtained by explicit use of a stack. The logic
follows (see the text for the code):
1.Stack the root node.
2.Exit with completion if the stack is
empty.
3.Pop the stack and visit the node
obtained.
4.Push the right child, if it exists, on
the stack.
5.Push the left child, if it exists, on the
stack.
6.Go to 2.
Using the runtime stack via recursion, we can write simple
definitions of the three depth-first traversals without use of an
explicit
stack (in these definitions I leave out the templates for brevity):
void Preorder(TreeNode *p) {
if (p) {
Visit(p);
Preorder(p->left);
Preorder(p->right);
}
}
void Inorder(TreeNode *p) {
if (p) {
Inorder(p->left);
Visit(p);
Inorder(p->right);
}
}
void Postorder(TreeNode *p) {
if (p) {
Postorder(p->left);
Postorder(p->right);
Visit(p);
}
}
TREE SORT
Combines tree initialization, insertion, and inorder traversal to
generate and print each node in a "sorted" binary tree.
1. Initialize: read first item, create root node.
2. For each item after the first: read item and insert in tree.
3. Traverse in order, printing each node.
More formally, in pseudocode:
def treesort ()
read item
root = makebt(null, item, null)
while not end of data
read item
insert(root, item)
end while
inorder(root)
end
Using tree sort, sort the letters M, A, R, J, K,
S, V.
Insertion produces
M
/\
A R
\
\
J
S
\
\
K
V
Traverse in order => A J K M R S V