Chapter 8
Binary and other trees
Two kinds of data structure
? Linear,list,stack,queue,string
? Non-linear,tree,graph
8.1 Tree
1.Definition,A tree T is a finite nonempty set
of elements,One of these elements is called
the root,and the remaining elements(if any)
are partitioned into trees which are called
the subtrees of T.
8.1 Tree
? example A
B C D
E F G H I J
K L M
8.1 Tree
2.Terminology
? Degree of an elememts,the number of children
it has.
? Degree of a tree,the maximum of its element
degrees
? Leaf,element whose degree is 0
? Branch,element whose degree is not 0
8.1 Tree
? Level,
the level of root is 1
the level of an element=the level of its parent+1
? Depth of a tree,
the maximum level of its elements
8.2 Binary Trees
1.Definition,A binary tree t is a finite
(possibly empty) collection of elements,
When the binary tree is not empty:
? It has a root element
? The remaining elements(if any) are
partitioned into two binary trees,which are
called the left and right subtrees of t,
8.2 Binary Trees
2.The essential differences between a binary
tree and a tree are:
1)A binary tree can be empty,whereas a tree
cannot.
2)Each element in a binary tree has exactly
two subtrees(one or both of these subtrees
may be empty).Each element in a tree can
have any number of subtrees.
8.2 Binary Trees
3) The subtrees of each element in a binary
tree are ordered,That is,we distinguish
between the left and the right subtrees.The
subtrees in a tree are unordered.
8.2 Binary Trees
? Example of a binary tree
+
* /
a b c d
8.3 Properties of binary trees
Property 1,The drawing of every binary tree
with n elements,n>0,has exactly n-1 edges.
Property 2,The number of elements at level i
is at most 2i-1 (i>=1).
8.3 Properties of binary trees
Property 3,A binary tree of height h,h>=0,
has at least h and at most 2h –1 elements in
it.
proof of property 3:
? 2i-1=20+21+……+2 h-1=1*(1-2h)/(1-2)=2h –1i-1
h
8.3 Properties of binary trees
Property 4.The height of a binary tree that
contains n,n>=0,element is at most n and at
least ?log2(n+1)?
proof,Since there must be at least one element
at each level,the height cannot exceed n,
From property 3,we know n<=2h-1,
so,h>=log2(n+1),since h is an integer,we get
h>=?log2(n+1)?
8.3 Properties of binary trees
Property 5,If number of leaves is n0,and the
number of the 2 degree elements is n2,then
n0=n2+1,
8.3 Properties of binary trees
? Definition of a full binary tree, A binary
tree of height h that contains exactly 2h-1
elements is called a full binary tree.
8.3 Properties of binary trees
? Definition of a complete binary tree,
suppose we number the elements in a full
binary tree of height h using the number 1
through 2h-1.We began at level 1 and go
down to level h.Within levels the elements
are numbered left to right.Suppose we
delete the k elements numbered 2h-i,
1<=i<=k,the resulting binary tree is called a
complete binary tree.
8.3 Properties of binary trees
? Example of complete binary trees
1
2 3
654 4
32
1
2
1
8.3 Properties of binary trees
Property 6,Let i,1<=i<=n,be the number
assigned to an element of a complete binary
tree,The following are true.
1).If i=1,then this element is the root of the
binary tree,If i>1,then the parent of this
element has been assigned the number ?i/2?
2).If 2i>n,then this element has no left child,
Otherwise,its left child has been assigned the
number 2i.
8.3 Properties of binary trees
3)If 2i+1>n,then this element has no right
child,Otherwise its right child has been
assigned the number 2i+1.
8.4 Representation of binary tree
1.Formula-Based Representation (array
representation)
? The binary tree to be representated is
regarded as a complete binary tree with
some missing elements.
8.4 Representation of binary tree
? Example of a complete binary tree (array
representation)
31 23 12 66 94 05 17 70
31
23 12
66 94 05
70
17
0 1 2 3 4 5 6 7
8.4 Representation of binary tree
? Example of a common binary tree(array
representation)
31
23 12
66 05
70
17
88
31 23 12 66 05 17 70 88
0 1 2 3 4 5 6 7 8 9 10 11 12
8.4 Representation of binary tree
2,Linked representation( also called L-R
linked storage)
? The node structure:
leftChild data rightChild
8.4 Representation of binary tree
? Example
A
B
C D
E F
G
A ^
B
F ^^ E ^
D^ C ^
^ G ^
8.4 Representation of binary tree
? Represented by simulating pointers
data leftchild rightchild
A 1 -1
B 2 3
C -1 -1
D 4 5
E -1 6
F -1 -1
G -1 -1
0
1
2
3
4
5
6
8.4 Representation of binary tree
? Node class for linked binary trees
template<class T>
class BianryTreeNode{
public,
BinaryTreeNode(){LeftChild=RightChild=0;}
BinaryTreeNode(const T& e)
{data=e; LeftChild=RightChild=0;}
8.4 Representation of binary tree
BinaryTreeNode(const T& e,
BinaryTreeNode* l,BinaryTreeNode* r)
{data=e; LeftChild=l; RightChild=r; }
private:
T data;
BinaryTreeNode<T>*LeftChild,//left subtree
*RightChild; //right subtree
};
8.5 Common binary tree
operations
? Determine the height of a binary tree
? Determine the number of its elements
? Make a copy
? Delete the tree
8.6 Binary Tree Traversal
Each element is visited exactly once
? Preorder
? Inorder
? Postorder
? Level order
8.6 Binary Tree Traversal
? Example of binary tree traversal
A
B C
D E F
IHG
Preorder,ABDCEGFHI
Inorder, DBAEGCHFI
Postorder,DBGEHIFCA
Level order,ABCDEFGHI
8.6 Binary Tree Traversal
? Preorder traversal (program 8.2)
template<class T>
void PreOrder(BinaryTreeNode<T>* t)
{// preorder traversal of *t.
if(t){
Visit(t);
PreOrder(t?LeftChild);
PreOrder(t?RightChild);}
}
8.6 Binary Tree Traversal
? Inorder traversal (program 8.3)
template<class T>
void InOrder(BinaryTreeNode<T>* t)
{ if(t){
InOrder(t?LeftChild);
visit(t);
InOrder(t?RightChild);}
}
8.6 Binary Tree Traversal
? Postorder traversal
template<class T>
void PostOrder(BinaryTreeNode<T>* t)
{if(t){
PostOrder(t?LeftChild);
PostOrder(t?RightChild);
visit(t);}
}
模拟中序递归过程
8.6 Binary Tree Traversal
? Level order (program 8.6)
it is a non-recursive function and a queue is used.
A
B C
D E F
IHG
A B C D E GF IH
8.6 Binary Tree Traversal
? Level order (program 8.6)
template<class T>
void LevelOrder(BinaryTreeNode<T>* t)
{ LinkedQueue<BinaryTreeNode<T>* Q;
while(t){
Visit(t); //visit t
8.6 Binary Tree Traversal
//put t’s children on queue
if(t?LeftChild) Q.Add(t?LeftChild);
if(t?RightChild) Q.Add(t?RightChild);
//get next node to visit
try{Q.Delete(t);}
catch(OutOfBounds){return;}
}
}
8.7 The ADT BinaryTree
ADT 8-1 the abstract data type binary tree
? Create()
? IsEmpty()
? Root(x)
? MakeTree(root,left,right)
? BreakTree(root,left,right)
? PreOrder
8.7 The ADT BinaryTree
? InOrder
? PostOrder
? LevelOrder
8.8 The Class BinaryTree
1.Binary tree class (program 8.7)
template<class T>
class BinaryTree{
public:
BinaryTree(){root=0;};
~BinaryTree(){};
bool IsEmpty()const
{return ((root)?false:true);}
8.8 The Class BinaryTree
bool Root(T& x)const;
void MakeTree(const T& element,
BinaryTree<T>& left,BinaryTree<T>& right);
void BreakTree(T& element,BinaryTree<T>& left,
BinaryTree<T>& right);
void PreOrder(void(*Visit)(BinaryTreeNode<T>*u))
{PreOrder(Visit,root);}
void InOrder(void(*Visit)(BinaryTreeNode<T>*u))
{InOrder(Visit,root);}
8.8 The Class BinaryTree
void PostOrder (void(*Visit)(BinaryTreeNode<T>*u))
{PostOrder(Visit,root);}
void LevelOrder
(void(*Visit)(BinaryTreeNode<T> *u));
private:
BinaryTreeNode<T>* root;
void PreOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
8.8 The Class BinaryTree
void InOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
void PostOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
};
? In this class,we employ a linked representation for
binary trees.
? The function visit is used as parameter to the traversal
methods,so that different operations can be implemented
easily
8.8 The Class BinaryTree
2.Implementation of some member functions
? Program 8.8
Template<class T>
void BinaryTree<T>::MakeTree(const T& element,
BinaryTree<T>& left,BinaryTree<T>& right)
{//combine left,right and element to make new tree.
//left,right and this must be different trees.
//create combined tree
8.8 The Class BinaryTree
root=new BinaryTreeNode<T>(element,left.root,
right.root);
//deny access from trees left and right
left.root=right.root=0;
}
8.8 The Class BinaryTree
template<class T>
void BinaryTree<T>::BreakTree(T& element,
BinaryTree<T>& left,BinaryTree<T>& right)
{//left,right,and this must be different trees.
//check if empty
if(!root)throw BadInput(); //tree empty
8.8 The Class BinaryTree
//break the tree
element=root?data;
left.root=root?LeftChild;
right.root=root?RightChild;
delete root;
root=0;
}
8.8 The Class BinaryTree
? Program 8.9
template<class T>
voidBinaryTree<T>::PreOrder ( void(*Visit)
(BinaryTree<T>*u),BinaryTree<T>*t)
{//Preorder traversal.
if(t) {Visit(t);
PreOrder(Visit,t?LeftChild);
PreOrder(Visit,t?RightChild);}
}
后根遍历、中根遍历的非递归算法：
8.8 The Class BinaryTree
3.Application of class BinaryTree (program
8.11)
#include<iostream.h>
#include,binary.h”
int count=0;
BinaryTree<int>a,x,y,z;
8.8 The Class BinaryTree
template<class T>
void ct(BinaryTreeNode<T>*t){count++;}
void main(void)
{y.MakeTree(1,a,a);
z.MakeTree(2,a,a);
x.MakeTree(3,y,z);
y.MakeTree(4,x,a);
y.PreOrder(ct);
cout<<count<<endl;
}
补充字符串、广义表、建立二叉树的算法
8.9 ADT and Class Extensions
? PreOutput():output the data fields in preorder
? InOutput():output the data fields in inorder
? PostOutput():output the data fields in postorder
? LevelOutput():output the data fields in level order
? Delete():delete a binary tree,freeing up its nodes
? Height():return the tree height
? Size():return the number of nodes in the tree
8.9 ADT and Class Extensions
? The height of the tree is determined as:
max{hl,hr}+1
? Program 8.12
template<class T>
int BinaryTree<T>::Height(BinaryTreeNode<T> *t)const
{if(!t) return 0;
int hl=Height(t?LeftChild);
int hr=Height(t?RightChild);
if(hl>hr)return ++ hl;
else return ++hr;}
8.10 Application
Take a tree as a binary tree
a
b c d e
f g h i j
a
b c
d e
f
g h
i
jFirstchild data nextSibling
1.Binary-Tree Representation of a Tree
树中插入一个新结点：
2,Equivalence Class
1).Definition of Equivalence Class:
Suppose we have a set U={1,2,…,n} of n
elements and a set R={(i1,j1),(i2,j2)……
(ir,jr)}of r relations,The relation R is an
equivalence relation iff the following
conditions are true(symbol’?’ represent the
equivalence relation on sets,x,y,z are elements
in set ),
2,Equivalence Class
? Reflexive x ?x.
? Symmetric x ?y,y ?x
? Transitive x ?y and y ?z,then x ?z
2),Example set s= {0,1,2,3,4,5,6,7,8,9,10,11}
pairs of equivalence:
(0 4),(3 1),(6 10),(8 9),(7 4),(6 8),(3 5),(2 11),(11 0)
Initial:{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}，
{10},{11}
0?4 {0,4},{1},{2},{3},{4},{5},{6},{7},{8},{9}，
{10},{11}
3 ?1 {0,4},{1,3},{2},{4},{5},{6},{7},{8},{9}，
{10},{11}
2,Equivalence Class
2,Equivalence Class
6 ?10 {0,4},{1,3},{2},{4},{5},{6,10},{7}，
{8},{9},{11}
8 ?9 {0,4},{1,3},{2},{4},{5},{6,10},{7},{8，
9},{11}
7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9}，
{11}
6 ? 8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11}
3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11}
2 ? 11 {0,4,7},{1,3,5},{2,11},{6,8,9,10}
11 ? 0 {0,4,7,2,11},{1,3,5},{6,8,9,10}
2,Equivalence Class
3),Online equivalence class operation
? Combine(a,b), combine the equivalence
classes that contains elements a and b into
a single class
? Find(e), determine the class that currently
contains element e.
Combine(a,b) is equivalent to i=Find(a);
j=Find(b); if(i!=j) Union(i,j);
2,Equivalence Class
4).Tree Representation(Union-Find sets)
? Example,
S1={1,7,8,9},S2={5,2,10},S3={3,4,6},they
all belong to S={1,2,3,……,10}
1
7 8 9 2 10
5
64
3
0 5 0 3 0 3 1 1 1 5parent
0 1 2 3 4 5 6 7 8 9 10
2,Equivalence Class
Program 8.15 simple tree solution to union-find
problem
void Initialize(int n)
{parent=new int[n+1];
for(int e=1;e<n;e++)
parent[e]=0;
}
2,Equivalence Class
int Find(int e)
{while(parent[e])
e=parent[e];
return e;
}
void Union(int i,int j)
{parent[j]=i;
}
2,Equivalence Class
5).Performance Evaluation
Time complexity,Find-- O(h),Union-- ?(1)
Assume that u times unions and f times finds are to be
performed,f>u,in the worst case a tree with m
elements can have a height of m:
Union(2,1),Union(3,2),Union(4,3),Union(5,4)…
Hence each find can take as much as ?(q) time where q is
the number of unions that have been performed
before the find.
2,Equivalence Class
6).Performance Enhancement
?improve Union in order to decrease the
time each find take,so that the height of
tree will not increase linearly,
2,Equivalence Class
two rules:
? Weight rule,if the number of nodes in tree i
is less than the number in tree j,then make j
the parent of i; otherwise,make i the parent
of j.
? Height rule,if the height of tree i is less
than that of tree j,then make j the parent of
i; otherwise,make i the parent of j,
2,Equivalence Class
? Let’s discuss the weight rule,
Parent[5]=1
Parent[1]=7
1
7 8 9 2 10
5 1
7 8 9 5
2 10
Union(1,5)
Besides the parent field,each node has a boolean field
root,The root field is true iff the node is presently a
root node.The parent field of each node is used to keep
a count of the total number of nodes in the tree.
2,Equivalence Class
? Program 8.16 Union with the weight rule
void Initialize(int n)
{ root=new bool[n+1];
parent=new int[n+1];
for(int e=1;e<=n;e++)
{ parent[e]=1;
root[e]=true;
}
2,Equivalence Class
int Find(int e)
{while(!root[e])
e=parent[e];
return e;
}
2,Equivalence Class
void Union(int i,int j)
{if(parent[i]<parent[j]) // i becomes subtree of j
{parent[j]=parent[j]+parent[i];
root[i]=false;
parent[i]=j;
}
else {parent[i]=parent[i]+parent[j];
root[j]=false;
parent[j]=i;
}
}
2,Equivalence Class
?.Improvement of Find –path compression
When processing a equivalence pair,we need to
operate Find twice,WeightUnion once.
Example of improvement:
1
7 8 9
2 10
4 6
1
7 8 910 6
42Find(6)
2,Equivalence Class
int Find( int e)
{ int j=e;
while(!root[j]) j=parent[j];
int f=e;
while(f!=j)
{int pf=parent[f]; parent[f]=j; f=pf;
}
Binary and other trees
Two kinds of data structure
? Linear,list,stack,queue,string
? Non-linear,tree,graph
8.1 Tree
1.Definition,A tree T is a finite nonempty set
of elements,One of these elements is called
the root,and the remaining elements(if any)
are partitioned into trees which are called
the subtrees of T.
8.1 Tree
? example A
B C D
E F G H I J
K L M
8.1 Tree
2.Terminology
? Degree of an elememts,the number of children
it has.
? Degree of a tree,the maximum of its element
degrees
? Leaf,element whose degree is 0
? Branch,element whose degree is not 0
8.1 Tree
? Level,
the level of root is 1
the level of an element=the level of its parent+1
? Depth of a tree,
the maximum level of its elements
8.2 Binary Trees
1.Definition,A binary tree t is a finite
(possibly empty) collection of elements,
When the binary tree is not empty:
? It has a root element
? The remaining elements(if any) are
partitioned into two binary trees,which are
called the left and right subtrees of t,
8.2 Binary Trees
2.The essential differences between a binary
tree and a tree are:
1)A binary tree can be empty,whereas a tree
cannot.
2)Each element in a binary tree has exactly
two subtrees(one or both of these subtrees
may be empty).Each element in a tree can
have any number of subtrees.
8.2 Binary Trees
3) The subtrees of each element in a binary
tree are ordered,That is,we distinguish
between the left and the right subtrees.The
subtrees in a tree are unordered.
8.2 Binary Trees
? Example of a binary tree
+
* /
a b c d
8.3 Properties of binary trees
Property 1,The drawing of every binary tree
with n elements,n>0,has exactly n-1 edges.
Property 2,The number of elements at level i
is at most 2i-1 (i>=1).
8.3 Properties of binary trees
Property 3,A binary tree of height h,h>=0,
has at least h and at most 2h –1 elements in
it.
proof of property 3:
? 2i-1=20+21+……+2 h-1=1*(1-2h)/(1-2)=2h –1i-1
h
8.3 Properties of binary trees
Property 4.The height of a binary tree that
contains n,n>=0,element is at most n and at
least ?log2(n+1)?
proof,Since there must be at least one element
at each level,the height cannot exceed n,
From property 3,we know n<=2h-1,
so,h>=log2(n+1),since h is an integer,we get
h>=?log2(n+1)?
8.3 Properties of binary trees
Property 5,If number of leaves is n0,and the
number of the 2 degree elements is n2,then
n0=n2+1,
8.3 Properties of binary trees
? Definition of a full binary tree, A binary
tree of height h that contains exactly 2h-1
elements is called a full binary tree.
8.3 Properties of binary trees
? Definition of a complete binary tree,
suppose we number the elements in a full
binary tree of height h using the number 1
through 2h-1.We began at level 1 and go
down to level h.Within levels the elements
are numbered left to right.Suppose we
delete the k elements numbered 2h-i,
1<=i<=k,the resulting binary tree is called a
complete binary tree.
8.3 Properties of binary trees
? Example of complete binary trees
1
2 3
654 4
32
1
2
1
8.3 Properties of binary trees
Property 6,Let i,1<=i<=n,be the number
assigned to an element of a complete binary
tree,The following are true.
1).If i=1,then this element is the root of the
binary tree,If i>1,then the parent of this
element has been assigned the number ?i/2?
2).If 2i>n,then this element has no left child,
Otherwise,its left child has been assigned the
number 2i.
8.3 Properties of binary trees
3)If 2i+1>n,then this element has no right
child,Otherwise its right child has been
assigned the number 2i+1.
8.4 Representation of binary tree
1.Formula-Based Representation (array
representation)
? The binary tree to be representated is
regarded as a complete binary tree with
some missing elements.
8.4 Representation of binary tree
? Example of a complete binary tree (array
representation)
31 23 12 66 94 05 17 70
31
23 12
66 94 05
70
17
0 1 2 3 4 5 6 7
8.4 Representation of binary tree
? Example of a common binary tree(array
representation)
31
23 12
66 05
70
17
88
31 23 12 66 05 17 70 88
0 1 2 3 4 5 6 7 8 9 10 11 12
8.4 Representation of binary tree
2,Linked representation( also called L-R
linked storage)
? The node structure:
leftChild data rightChild
8.4 Representation of binary tree
? Example
A
B
C D
E F
G
A ^
B
F ^^ E ^
D^ C ^
^ G ^
8.4 Representation of binary tree
? Represented by simulating pointers
data leftchild rightchild
A 1 -1
B 2 3
C -1 -1
D 4 5
E -1 6
F -1 -1
G -1 -1
0
1
2
3
4
5
6
8.4 Representation of binary tree
? Node class for linked binary trees
template<class T>
class BianryTreeNode{
public,
BinaryTreeNode(){LeftChild=RightChild=0;}
BinaryTreeNode(const T& e)
{data=e; LeftChild=RightChild=0;}
8.4 Representation of binary tree
BinaryTreeNode(const T& e,
BinaryTreeNode* l,BinaryTreeNode* r)
{data=e; LeftChild=l; RightChild=r; }
private:
T data;
BinaryTreeNode<T>*LeftChild,//left subtree
*RightChild; //right subtree
};
8.5 Common binary tree
operations
? Determine the height of a binary tree
? Determine the number of its elements
? Make a copy
? Delete the tree
8.6 Binary Tree Traversal
Each element is visited exactly once
? Preorder
? Inorder
? Postorder
? Level order
8.6 Binary Tree Traversal
? Example of binary tree traversal
A
B C
D E F
IHG
Preorder,ABDCEGFHI
Inorder, DBAEGCHFI
Postorder,DBGEHIFCA
Level order,ABCDEFGHI
8.6 Binary Tree Traversal
? Preorder traversal (program 8.2)
template<class T>
void PreOrder(BinaryTreeNode<T>* t)
{// preorder traversal of *t.
if(t){
Visit(t);
PreOrder(t?LeftChild);
PreOrder(t?RightChild);}
}
8.6 Binary Tree Traversal
? Inorder traversal (program 8.3)
template<class T>
void InOrder(BinaryTreeNode<T>* t)
{ if(t){
InOrder(t?LeftChild);
visit(t);
InOrder(t?RightChild);}
}
8.6 Binary Tree Traversal
? Postorder traversal
template<class T>
void PostOrder(BinaryTreeNode<T>* t)
{if(t){
PostOrder(t?LeftChild);
PostOrder(t?RightChild);
visit(t);}
}
模拟中序递归过程
8.6 Binary Tree Traversal
? Level order (program 8.6)
it is a non-recursive function and a queue is used.
A
B C
D E F
IHG
A B C D E GF IH
8.6 Binary Tree Traversal
? Level order (program 8.6)
template<class T>
void LevelOrder(BinaryTreeNode<T>* t)
{ LinkedQueue<BinaryTreeNode<T>* Q;
while(t){
Visit(t); //visit t
8.6 Binary Tree Traversal
//put t’s children on queue
if(t?LeftChild) Q.Add(t?LeftChild);
if(t?RightChild) Q.Add(t?RightChild);
//get next node to visit
try{Q.Delete(t);}
catch(OutOfBounds){return;}
}
}
8.7 The ADT BinaryTree
ADT 8-1 the abstract data type binary tree
? Create()
? IsEmpty()
? Root(x)
? MakeTree(root,left,right)
? BreakTree(root,left,right)
? PreOrder
8.7 The ADT BinaryTree
? InOrder
? PostOrder
? LevelOrder
8.8 The Class BinaryTree
1.Binary tree class (program 8.7)
template<class T>
class BinaryTree{
public:
BinaryTree(){root=0;};
~BinaryTree(){};
bool IsEmpty()const
{return ((root)?false:true);}
8.8 The Class BinaryTree
bool Root(T& x)const;
void MakeTree(const T& element,
BinaryTree<T>& left,BinaryTree<T>& right);
void BreakTree(T& element,BinaryTree<T>& left,
BinaryTree<T>& right);
void PreOrder(void(*Visit)(BinaryTreeNode<T>*u))
{PreOrder(Visit,root);}
void InOrder(void(*Visit)(BinaryTreeNode<T>*u))
{InOrder(Visit,root);}
8.8 The Class BinaryTree
void PostOrder (void(*Visit)(BinaryTreeNode<T>*u))
{PostOrder(Visit,root);}
void LevelOrder
(void(*Visit)(BinaryTreeNode<T> *u));
private:
BinaryTreeNode<T>* root;
void PreOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
8.8 The Class BinaryTree
void InOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
void PostOrder(void(*Visit)
(BinaryTreeNode<T> *u),BinaryTreeNode<T>*t);
};
? In this class,we employ a linked representation for
binary trees.
? The function visit is used as parameter to the traversal
methods,so that different operations can be implemented
easily
8.8 The Class BinaryTree
2.Implementation of some member functions
? Program 8.8
Template<class T>
void BinaryTree<T>::MakeTree(const T& element,
BinaryTree<T>& left,BinaryTree<T>& right)
{//combine left,right and element to make new tree.
//left,right and this must be different trees.
//create combined tree
8.8 The Class BinaryTree
root=new BinaryTreeNode<T>(element,left.root,
right.root);
//deny access from trees left and right
left.root=right.root=0;
}
8.8 The Class BinaryTree
template<class T>
void BinaryTree<T>::BreakTree(T& element,
BinaryTree<T>& left,BinaryTree<T>& right)
{//left,right,and this must be different trees.
//check if empty
if(!root)throw BadInput(); //tree empty
8.8 The Class BinaryTree
//break the tree
element=root?data;
left.root=root?LeftChild;
right.root=root?RightChild;
delete root;
root=0;
}
8.8 The Class BinaryTree
? Program 8.9
template<class T>
voidBinaryTree<T>::PreOrder ( void(*Visit)
(BinaryTree<T>*u),BinaryTree<T>*t)
{//Preorder traversal.
if(t) {Visit(t);
PreOrder(Visit,t?LeftChild);
PreOrder(Visit,t?RightChild);}
}
后根遍历、中根遍历的非递归算法：
8.8 The Class BinaryTree
3.Application of class BinaryTree (program
8.11)
#include<iostream.h>
#include,binary.h”
int count=0;
BinaryTree<int>a,x,y,z;
8.8 The Class BinaryTree
template<class T>
void ct(BinaryTreeNode<T>*t){count++;}
void main(void)
{y.MakeTree(1,a,a);
z.MakeTree(2,a,a);
x.MakeTree(3,y,z);
y.MakeTree(4,x,a);
y.PreOrder(ct);
cout<<count<<endl;
}
补充字符串、广义表、建立二叉树的算法
8.9 ADT and Class Extensions
? PreOutput():output the data fields in preorder
? InOutput():output the data fields in inorder
? PostOutput():output the data fields in postorder
? LevelOutput():output the data fields in level order
? Delete():delete a binary tree,freeing up its nodes
? Height():return the tree height
? Size():return the number of nodes in the tree
8.9 ADT and Class Extensions
? The height of the tree is determined as:
max{hl,hr}+1
? Program 8.12
template<class T>
int BinaryTree<T>::Height(BinaryTreeNode<T> *t)const
{if(!t) return 0;
int hl=Height(t?LeftChild);
int hr=Height(t?RightChild);
if(hl>hr)return ++ hl;
else return ++hr;}
8.10 Application
Take a tree as a binary tree
a
b c d e
f g h i j
a
b c
d e
f
g h
i
jFirstchild data nextSibling
1.Binary-Tree Representation of a Tree
树中插入一个新结点：
2,Equivalence Class
1).Definition of Equivalence Class:
Suppose we have a set U={1,2,…,n} of n
elements and a set R={(i1,j1),(i2,j2)……
(ir,jr)}of r relations,The relation R is an
equivalence relation iff the following
conditions are true(symbol’?’ represent the
equivalence relation on sets,x,y,z are elements
in set ),
2,Equivalence Class
? Reflexive x ?x.
? Symmetric x ?y,y ?x
? Transitive x ?y and y ?z,then x ?z
2),Example set s= {0,1,2,3,4,5,6,7,8,9,10,11}
pairs of equivalence:
(0 4),(3 1),(6 10),(8 9),(7 4),(6 8),(3 5),(2 11),(11 0)
Initial:{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}，
{10},{11}
0?4 {0,4},{1},{2},{3},{4},{5},{6},{7},{8},{9}，
{10},{11}
3 ?1 {0,4},{1,3},{2},{4},{5},{6},{7},{8},{9}，
{10},{11}
2,Equivalence Class
2,Equivalence Class
6 ?10 {0,4},{1,3},{2},{4},{5},{6,10},{7}，
{8},{9},{11}
8 ?9 {0,4},{1,3},{2},{4},{5},{6,10},{7},{8，
9},{11}
7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9}，
{11}
6 ? 8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11}
3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11}
2 ? 11 {0,4,7},{1,3,5},{2,11},{6,8,9,10}
11 ? 0 {0,4,7,2,11},{1,3,5},{6,8,9,10}
2,Equivalence Class
3),Online equivalence class operation
? Combine(a,b), combine the equivalence
classes that contains elements a and b into
a single class
? Find(e), determine the class that currently
contains element e.
Combine(a,b) is equivalent to i=Find(a);
j=Find(b); if(i!=j) Union(i,j);
2,Equivalence Class
4).Tree Representation(Union-Find sets)
? Example,
S1={1,7,8,9},S2={5,2,10},S3={3,4,6},they
all belong to S={1,2,3,……,10}
1
7 8 9 2 10
5
64
3
0 5 0 3 0 3 1 1 1 5parent
0 1 2 3 4 5 6 7 8 9 10
2,Equivalence Class
Program 8.15 simple tree solution to union-find
problem
void Initialize(int n)
{parent=new int[n+1];
for(int e=1;e<n;e++)
parent[e]=0;
}
2,Equivalence Class
int Find(int e)
{while(parent[e])
e=parent[e];
return e;
}
void Union(int i,int j)
{parent[j]=i;
}
2,Equivalence Class
5).Performance Evaluation
Time complexity,Find-- O(h),Union-- ?(1)
Assume that u times unions and f times finds are to be
performed,f>u,in the worst case a tree with m
elements can have a height of m:
Union(2,1),Union(3,2),Union(4,3),Union(5,4)…
Hence each find can take as much as ?(q) time where q is
the number of unions that have been performed
before the find.
2,Equivalence Class
6).Performance Enhancement
?improve Union in order to decrease the
time each find take,so that the height of
tree will not increase linearly,
2,Equivalence Class
two rules:
? Weight rule,if the number of nodes in tree i
is less than the number in tree j,then make j
the parent of i; otherwise,make i the parent
of j.
? Height rule,if the height of tree i is less
than that of tree j,then make j the parent of
i; otherwise,make i the parent of j,
2,Equivalence Class
? Let’s discuss the weight rule,
Parent[5]=1
Parent[1]=7
1
7 8 9 2 10
5 1
7 8 9 5
2 10
Union(1,5)
Besides the parent field,each node has a boolean field
root,The root field is true iff the node is presently a
root node.The parent field of each node is used to keep
a count of the total number of nodes in the tree.
2,Equivalence Class
? Program 8.16 Union with the weight rule
void Initialize(int n)
{ root=new bool[n+1];
parent=new int[n+1];
for(int e=1;e<=n;e++)
{ parent[e]=1;
root[e]=true;
}
2,Equivalence Class
int Find(int e)
{while(!root[e])
e=parent[e];
return e;
}
2,Equivalence Class
void Union(int i,int j)
{if(parent[i]<parent[j]) // i becomes subtree of j
{parent[j]=parent[j]+parent[i];
root[i]=false;
parent[i]=j;
}
else {parent[i]=parent[i]+parent[j];
root[j]=false;
parent[j]=i;
}
}
2,Equivalence Class
?.Improvement of Find –path compression
When processing a equivalence pair,we need to
operate Find twice,WeightUnion once.
Example of improvement:
1
7 8 9
2 10
4 6
1
7 8 910 6
42Find(6)
2,Equivalence Class
int Find( int e)
{ int j=e;
while(!root[j]) j=parent[j];
int f=e;
while(f!=j)
{int pf=parent[f]; parent[f]=j; f=pf;
}
