? 树和森林的概念
? 二叉树
? 二叉树遍历
? 二叉树的计数
? 线索化二叉树
? 堆
? 树与森林
? 霍夫曼树
树和森林的概念
树的定义
树是由 n (n ? 0) 个结点组成的有限集合。
如果 n = 0，称为空树；如果 n > 0，则
?有一个特定的称之为 根 (root)的结点，
它只有直接后继，但没有直接前驱；
?除根以外的其它结点划分为 m (m ? 0)
个 互不相交的有限集合 T0,T1,…,Tm-1，每
个集合又是一棵树, 并且称之为根的 子树 。
树的特点
? 每棵子树的根结点有且仅有一个直接前
驱，但可以有 0个或多个直接后继。
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
?结点
?结点的度
?分支结点
?叶结点
?子女
?双亲
?兄弟
?祖先
?子孙
?结点层次
?树的度
?树 高度
?森林
template <class Type> class Tree {
//对象, 树是由 n(≥0)个结点组成的有限集
//合。在类界面中的 position是树中结点的
//地址。在 顺序存储方式下是下标型,在链
//表存储方式下是指针型 。 Type是树结点
中存放数据的类型。
public:
Tree ( );
~Tree ( );
树的抽象数据类型
position Root ( );
BuildRoot ( const Type& value );
position FirstChild ( position p );
position NextSibling ( position p,
position v );
position Parent ( position p );
Type GetData ( position p );
int InsertChild ( const position p,
const Type &value );
int DeleteChild ( position p,int i );
}
二叉树 (Binary Tree)
二叉树的定义
二叉树的五种不同形态
一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加
上两棵分别称为左子树和右子树的、互不
相交的二叉树组成。
L LR R
性质 1 若二叉树的层次从 0开始,则在二叉
树的第 i 层最多有 2i 个结点。 (i? 0)
[证明用数学归纳法 ]
性质 2 高度为 h 的二叉树最多有 2h+1-1个
结点。 (h? -1)
[证明用求等比级数前 k项和的公式 ]
20 + 21 + 22 + … + 2 h = 2h+1-1
二叉树的性质
性质 3 对任何一棵二叉树,如果其 叶结点
有 n0 个,度 为 2的 非叶结点 有 n2 个,则有
n0＝ n2＋ 1
证明,若设 度 为 1的结点有 n1 个，总结点
个数为 n，总边数为 e，则根据二叉树的
定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
定义 1 满二叉树 (Full Binary Tree)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h+1层。
除第 h 层外，其它各层 (0 ? h-1) 的结点数
都达到最大个数，第 h 层从右向左连续缺
若干结点，这就是完全二叉树。
性质 4 具有 n (n ? 0) 个结点的完全二叉树
的高度为 ?log2(n+1)?-1
证明,设完全二叉树的高度为 h，则有
2h - 1 < n ? 2h+1 - 1
变形 2h < n+1 ? 2h+1
取对数 h < log2(n+1) ? h+1
因此有 ?log2(n+1)?= h+1
h = ?log2(n+1)?-1
上面 h层 结点数 第 h层 结点数
性质 5 如将一棵有 n个结点的完全二叉树自
顶向下，同一层自左向右连续给结点编号 0,
1,2,…,n-1，则有以下关系：
? 若 i = 0,则 i 无双亲
若 i > 0,则 i 的双亲为 ?(i -1)/2?
? 若 2*i+1 < n,则 i 的左子女为 2*i+1，若
2*i+2 < n,则 i 的右子女为 2*i+2
? 若 i 为偶数,且 i != 0,
则其左兄弟为 i-1,若
i 为奇数,且 i != n-1,
则其右兄弟为 i+1
0
1 2
3
7
4 5 6
8 9
二叉树的抽象数据类型
template <class Type> class BinaryTree {
public:
BinaryTree ( ); //构造函数
BinaryTree ( BinTreeNode<Type> * lch,
BinTreeNode<Type> * rch,Type item );
//构造以 item为根,lch和 rch为左、右
//子树的二叉树
int IsEmpty ( ); //判二叉树空否？
BinTreeNode<Type> * Parent ( ); //双亲
BinTreeNode<Type> * LeftChild ( );
//取左子女结点地址
BinTreeNode<Type> * RightChild ( );
//取右子女结点地址
int Insert ( const Type& item ); //插入
int Find ( const Type &item ) const; //搜索
Type GetData ( ) const; //取得结点数据
BinTreeNode<Type> *GetRoot ( ) const;
//取根结点地址
}
完全二叉树 一般二叉树
的 顺序表示 的 顺序表示
二叉树的顺序表示
0
0 1 2 3 4 5 6 7 8 9
9
0 1 2 3 4 5 6 7 8 9
1
3
7 8 9
4 5 6
2
0
1 2
543
6 7 8
二叉树的链表表示
leftChild data rightChild
data
leftChild rightChild
二叉链表
二叉树的链表表示
leftChild data parent rightChild
parent
data
leftChild rightChild
三叉链表
二叉树链表表示的示例
?
? ?
? ? ? ? ? ? ? ?
??
??A A A
B B B
CCC D D D
FFFE E E
root root root
二叉树 二叉链表 三叉链表
二叉链表的静态结构
A
B
C D
FE
root
data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
template <class Type> class BinaryTree;
template <class Type> Class BinTreeNode {
friend class BinaryTree<Type>;
private:
Type data;
BinTreeNode<Type> * leftChild;
BinTreeNode<Type> * rightChild;
public:
BinTreeNode ( ), leftChild (NULL),
rightChild (NULL) { }
二叉树的类定义
BinTreeNode ( Type item,
BinTreeNode<Type> *left = NULL,
BinTreeNode<Type> *right = NULL ),
data (item),leftChild (left),rightChild
(right) { }
Type GetData ( ) const { return data; }
BinTreeNode<Type> * GetLeft ( ) const
{ return leftChild; }
BinTreeNode<Type> * GetRight ( ) const
{ return rightChild; }
void SetData ( const Type& item )
{ data = item; }
void SetLeft ( BinTreeNode <Type> * L )
{ leftChild = L; }
void SetRight ( BinTreeNode <Type> * R )
{ rightChild = R; }
};
template <class Type> class BinaryTree {
private:
BinTreeNode <Type> *root;
Type RefValue;
void CreateBinTree ( ifstream& in,
BinTreeNode<Type> * & current );
BinTreeNode<Type> * Parent (
BinTreeNode<Type> * start,
BinTreeNode<Type> * current );
int Insert ( BinTreeNode<Type> * & current,
const Type &item ); //插入
void Traverse ( BinTreeNode<Type> *current,
ostream &out ) const //遍历
int Find ( BinTreeNode<Type> *current,
const Type &item ) const //搜索
void destroy ( BinTreeNode<Type> * current );
//删除
public:
virtual BinaryTree ( ), root (NULL) { }
virtual BinaryTree ( Type value ),
RefValue (value),root (NULL) { }
virtual ~BinaryTree ( ) { destroy ( root ); }
virtual int IsEmpty ( ) //判树空否
{ return root == NULL? 1, 0; }
virtual BinTreeNode <Type> * Parent (
BinTreeNode <Type> *current )
{ return root == NULL || root == current？
NULL, Parent ( root,current ); }
//找 current结点的双亲
virtual BinTreeNode<Type> * LeftChild
( BinTreeNode<Type> *current )
//取 current结点的左子女
{ return root != NULL?
current->leftChild, NULL; }
virtual BinTreeNode<Type> * RightChild
( BinTreeNode<Type> *current )
//取 current结点的右子女
{ return root != NULL?
current->rightChild, NULL; }
virtual int Insert ( const Type& item);
virtual BinTreeNode<Type> * Find
( const Type& item ) const; //搜索
BinTreeNode<Type> *GetRoot ( ) const
{ return root; } //取根
friend istream& operator >>
(filename,BinaryTree<Type>& Tree)
//重载操作：输入
friend ostream& operator <<
(ostream&out,BinaryTree<Type>& Tree)
//重载操作：输出
}
二叉树部分成员函数的实现
template<class Type>
void BinaryTree<Type>,,destroy
( BinTreeNode<Type> *current ) {
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
template<class Type>
void BinaryTree <Type>,,CreateBinTree
( ifstream& in,BinTreeNode<Type> * &
current ) {
//私有函数, 以递归方式建立二叉树 。
//输入结点值的顺序必须对应二叉树结点 前
//序遍历的顺序 。 并约定以输入序列中不可
//能出现的值作为空结点的值以结束递归,
//此值在 RefValue中 。 例如用, @”或用, -1”
//表示字符序列或正整数序列空结点 。
Type item;
if ( !in.eof ( ) ) {
如图所示的二叉树的前序遍历顺序为
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
in >> item; //读入根结点的值
if ( item != RefValue ) {
current = new BinTreeNode<Type>
( item ); //建立根结点
if ( current == NULL )
{ cerr <<,存储分配错 !” << endl;
exit (1); }
CreateBinTree ( in,current->leftChild );
CreateBinTree ( in,current->rightChild );
}
else current = NULL; //封闭叶结点
}
}
template <class Type> BinTreeNode <Type> *
BinaryTree <Type>,,Parent
( BinTreeNode <Type> * start,
BinTreeNode <Type> * cuurent ) {
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current ) return start;
BinTreeNode <Type> *p;
if (( p = Parent ( start->leftChild,current ))
!= NULL ) return p;
else return Parent(start->rightChild,current);
}
template <class Type>
void BinaryTree<Type>,,
Traverse ( BinTreeNode <Type> *current,
ostream &out ) const {
//私有函数,搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data << ? ?;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
template<class Type> istream& operator >>
( filename,BinaryTree<Type> & Tree ) {
//建立一棵二叉树 Tree。 in是输入流对象
Type item;
ifstream fin (filename,//打开文件
ios,,in | ios,,nocreate );
if ( !fin ) {
cerr <<,文件未发现 !” << endl; exit (1);
}
CreateBinTree ( ifstream& fin,root );
fin.close ( ); //关闭文件
}
template <class Type>
ostream& operator << ( ostream& out,
BinaryTree<Type> &Tree ) {
out <<,二叉树的前序遍历,\n";
Tree.Traverse ( Tree.root,out );
out << endl;
return out;
}
二叉树遍历
树的遍历就是按某种次序访问树中的结
点，要求每个结点访问一次且仅访问一次。
设 访问根结点 记作 V
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有
前序 VLR 镜像 VRL
中序 LVR 镜像 RVL
后序 LRV 镜像 RLV
中序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 中序遍历左子树 (L)；
? 访问根结点 (V)；
? 中序遍历右子树 (R)。
遍历结果
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的中序遍历算法
template <class Type>
void BinaryTree <Type>,,
InOrder ( BinTreeNode <Type> *current ) {
if ( current != NULL ) {
InOrder ( current->leftChild );
cout << current->data;
InOrder ( current->rightChild );
}
}
前序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 访问根结点 (V)；
? 前序遍历左子树 (L)；
? 前序遍历右子树 (R)。
遍历结果
- + a * b - c d / e f
前序遍历 (Preorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的前序遍历算法
template <class Type>
void BinaryTree<Type>,:
PreOrder ( BinTreeNode <Type> * current ) {
if ( current != NULL ) {
cout << current->data;
PreOrder ( current->leftChild );
PreOrder ( current->rightChild );
}
}
后序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 后序遍历左子树 (L)；
? 后序遍历右子树 (R)；
? 访问根结点 (V)。
遍历结果
a b c d - * + e f / -
后序遍历 (Postorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的后序遍历算法
template <class Type>
void BinaryTree <Type>,:
PostOrder ( BinTreeNode <Type> * current ) {
if ( current != NULL ) {
PostOrder ( current->leftChild );
PostOrder ( current->rightChild );
cout << current->data;
}
}
利用二叉树 后序遍历 计算二叉树结点个数
及二叉树的高度
template <class Type>
int BinaryTree<Type>,,Count (
const BinTreeNode <Type> * t ) const {
if ( t == NULL ) return 0;
else return 1 + Count ( t->leftChild )
+ Count ( t->rightChild );
}
应用二叉树遍历的事例
template <class Type>
int BinaryTree<Type>,,Height (
const BinTreeNode <Type> * t ) const {
if ( t == NULL ) return -1;
else
return 1 + Max ( Height ( t->leftChild ),
Height ( t->rightChild ) );
}
利用栈的前序遍历非递归算法
a
b c
d e
c
d
c c
访问
a
进栈
c
左进
b
访问
b
进栈
d
左进
空
退栈
d
访问
d
左进
空
退栈
c
访问
c
左进
e
访问
e
左进
空
栈空
结束
template <class Type>
void BinaryTree<Type>,,PreOrder( ) {
stack <TreeNode<Type>* > S;
BinTreeNode<Type> * p = root; //初始化
S.Push ( NULL );
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
S.Push ( p->rightChild );
//预留右子树指针在栈中
利用栈的前序遍历非递归算法
if ( p->leftChild != NULL )
p = p->leftChild; //进左子树
else { p = S.getTop( ); S.Pop( ); }
//左子树为空,进右子树
}
}
利用栈的中序遍历非递归算法
template <class Type>
void BinaryTree<Type>,,InOrder ( ) {
stack <TreeNode<Type>* > S;
利用栈的中序遍历非递归算法
a
b c
d e
b
a a
d
a a
左空 退栈
访问
左空 退栈
访问
退栈
访问
左空
e
c
退栈访问
c c
右空 退栈访问 栈空结束
BinTreeNode<Type> * p = root; //初始化
do {
while ( p != NULL )
{ S.Push(p); p = p->leftChild; }
if ( !S.IsEmpty( ) ) { //栈非空
p = S.getTop( ); S.Pop( ); //退栈
cout << p->data << endl; //访问根
p = p->rightChild; //向右链走
}
} while ( p != NULL || !S.IsEmpty( ) );
}
利用栈的后序遍历非递归算法
后序遍历时使用的栈的结点定义
template <class Type> struct stkNode {
BinTreeNode<Type> *ptr;
enum tag{ L,R };
//该结点退栈标记
stkNode( BinTreeNode<Type>* N = NULL )
,ptr (N),tag ( L ) { } //构造函数
};
根结点的 tag = L，表示从左子树退出,访问右
子树。 tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
a
b c
d e
aL
bL
aL
bR
aL
dL
bR
aL
dR
bR
aL
bR
aL aL aR
eL
cL
aR
eR
cL
aR
cL
aR
cR
aR aR
template <class Type>
void BinaryTree<Type>,,PostOrder ( ) {
stack <stkNode<Type> > S;
stkNode<Type> w;
BinTreeNode<Type> * p = root;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; st.Push ( w );
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !S.IsEmpty( ) ) {
w = st.getTop ( ); st.Pop ( ); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L, w.tag = R; st.Push ( w );
continue = 0;
p = p->rightChild; break;
case R, cout << p->data << endl;
}
}
} while ( p != NULL || !S.IsEmpty( ) );
cout << endl;
}
二叉树的计数
由二叉树的前序序列和中序序列可唯一
地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序
列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
前序序列 { ABHFDECKG }
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
如果前序序列固定不变，给出不同的中序
序列，可得到不同的二叉树。
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
固定前序排列,选择所有可能的中序排列,
可以可能构造多少种不同的二叉树？
例如,有 3 个数据 { 1,2,3 }，可得 5 种不
同的二叉树。它们的前序排列均为 123,中
序序列可能是 123,132,213,231,321。
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
有 0个,1个,2个,3个结点的不同二叉树如下
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
??
?
?
?
计算具有 n 个结点的不同二叉树的棵数
Catalan函数
bi bn-i-1
1
?
?
?
????
1
0
1
n
i
inin bbb
线索化二叉树 (Threaded Binary Tree)
线索 (Thread)
增加 Pred 指针和 Succ 指针的二叉树
线索化二叉树及其二叉链表表示
LeftThread=0,LeftChild为 左子女指针
LeftThread=1,LeftChild为 前驱线索
RightThread=0,RightChild为 右子女指针
RightThread=1,RightChild为 后继指针
LeftChild RightChilddata
LeftThread RightThread
中序线索化二叉树的类定义
template <class Type> class ThreadTree;
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ), root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
通过中序遍历建立中序线索化二叉树
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
template <class Type> void
ThreadTree<Type>,,CreateInThread ( ) {
ThreadNode<Type> *pre = NULL;
//前驱指针
if ( root != NULL ) { //非空二叉树,线索化
InThread ( root,pre );
//中序遍历线索化二叉树
pre->rightChild = NULL;
pre->rightThread = 1;
//后处理,中序最后一个结点
}
}
0 A 0
? 0 B 0 0 C 0 ?
? 0 D 0 ? ? 0 E 0 ?
rootpre == NULL current
0 A 0
? 1 B 0 0 C 0 ?
? 0 D 0 ? ? 0 E 0 ?
rootpre == NULL
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 0 ? ? 0 E 0 ?
root
pre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 ? 0 E 0 ?
root
pre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 1 E 0 ?
rootpre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 1 E 1
root
pre
current
0 A 0
? 1 B 0 0 C 1 ?
1 D 1 1 E 1
root
pre
后处理
if (p->rightThread ==1)
if (p->rightChild != NULL)
后继为 p->rightChild
else 无后继
else //p->rightThread != 1
if (p->rightChild != NULL)
后继为当前结点右子树
的中序下的第一个结点
else 出错情况
寻找当前结点在中序下的后继
A
B
D E
C
F
H I
K
G
J
if (current->leftThread==1)
if (current->leftChild !=
NULL)
前驱为 current->leftChild
else 无前驱
else //current->leftThread==0
if (current->leftChild !=
NULL)
前驱为当前结点左子树
中序下的最后一个结点
else 出错情况
寻找当前结点在中序下的前驱
A
B
D E
C
F
H I
K
G
J
L
在中序线索化二叉树中部分成员函数的实现
template <class Type>
ThreadNode<Type> * ThreadTree <Type>,,
First ( ThreadNode<Type> * current ) {
//函数返回以 *current为根在线索化二叉树中
//的中序序列下的第一个结点
ThreadNode<Type> * p = current;
while ( p->leftThread == 0 )
p = p->leftChild; //最左下的结点
return p;
}
template <class Type>
ThreadNode<Type> * ThreadTree <Type>,:
Next ( ThreadNode<Type> * current ) {
//函数返回在线索化二叉树中结点 *current在
//中序下的后继结点
ThreadNode<Type> *p = current->rightChild;
if ( current->rightThread == 0 )
return First ( p );
//rightThread == 0,表示有右子女
else return p;
//rightThread == 1,直接返回后继线索
}
template <class Type> void
ThreadTree <Type>,,Inorder ( ) {
//线索化二叉树的中序遍历
ThreadNode<Type> * p;
for ( p = First ( ); p != NULL; p = Next ( ) )
cout << p->data << endl;
}
前序线索化二叉树
前序序列
A B D C E
在前序线索化二叉树中
寻找当前结点的后继
p->leftThread==1?
前驱线索 = ? 左子女
p->rightChild
== NULL
后继为
p->leftChild
= ?
无后继 后继为
p->rightChild
A
B C
ED
后序线索化二叉树
后序序列
D B E C A
在前序线索化二
叉树中寻找当前
结点的后继
p->rightThread==1?
后继线索 = ? 右子女
后继为 q的右子树中
后序下第一个结点
后继为
p->leftChild
=?
无后继
后继为 q
A
B C
ED
q=p->parent
q==NULL?
Q->rightThread==1 ||
q->rightChild==p?
= ?
堆 ( Heap )
template <class Type> class MinPQ {
public:
Virtual void Insert ( const Type & ) = 0;
Virtual Type *RemoveMin ( Type & ) = 0;
}
最小优先级队列类的定义
优先级队列
每次出队列的是优先权最高的元素
完全二叉树
数组表示
Ki ? K2i+1 &&
Ki? K2i+2
完全二叉树
数组表示
Ki ? K2i+1 &&
Ki? K2i+2
堆的定义
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
最小堆的类定义
#define DefaultSize 10;
template <class Type>
class MinHeap, public MinPQ <Type> {
private:
Type * heap; //存放最小堆元素的数组
int CurrentSize; //最小堆当前元素个数
int MaxHeapSize; //最多允许元素个数
void FilterDown ( int i,int m );
//从 i 到 m自顶向下进行调整成为最小堆
void FilterUp ( int i );
//从 i 到 0自底向上进行调整成为最小堆
public,
MinHeap ( int sz ); //构造函数, 建立空堆
MinHeap ( Type arr[ ],int n ); //构造函数
~MinHeap ( ) { delete [ ] heap; }
const MinHeap<Type>&
operator = ( const MinHeap& R );
int Insert ( const Type& x ); //插入
int RemoveMin ( Type& x ); //删除
int IsEmpty ( ) const //判堆空否
{ return CurrentSize == 0; }
int IsFull ( ) const //判堆满否
{ return CurrentSize == MaxHeapSize; }
void MakeEmpty ( ) { CurrentSize = 0; }
}
堆的建立
template <class Type> MinHeap <Type>,:
MinHeap ( int maxSize ) {
//根据给定大小 maxSize,建立堆对象
MaxHeapSize = DefaultSize < maxSize?
maxSize, DefaultSize; //确定堆的大小
heap = new Type [MaxHeapSize];
if ( heap == NULL ) {
cerr <<,存储分配错 !”<< endl; exit(1);
}
CurrentSize = 0;
}
template <class Type> MinHeap <Type>,,
MinHeap ( Type arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆对象
MaxHeapSize = DefaultSize < n?
n, DefaultSize;
heap = new Type [MaxHeapSize];
if ( heap == NULL ) {
cerr <<,存储分配错 !” << endl; exit(1);
}
heap = arr; //数组传送
CurrentSize = n; //当前堆大小
int currentPos = (CurrentSize-2)/2;
//找最初调整位置,最后的分支结点号
while ( currentPos >= 0 ) {
//从下到上逐步扩大,形成堆
FilterDown ( currentPos,CurrentSize-1 );
//从 currentPos开始,到 CurrentSize止,
//调整
currentPos--;
}
}
自下向上逐步调整为最小堆
将一组用数组存放的任意数据调整成堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
currentPos = i = 3 currentPos = i = 2
i
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
currentPos = i = 1
i
53
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
currentPos = i = 0
i
09
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i17
最小堆的向下调整算法
template <class Type>
void MinHeap<Type>,,
FilterDown ( int start,int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
Type temp = heap[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap &&
heap[j].key > heap[j+1].key ) j++;
//两子女中选小者
if ( temp.key <= heap[j].key ) break;
else { heap[i] = heap[j]; //下面的上浮
i = j; j = 2*j+1; //向下滑动
}
}
heap[i] = temp;
}
堆的插入
template <class Type> int MinHeap<Type>,,
Insert ( const Type &x ) {
//在堆中插入新元素 x
if ( CurrentSize == MaxHeapSize ) //堆满
{ cerr << "堆已满 " << endl; return 0; }
heap[CurrentSize] = x; //插在表尾
FilterUp (CurrentSize); //向上调整为堆
CurrentSize++; //堆元素增一
return 1;
}
最小堆的向上调整算法
template <class Type>
void MinHeap<Type>,,FilterUp ( int start ) {
//从 start 开始,向上直到 0,调整堆
int j = start,i = (j-1)/2; // i 是 j 的双亲
Type temp = heap[j];
while ( j > 0 ) {
if ( heap[i].key <= temp.key ) break;
else { heap[j] = heap[i]; j = i; i = (i -1)/2;}
}
heap[j] = temp;
}
53
17 17
78 78
09
23 45
65
87
i
09
23 45
65
87
j
11
在堆中插入新元素 11
53
j
11
23
i
最小堆的向上调整
53
17 11
78 78
09
45
65
87
09
23 45
65
87
j
11
53 23
i
23
17
j
i
最小堆的删除算法
template <class Type> int MinHeap <Type>,:
RemoveMin ( Type &x ) {
if ( !CurrentSize )
{ cout <<, 堆已空 " << endl; return 0; }
x = heap[0]; //最小元素出队列
heap[0] = heap[CurrentSize-1];
CurrentSize--; //用最小元素填补
FilterDown ( 0,CurrentSize-1 ); //调整
return 1;
}
树的存储表示
? 广义表表示
树的广义表表示 (结点的 utype域没有画出 )
树与森林
A
B C D
E F G
A
B E F
C
D G
?双亲表示
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
?左子女 -右兄弟表示法
第一种解决方案
data child1 child2 child3 childd
第二种解决方案
树的左子女 -
右兄弟表示
data firstChild nextSibling
A
B C D
E F G
A
B
C
D
G
F
E
用左子女 -右兄弟表示实现的树的类定义
template <class Type> class Tree;
template <class Type> class TreeNode {
friend class<Type> Tree;
private:
Type data;
TreeNode<Type> *firstChild,*nextSibling;
public:
TreeNode ( Type value=0,
TreeNode<Type> *fc=NULL,
TreeNode<Type> *ns=NULL )
,data (value),firstChild (fc),nextSibling (ns)
{ }
};
template <class Type> class Tree {
private:
TreeNode<Type> *root,*current;
//根指针及当前指针
void PreOrder ( ostream& out,
TreeNode<Type> *p );
//先根次序遍历并输出以 p 为根的树
int Find ( TreeNode<Type> *p,Type target );
void RemovesubTree (TreeNode<Type> * p);
//删除以 p 为根的子树
int FindParent ( TreeNode<Type> * t,
TreeNode<Type> * p );
//在树 t 中搜索结点 p 的双亲
public:
Tree ( ) { root = current = NULL; }
int Root ( );
int FirstChild ( );
int NextSibling ( );
int Parent ( );
int Find ( Type target );
//树的其它公共操作
……
}
template <class Type>
int Tree <Type>,,Root ( ) {
//让树的根结点成为树的当前结点
if ( root == NULL )
{ current = NULL; return 0; }
else { current = root; return 1; }
}
template <class Type>
int Tree<Type>,,Parent ( ) {
//在树中找当前结点的双亲,成为当前结点
TreeNode<Type> * p = current,*t;
if ( current == NULL || current == root )
{ current = NULL; return 0; }
//空树或根为当前结点,返回 0
t = root;
int k = FindParent ( t,p ); //从 t找 p双亲
return k;
}
template <class Type>
int Tree<Type>,,FindParent
( TreeNode<Type> *t,TreeNode<Type> *p ) {
//在根为 t 的树中找 p 的双亲,成为当前结点
TreeNode<Type> *q = t->firstChild;
while ( q != NULL && q != p ) {
//循根的长子的兄弟链,递归在子树中搜索
if (( int i = FindParent (* q,* p) ) != 0 )
return i;
q = q->nextSibling;
}
if ( q != NULL && q ==p )
{ current = t; return 1; }
else return 0; //未找到双亲,当前结点不变
}
template <class Type>
int Tree <Type>,,FirstChild ( ) {
//在树中找当前结点的长子,成为当前结点
if (current != NULL &&
current->firstChild != NULL )
{ current = current→firstChild ; return 1; }
current = NULL; return 0;
}
template <class Type>
int Tree <Type>,,NextSibling ( ) {
//在树中找当前结点的兄弟,成为当前结点
if ( current != NULL &&
current->nextSibling != NULL )
{ current = current->nextSibling; return 1; }
current = NULL; return 0;
}
template <class Type>
int Tree<Type>,,Find ( Type target ) {
if ( IsEmpty ( ) ) return 0;
return Find ( root,target );
}
template <class Type> int Tree <Type>::
Find ( TreeNode <Type> * p,Type target ) {
//在根为 p 的树中找值为 target 的结点,找到
//后该结点成为当前结点,否则当前结点不变 。
//函数返回成功标志, =1,成功 ; =0,失败
int result = 0;
if ( p->data == target )
{ result = 1; current = p; } //搜索成功
else //搜索失败
{ TreeNode<Type> *q = p->firstChild;
while ( q != NULL &&
! ( result = Find ( q,target ) ) )
q = q->nextSibling;
}
return result;
}
森林与二叉树的转换
森林与二叉树的对应关系
T1 T2 T3A F H
T1 T2 T3A
B C D G I J
E K
F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林
各棵树的二叉树表示
森林的二叉树表示
(1) 森林转化成二叉树的规则
?若 F 为空,即 n = 0，则
对应的 二叉树 B 为 空二叉树 。
?若 F 不空,则
对应 二叉树 B 的根 root (B) 是 F 中 第
一棵树 T1 的根 root (T1)；
其 左子树 为 B (T11,T12,…,T 1m)，其中，
T11,T12,…,T 1m 是 root (T1) 的子树；
其 右子树 为 B (T2,T3,…,T n)，其中，
T2,T3,…,T n 是除 T1 外 其它树构成的森林 。
(2) 二叉树转换为森林的规则
?如果 B 为空，则对应的 森林 F 也为空。
?如果 B 非空，则
F 中 第一棵树 T1 的根为 root；
T1 的根的子树森林 { T11,T12,…,T 1m }
是由 root 的 左子树 LB 转换而来,F 中除了
T1 之外 其余的树组成的森林 { T2,T3,…,T n }
是由 root 的 右子树 RB 转换而成的森林。
树的二叉树表示
树的遍历
? 深度优先遍历
? 先根次序遍历
? 后根次序遍历
? 广度优先遍历 AB
CE
D
A
B C D
E F G G
F
(1) 树的先根次序遍历的递归算法
template <class Type>
void Tree<Type>,,PreOrder ( ) {
//以当前指针 current为根,先根次序遍历
if ( IsEmpty ( ) == 0 ) {
visit ( ); //访问根结点
TreeNode<Type> *p = current;
current = current ->firstChild; //第一棵子树
while ( current != NULL ) {
PreOrder ( ); //递归先根遍历子树
current = current ->nextSibling;
}
current = p; //恢复当前指针
}
}
(2) 树的后根次序遍历的递归算法
template <class Type> void Tree<Type>,,
PostOrder ( ) {
//以当前指针 current为根,按后根次序遍历树
if ( IsEmpty ( ) == 0 ) {
TreeNode<Type> *p = current;
current = current ->firstChild;
while ( current != NULL ) {
PostOrder ( );
current = current->nextSibling;
}
current = p; visit ( );
//恢复当前指针,最后访问根结点
}
}
(3) 广度优先 (层次次序 )遍历
template <class Type>
void Tree<Type>,,LevelOrder ( ) {
//按广度优先次序分层遍历树,树的根结点是
//当前指针 current。 算法中用到一个队列 。
Queue<TreeNode<Type>*> Qu(DefaultSize);
TreeNode<Type> *p;
if ( current != NULL ) { //当前指针不空
p = current; //保存当前指针
Qu.EnQueue ( current );
while ( Qu.IsEmpty ( ) == 0 ) {
current = Qu.getFront( ); DeQueue ( );
visit ( ); //队列中取一个并访问之
current = current ->firstChild ;
//待访问结点的子女结点进队列
while ( current != NULL ) {
Qu.EnQueue ( current );
current = current->nextSibling;
}
}
current = p; //恢复算法开始的当前指针
}
}
森林的遍历
森林的二叉树表示
(1) 先根次序遍历的规则,
?若森林 F 为空,
返回；否则
?访问 F 的第一棵
树的根结点；
?先根次序遍历第
一棵树的子树森林；
?先根次序遍历其
它树组成的森林。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(2) 中根次序遍历的规则：
?若森林 F 为空，
返回；否则
?中根次序遍历第
一棵树的子树森林；
?访问 F 的第一棵
树的根结点；
?中根次序序遍历
其它树组成的森林。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(3) 后根次序遍历的规则：
?若森林 F 为空，
返回；否则
?后根次序遍历第
一棵树的子树森林；
?后根次序遍历其
它树组成的森林；
?访问 F 的第一棵
树的根结点。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(4) 广度优先遍历 (层次
序遍历 ),
?若森林 F 为空，
返回；否则
?依次遍历各棵树
的根结点；
?依次遍历各棵树
根结点的所有子女；
?依次遍历这些子
女结点的子女结点 。 ??
A
B
C
E
D
H
I
K J
F
G
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两
结点的路径上的分支数。树的路径长度是
各叶结点到根结点的路径长度之和。
1 1
2 23 3
4 45 56
6
7
78
8树的路径长度
PL = 3*1+2*3 = 9 树的路径长度
PL = 1*1+2*1+3*1+4*1 = 10
n 个结点的二叉树的路径长度不小于
下述数列前 n 项的和，即
其路径长度最小者为
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
带权路径长度 (Weighted Path Length,WPL)
树的带权路径长度是树的各叶结点所带的权
值与该结点到根的路径长度的乘积的和。
?
?
?
??
1
0
n
i
ii lwW P L
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
??????????? 332222110
具有不同带权路径长度的扩充二叉树
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
带权路径长度达到最小
2
2
24
4
45 5
5
7
7
7
霍夫曼树
? 带权路径长度达到最小的扩充二叉树即为
霍夫曼树。
? 在霍夫曼树中，权值大的结点离根最近。
霍夫曼算法
(1) 由给定的 n 个权值 {w0,w1,w2,…,wn-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,Tn-1 }，其中每棵扩充二叉树 Ti 只有一
个带权值 wi 的根结点,其左、右子树均为空。
(2) 重复以下步骤,直到 F 中仅剩下一棵
树为止：
① 在 F 中选取两棵 根结点的权值最小 的
扩充二叉树,做为左、右子树 构造一棵新
的二叉树。置新的二叉树的 根结点的权值
为其左、右子树上根结点的权值之和 。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
霍夫曼树的构造过程
F, {7} {5} {2} {4} F, {7} {5} {6}
7 5 2 4
初始
合并 {2} {4}
F, {7} {11}
7 5
2 4
7 5
2 4
6
6
11
合并 {5} {6}
F, {18}
5
合并 {5} {6} 2
7
4
6
11
18
扩充二叉树的类定义
const int DefaultSize = 20;
template <class Type> class ExtBinTree;
template <class Type> class Element {
friend class ExtBinTree;
private:
Type data;
Element<Type> * leftChild,* rightChild;
};
template <class Type> class ExtBinTree {
public:
ExtBinTree (ExtBinTree<Type>& bt1,
ExtBinTree<Type> & bt2 ) {
root->leftChild = bt1.root;
root->rightChild = bt2.root;
root->data.key = bt1.root->data.key +
bt2.root->data.key;
}
protected:
Element<Type> *root; //二叉树的根
}
建立霍夫曼树的算法
template <class Type>
void HuffmanTree (Type *fr,int n,
ExtBinTree <Type> & newtree ) {
ExtBinTree <Type> & first,& second;
ExtBinTree <Type> Node[DafualtSize];
MinHeap < ExtBinTree <Type> > hp;
if ( n > DefaultSize ) {
cerr <<,大小 n, << n <<,超出了数组
边界, << endl; return;
}
for ( int i = 0; i < n; i++ ) {
Node[i].root->data.key = fr[i];
Node[i].root->leftChild =
Node[i].root ->rightChild = NULL;
}
hp.MinHeap ( Node,n );
//建立存储扩充二叉树森林的最小堆
for ( int i = 0; i < n-1; i++ ) {
//做 n-1趟,逐步形成霍夫曼树
hp.RemoveMin ( first ); //选择最小
hp.RemoveMin ( second ); //选择次小
newtree = new ExtBinTree<Type>
(first,second); //合并
hp.Insert ( newtree );
//重新插入到最小堆中
}
}
霍夫曼编码
主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现
的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A, 00 T, 10 C, 01 S, 11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36.
若按各个字符出现的概率不同而给予不等
长编码，可望减少总编码长度。
各字符出现概率为 { 2/18,7/18,4/18,5/18 },
化整为 { 2,7,4,5 }.
以它们为各叶结点上的权值,建立霍夫曼
树。 左分支 赋 0,右分支 赋 1，得霍夫曼编
码 (变长编码 )。
A, 0 T, 10 C, 110 S, 111
它的总 编码长度, 7*1+5*2+( 2+4 )*3 = 35。
比等长编码的情形要短。
总编码长度正好等于霍夫
曼树的带权路径长度 WPL。
霍夫曼编码是一种 无前缀
编码 。解码时不会混淆。
霍夫曼编码树
2 4
5
7
0
0
0
1
1
1
? 二叉树
? 二叉树遍历
? 二叉树的计数
? 线索化二叉树
? 堆
? 树与森林
? 霍夫曼树
树和森林的概念
树的定义
树是由 n (n ? 0) 个结点组成的有限集合。
如果 n = 0，称为空树；如果 n > 0，则
?有一个特定的称之为 根 (root)的结点，
它只有直接后继，但没有直接前驱；
?除根以外的其它结点划分为 m (m ? 0)
个 互不相交的有限集合 T0,T1,…,Tm-1，每
个集合又是一棵树, 并且称之为根的 子树 。
树的特点
? 每棵子树的根结点有且仅有一个直接前
驱，但可以有 0个或多个直接后继。
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
?结点
?结点的度
?分支结点
?叶结点
?子女
?双亲
?兄弟
?祖先
?子孙
?结点层次
?树的度
?树 高度
?森林
template <class Type> class Tree {
//对象, 树是由 n(≥0)个结点组成的有限集
//合。在类界面中的 position是树中结点的
//地址。在 顺序存储方式下是下标型,在链
//表存储方式下是指针型 。 Type是树结点
中存放数据的类型。
public:
Tree ( );
~Tree ( );
树的抽象数据类型
position Root ( );
BuildRoot ( const Type& value );
position FirstChild ( position p );
position NextSibling ( position p,
position v );
position Parent ( position p );
Type GetData ( position p );
int InsertChild ( const position p,
const Type &value );
int DeleteChild ( position p,int i );
}
二叉树 (Binary Tree)
二叉树的定义
二叉树的五种不同形态
一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加
上两棵分别称为左子树和右子树的、互不
相交的二叉树组成。
L LR R
性质 1 若二叉树的层次从 0开始,则在二叉
树的第 i 层最多有 2i 个结点。 (i? 0)
[证明用数学归纳法 ]
性质 2 高度为 h 的二叉树最多有 2h+1-1个
结点。 (h? -1)
[证明用求等比级数前 k项和的公式 ]
20 + 21 + 22 + … + 2 h = 2h+1-1
二叉树的性质
性质 3 对任何一棵二叉树,如果其 叶结点
有 n0 个,度 为 2的 非叶结点 有 n2 个,则有
n0＝ n2＋ 1
证明,若设 度 为 1的结点有 n1 个，总结点
个数为 n，总边数为 e，则根据二叉树的
定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
定义 1 满二叉树 (Full Binary Tree)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h+1层。
除第 h 层外，其它各层 (0 ? h-1) 的结点数
都达到最大个数，第 h 层从右向左连续缺
若干结点，这就是完全二叉树。
性质 4 具有 n (n ? 0) 个结点的完全二叉树
的高度为 ?log2(n+1)?-1
证明,设完全二叉树的高度为 h，则有
2h - 1 < n ? 2h+1 - 1
变形 2h < n+1 ? 2h+1
取对数 h < log2(n+1) ? h+1
因此有 ?log2(n+1)?= h+1
h = ?log2(n+1)?-1
上面 h层 结点数 第 h层 结点数
性质 5 如将一棵有 n个结点的完全二叉树自
顶向下，同一层自左向右连续给结点编号 0,
1,2,…,n-1，则有以下关系：
? 若 i = 0,则 i 无双亲
若 i > 0,则 i 的双亲为 ?(i -1)/2?
? 若 2*i+1 < n,则 i 的左子女为 2*i+1，若
2*i+2 < n,则 i 的右子女为 2*i+2
? 若 i 为偶数,且 i != 0,
则其左兄弟为 i-1,若
i 为奇数,且 i != n-1,
则其右兄弟为 i+1
0
1 2
3
7
4 5 6
8 9
二叉树的抽象数据类型
template <class Type> class BinaryTree {
public:
BinaryTree ( ); //构造函数
BinaryTree ( BinTreeNode<Type> * lch,
BinTreeNode<Type> * rch,Type item );
//构造以 item为根,lch和 rch为左、右
//子树的二叉树
int IsEmpty ( ); //判二叉树空否？
BinTreeNode<Type> * Parent ( ); //双亲
BinTreeNode<Type> * LeftChild ( );
//取左子女结点地址
BinTreeNode<Type> * RightChild ( );
//取右子女结点地址
int Insert ( const Type& item ); //插入
int Find ( const Type &item ) const; //搜索
Type GetData ( ) const; //取得结点数据
BinTreeNode<Type> *GetRoot ( ) const;
//取根结点地址
}
完全二叉树 一般二叉树
的 顺序表示 的 顺序表示
二叉树的顺序表示
0
0 1 2 3 4 5 6 7 8 9
9
0 1 2 3 4 5 6 7 8 9
1
3
7 8 9
4 5 6
2
0
1 2
543
6 7 8
二叉树的链表表示
leftChild data rightChild
data
leftChild rightChild
二叉链表
二叉树的链表表示
leftChild data parent rightChild
parent
data
leftChild rightChild
三叉链表
二叉树链表表示的示例
?
? ?
? ? ? ? ? ? ? ?
??
??A A A
B B B
CCC D D D
FFFE E E
root root root
二叉树 二叉链表 三叉链表
二叉链表的静态结构
A
B
C D
FE
root
data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
template <class Type> class BinaryTree;
template <class Type> Class BinTreeNode {
friend class BinaryTree<Type>;
private:
Type data;
BinTreeNode<Type> * leftChild;
BinTreeNode<Type> * rightChild;
public:
BinTreeNode ( ), leftChild (NULL),
rightChild (NULL) { }
二叉树的类定义
BinTreeNode ( Type item,
BinTreeNode<Type> *left = NULL,
BinTreeNode<Type> *right = NULL ),
data (item),leftChild (left),rightChild
(right) { }
Type GetData ( ) const { return data; }
BinTreeNode<Type> * GetLeft ( ) const
{ return leftChild; }
BinTreeNode<Type> * GetRight ( ) const
{ return rightChild; }
void SetData ( const Type& item )
{ data = item; }
void SetLeft ( BinTreeNode <Type> * L )
{ leftChild = L; }
void SetRight ( BinTreeNode <Type> * R )
{ rightChild = R; }
};
template <class Type> class BinaryTree {
private:
BinTreeNode <Type> *root;
Type RefValue;
void CreateBinTree ( ifstream& in,
BinTreeNode<Type> * & current );
BinTreeNode<Type> * Parent (
BinTreeNode<Type> * start,
BinTreeNode<Type> * current );
int Insert ( BinTreeNode<Type> * & current,
const Type &item ); //插入
void Traverse ( BinTreeNode<Type> *current,
ostream &out ) const //遍历
int Find ( BinTreeNode<Type> *current,
const Type &item ) const //搜索
void destroy ( BinTreeNode<Type> * current );
//删除
public:
virtual BinaryTree ( ), root (NULL) { }
virtual BinaryTree ( Type value ),
RefValue (value),root (NULL) { }
virtual ~BinaryTree ( ) { destroy ( root ); }
virtual int IsEmpty ( ) //判树空否
{ return root == NULL? 1, 0; }
virtual BinTreeNode <Type> * Parent (
BinTreeNode <Type> *current )
{ return root == NULL || root == current？
NULL, Parent ( root,current ); }
//找 current结点的双亲
virtual BinTreeNode<Type> * LeftChild
( BinTreeNode<Type> *current )
//取 current结点的左子女
{ return root != NULL?
current->leftChild, NULL; }
virtual BinTreeNode<Type> * RightChild
( BinTreeNode<Type> *current )
//取 current结点的右子女
{ return root != NULL?
current->rightChild, NULL; }
virtual int Insert ( const Type& item);
virtual BinTreeNode<Type> * Find
( const Type& item ) const; //搜索
BinTreeNode<Type> *GetRoot ( ) const
{ return root; } //取根
friend istream& operator >>
(filename,BinaryTree<Type>& Tree)
//重载操作：输入
friend ostream& operator <<
(ostream&out,BinaryTree<Type>& Tree)
//重载操作：输出
}
二叉树部分成员函数的实现
template<class Type>
void BinaryTree<Type>,,destroy
( BinTreeNode<Type> *current ) {
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
template<class Type>
void BinaryTree <Type>,,CreateBinTree
( ifstream& in,BinTreeNode<Type> * &
current ) {
//私有函数, 以递归方式建立二叉树 。
//输入结点值的顺序必须对应二叉树结点 前
//序遍历的顺序 。 并约定以输入序列中不可
//能出现的值作为空结点的值以结束递归,
//此值在 RefValue中 。 例如用, @”或用, -1”
//表示字符序列或正整数序列空结点 。
Type item;
if ( !in.eof ( ) ) {
如图所示的二叉树的前序遍历顺序为
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
in >> item; //读入根结点的值
if ( item != RefValue ) {
current = new BinTreeNode<Type>
( item ); //建立根结点
if ( current == NULL )
{ cerr <<,存储分配错 !” << endl;
exit (1); }
CreateBinTree ( in,current->leftChild );
CreateBinTree ( in,current->rightChild );
}
else current = NULL; //封闭叶结点
}
}
template <class Type> BinTreeNode <Type> *
BinaryTree <Type>,,Parent
( BinTreeNode <Type> * start,
BinTreeNode <Type> * cuurent ) {
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current ) return start;
BinTreeNode <Type> *p;
if (( p = Parent ( start->leftChild,current ))
!= NULL ) return p;
else return Parent(start->rightChild,current);
}
template <class Type>
void BinaryTree<Type>,,
Traverse ( BinTreeNode <Type> *current,
ostream &out ) const {
//私有函数,搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data << ? ?;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
template<class Type> istream& operator >>
( filename,BinaryTree<Type> & Tree ) {
//建立一棵二叉树 Tree。 in是输入流对象
Type item;
ifstream fin (filename,//打开文件
ios,,in | ios,,nocreate );
if ( !fin ) {
cerr <<,文件未发现 !” << endl; exit (1);
}
CreateBinTree ( ifstream& fin,root );
fin.close ( ); //关闭文件
}
template <class Type>
ostream& operator << ( ostream& out,
BinaryTree<Type> &Tree ) {
out <<,二叉树的前序遍历,\n";
Tree.Traverse ( Tree.root,out );
out << endl;
return out;
}
二叉树遍历
树的遍历就是按某种次序访问树中的结
点，要求每个结点访问一次且仅访问一次。
设 访问根结点 记作 V
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有
前序 VLR 镜像 VRL
中序 LVR 镜像 RVL
后序 LRV 镜像 RLV
中序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 中序遍历左子树 (L)；
? 访问根结点 (V)；
? 中序遍历右子树 (R)。
遍历结果
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的中序遍历算法
template <class Type>
void BinaryTree <Type>,,
InOrder ( BinTreeNode <Type> *current ) {
if ( current != NULL ) {
InOrder ( current->leftChild );
cout << current->data;
InOrder ( current->rightChild );
}
}
前序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 访问根结点 (V)；
? 前序遍历左子树 (L)；
? 前序遍历右子树 (R)。
遍历结果
- + a * b - c d / e f
前序遍历 (Preorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的前序遍历算法
template <class Type>
void BinaryTree<Type>,:
PreOrder ( BinTreeNode <Type> * current ) {
if ( current != NULL ) {
cout << current->data;
PreOrder ( current->leftChild );
PreOrder ( current->rightChild );
}
}
后序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 后序遍历左子树 (L)；
? 后序遍历右子树 (R)；
? 访问根结点 (V)。
遍历结果
a b c d - * + e f / -
后序遍历 (Postorder Traversal)
-
-
/+
*a
b
c d
e f
二叉树递归的后序遍历算法
template <class Type>
void BinaryTree <Type>,:
PostOrder ( BinTreeNode <Type> * current ) {
if ( current != NULL ) {
PostOrder ( current->leftChild );
PostOrder ( current->rightChild );
cout << current->data;
}
}
利用二叉树 后序遍历 计算二叉树结点个数
及二叉树的高度
template <class Type>
int BinaryTree<Type>,,Count (
const BinTreeNode <Type> * t ) const {
if ( t == NULL ) return 0;
else return 1 + Count ( t->leftChild )
+ Count ( t->rightChild );
}
应用二叉树遍历的事例
template <class Type>
int BinaryTree<Type>,,Height (
const BinTreeNode <Type> * t ) const {
if ( t == NULL ) return -1;
else
return 1 + Max ( Height ( t->leftChild ),
Height ( t->rightChild ) );
}
利用栈的前序遍历非递归算法
a
b c
d e
c
d
c c
访问
a
进栈
c
左进
b
访问
b
进栈
d
左进
空
退栈
d
访问
d
左进
空
退栈
c
访问
c
左进
e
访问
e
左进
空
栈空
结束
template <class Type>
void BinaryTree<Type>,,PreOrder( ) {
stack <TreeNode<Type>* > S;
BinTreeNode<Type> * p = root; //初始化
S.Push ( NULL );
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
S.Push ( p->rightChild );
//预留右子树指针在栈中
利用栈的前序遍历非递归算法
if ( p->leftChild != NULL )
p = p->leftChild; //进左子树
else { p = S.getTop( ); S.Pop( ); }
//左子树为空,进右子树
}
}
利用栈的中序遍历非递归算法
template <class Type>
void BinaryTree<Type>,,InOrder ( ) {
stack <TreeNode<Type>* > S;
利用栈的中序遍历非递归算法
a
b c
d e
b
a a
d
a a
左空 退栈
访问
左空 退栈
访问
退栈
访问
左空
e
c
退栈访问
c c
右空 退栈访问 栈空结束
BinTreeNode<Type> * p = root; //初始化
do {
while ( p != NULL )
{ S.Push(p); p = p->leftChild; }
if ( !S.IsEmpty( ) ) { //栈非空
p = S.getTop( ); S.Pop( ); //退栈
cout << p->data << endl; //访问根
p = p->rightChild; //向右链走
}
} while ( p != NULL || !S.IsEmpty( ) );
}
利用栈的后序遍历非递归算法
后序遍历时使用的栈的结点定义
template <class Type> struct stkNode {
BinTreeNode<Type> *ptr;
enum tag{ L,R };
//该结点退栈标记
stkNode( BinTreeNode<Type>* N = NULL )
,ptr (N),tag ( L ) { } //构造函数
};
根结点的 tag = L，表示从左子树退出,访问右
子树。 tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
a
b c
d e
aL
bL
aL
bR
aL
dL
bR
aL
dR
bR
aL
bR
aL aL aR
eL
cL
aR
eR
cL
aR
cL
aR
cR
aR aR
template <class Type>
void BinaryTree<Type>,,PostOrder ( ) {
stack <stkNode<Type> > S;
stkNode<Type> w;
BinTreeNode<Type> * p = root;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; st.Push ( w );
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !S.IsEmpty( ) ) {
w = st.getTop ( ); st.Pop ( ); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L, w.tag = R; st.Push ( w );
continue = 0;
p = p->rightChild; break;
case R, cout << p->data << endl;
}
}
} while ( p != NULL || !S.IsEmpty( ) );
cout << endl;
}
二叉树的计数
由二叉树的前序序列和中序序列可唯一
地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序
列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
前序序列 { ABHFDECKG }
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
如果前序序列固定不变，给出不同的中序
序列，可得到不同的二叉树。
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
固定前序排列,选择所有可能的中序排列,
可以可能构造多少种不同的二叉树？
例如,有 3 个数据 { 1,2,3 }，可得 5 种不
同的二叉树。它们的前序排列均为 123,中
序序列可能是 123,132,213,231,321。
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
有 0个,1个,2个,3个结点的不同二叉树如下
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
??
?
?
?
计算具有 n 个结点的不同二叉树的棵数
Catalan函数
bi bn-i-1
1
?
?
?
????
1
0
1
n
i
inin bbb
线索化二叉树 (Threaded Binary Tree)
线索 (Thread)
增加 Pred 指针和 Succ 指针的二叉树
线索化二叉树及其二叉链表表示
LeftThread=0,LeftChild为 左子女指针
LeftThread=1,LeftChild为 前驱线索
RightThread=0,RightChild为 右子女指针
RightThread=1,RightChild为 后继指针
LeftChild RightChilddata
LeftThread RightThread
中序线索化二叉树的类定义
template <class Type> class ThreadTree;
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ), root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
通过中序遍历建立中序线索化二叉树
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
template <class Type> void
ThreadTree<Type>,,CreateInThread ( ) {
ThreadNode<Type> *pre = NULL;
//前驱指针
if ( root != NULL ) { //非空二叉树,线索化
InThread ( root,pre );
//中序遍历线索化二叉树
pre->rightChild = NULL;
pre->rightThread = 1;
//后处理,中序最后一个结点
}
}
0 A 0
? 0 B 0 0 C 0 ?
? 0 D 0 ? ? 0 E 0 ?
rootpre == NULL current
0 A 0
? 1 B 0 0 C 0 ?
? 0 D 0 ? ? 0 E 0 ?
rootpre == NULL
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 0 ? ? 0 E 0 ?
root
pre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 ? 0 E 0 ?
root
pre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 1 E 0 ?
rootpre
current
0 A 0
? 1 B 0 0 C 0 ?
1 D 1 1 E 1
root
pre
current
0 A 0
? 1 B 0 0 C 1 ?
1 D 1 1 E 1
root
pre
后处理
if (p->rightThread ==1)
if (p->rightChild != NULL)
后继为 p->rightChild
else 无后继
else //p->rightThread != 1
if (p->rightChild != NULL)
后继为当前结点右子树
的中序下的第一个结点
else 出错情况
寻找当前结点在中序下的后继
A
B
D E
C
F
H I
K
G
J
if (current->leftThread==1)
if (current->leftChild !=
NULL)
前驱为 current->leftChild
else 无前驱
else //current->leftThread==0
if (current->leftChild !=
NULL)
前驱为当前结点左子树
中序下的最后一个结点
else 出错情况
寻找当前结点在中序下的前驱
A
B
D E
C
F
H I
K
G
J
L
在中序线索化二叉树中部分成员函数的实现
template <class Type>
ThreadNode<Type> * ThreadTree <Type>,,
First ( ThreadNode<Type> * current ) {
//函数返回以 *current为根在线索化二叉树中
//的中序序列下的第一个结点
ThreadNode<Type> * p = current;
while ( p->leftThread == 0 )
p = p->leftChild; //最左下的结点
return p;
}
template <class Type>
ThreadNode<Type> * ThreadTree <Type>,:
Next ( ThreadNode<Type> * current ) {
//函数返回在线索化二叉树中结点 *current在
//中序下的后继结点
ThreadNode<Type> *p = current->rightChild;
if ( current->rightThread == 0 )
return First ( p );
//rightThread == 0,表示有右子女
else return p;
//rightThread == 1,直接返回后继线索
}
template <class Type> void
ThreadTree <Type>,,Inorder ( ) {
//线索化二叉树的中序遍历
ThreadNode<Type> * p;
for ( p = First ( ); p != NULL; p = Next ( ) )
cout << p->data << endl;
}
前序线索化二叉树
前序序列
A B D C E
在前序线索化二叉树中
寻找当前结点的后继
p->leftThread==1?
前驱线索 = ? 左子女
p->rightChild
== NULL
后继为
p->leftChild
= ?
无后继 后继为
p->rightChild
A
B C
ED
后序线索化二叉树
后序序列
D B E C A
在前序线索化二
叉树中寻找当前
结点的后继
p->rightThread==1?
后继线索 = ? 右子女
后继为 q的右子树中
后序下第一个结点
后继为
p->leftChild
=?
无后继
后继为 q
A
B C
ED
q=p->parent
q==NULL?
Q->rightThread==1 ||
q->rightChild==p?
= ?
堆 ( Heap )
template <class Type> class MinPQ {
public:
Virtual void Insert ( const Type & ) = 0;
Virtual Type *RemoveMin ( Type & ) = 0;
}
最小优先级队列类的定义
优先级队列
每次出队列的是优先权最高的元素
完全二叉树
数组表示
Ki ? K2i+1 &&
Ki? K2i+2
完全二叉树
数组表示
Ki ? K2i+1 &&
Ki? K2i+2
堆的定义
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
最小堆的类定义
#define DefaultSize 10;
template <class Type>
class MinHeap, public MinPQ <Type> {
private:
Type * heap; //存放最小堆元素的数组
int CurrentSize; //最小堆当前元素个数
int MaxHeapSize; //最多允许元素个数
void FilterDown ( int i,int m );
//从 i 到 m自顶向下进行调整成为最小堆
void FilterUp ( int i );
//从 i 到 0自底向上进行调整成为最小堆
public,
MinHeap ( int sz ); //构造函数, 建立空堆
MinHeap ( Type arr[ ],int n ); //构造函数
~MinHeap ( ) { delete [ ] heap; }
const MinHeap<Type>&
operator = ( const MinHeap& R );
int Insert ( const Type& x ); //插入
int RemoveMin ( Type& x ); //删除
int IsEmpty ( ) const //判堆空否
{ return CurrentSize == 0; }
int IsFull ( ) const //判堆满否
{ return CurrentSize == MaxHeapSize; }
void MakeEmpty ( ) { CurrentSize = 0; }
}
堆的建立
template <class Type> MinHeap <Type>,:
MinHeap ( int maxSize ) {
//根据给定大小 maxSize,建立堆对象
MaxHeapSize = DefaultSize < maxSize?
maxSize, DefaultSize; //确定堆的大小
heap = new Type [MaxHeapSize];
if ( heap == NULL ) {
cerr <<,存储分配错 !”<< endl; exit(1);
}
CurrentSize = 0;
}
template <class Type> MinHeap <Type>,,
MinHeap ( Type arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆对象
MaxHeapSize = DefaultSize < n?
n, DefaultSize;
heap = new Type [MaxHeapSize];
if ( heap == NULL ) {
cerr <<,存储分配错 !” << endl; exit(1);
}
heap = arr; //数组传送
CurrentSize = n; //当前堆大小
int currentPos = (CurrentSize-2)/2;
//找最初调整位置,最后的分支结点号
while ( currentPos >= 0 ) {
//从下到上逐步扩大,形成堆
FilterDown ( currentPos,CurrentSize-1 );
//从 currentPos开始,到 CurrentSize止,
//调整
currentPos--;
}
}
自下向上逐步调整为最小堆
将一组用数组存放的任意数据调整成堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
currentPos = i = 3 currentPos = i = 2
i
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
currentPos = i = 1
i
53
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
currentPos = i = 0
i
09
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i17
最小堆的向下调整算法
template <class Type>
void MinHeap<Type>,,
FilterDown ( int start,int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
Type temp = heap[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap &&
heap[j].key > heap[j+1].key ) j++;
//两子女中选小者
if ( temp.key <= heap[j].key ) break;
else { heap[i] = heap[j]; //下面的上浮
i = j; j = 2*j+1; //向下滑动
}
}
heap[i] = temp;
}
堆的插入
template <class Type> int MinHeap<Type>,,
Insert ( const Type &x ) {
//在堆中插入新元素 x
if ( CurrentSize == MaxHeapSize ) //堆满
{ cerr << "堆已满 " << endl; return 0; }
heap[CurrentSize] = x; //插在表尾
FilterUp (CurrentSize); //向上调整为堆
CurrentSize++; //堆元素增一
return 1;
}
最小堆的向上调整算法
template <class Type>
void MinHeap<Type>,,FilterUp ( int start ) {
//从 start 开始,向上直到 0,调整堆
int j = start,i = (j-1)/2; // i 是 j 的双亲
Type temp = heap[j];
while ( j > 0 ) {
if ( heap[i].key <= temp.key ) break;
else { heap[j] = heap[i]; j = i; i = (i -1)/2;}
}
heap[j] = temp;
}
53
17 17
78 78
09
23 45
65
87
i
09
23 45
65
87
j
11
在堆中插入新元素 11
53
j
11
23
i
最小堆的向上调整
53
17 11
78 78
09
45
65
87
09
23 45
65
87
j
11
53 23
i
23
17
j
i
最小堆的删除算法
template <class Type> int MinHeap <Type>,:
RemoveMin ( Type &x ) {
if ( !CurrentSize )
{ cout <<, 堆已空 " << endl; return 0; }
x = heap[0]; //最小元素出队列
heap[0] = heap[CurrentSize-1];
CurrentSize--; //用最小元素填补
FilterDown ( 0,CurrentSize-1 ); //调整
return 1;
}
树的存储表示
? 广义表表示
树的广义表表示 (结点的 utype域没有画出 )
树与森林
A
B C D
E F G
A
B E F
C
D G
?双亲表示
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
?左子女 -右兄弟表示法
第一种解决方案
data child1 child2 child3 childd
第二种解决方案
树的左子女 -
右兄弟表示
data firstChild nextSibling
A
B C D
E F G
A
B
C
D
G
F
E
用左子女 -右兄弟表示实现的树的类定义
template <class Type> class Tree;
template <class Type> class TreeNode {
friend class<Type> Tree;
private:
Type data;
TreeNode<Type> *firstChild,*nextSibling;
public:
TreeNode ( Type value=0,
TreeNode<Type> *fc=NULL,
TreeNode<Type> *ns=NULL )
,data (value),firstChild (fc),nextSibling (ns)
{ }
};
template <class Type> class Tree {
private:
TreeNode<Type> *root,*current;
//根指针及当前指针
void PreOrder ( ostream& out,
TreeNode<Type> *p );
//先根次序遍历并输出以 p 为根的树
int Find ( TreeNode<Type> *p,Type target );
void RemovesubTree (TreeNode<Type> * p);
//删除以 p 为根的子树
int FindParent ( TreeNode<Type> * t,
TreeNode<Type> * p );
//在树 t 中搜索结点 p 的双亲
public:
Tree ( ) { root = current = NULL; }
int Root ( );
int FirstChild ( );
int NextSibling ( );
int Parent ( );
int Find ( Type target );
//树的其它公共操作
……
}
template <class Type>
int Tree <Type>,,Root ( ) {
//让树的根结点成为树的当前结点
if ( root == NULL )
{ current = NULL; return 0; }
else { current = root; return 1; }
}
template <class Type>
int Tree<Type>,,Parent ( ) {
//在树中找当前结点的双亲,成为当前结点
TreeNode<Type> * p = current,*t;
if ( current == NULL || current == root )
{ current = NULL; return 0; }
//空树或根为当前结点,返回 0
t = root;
int k = FindParent ( t,p ); //从 t找 p双亲
return k;
}
template <class Type>
int Tree<Type>,,FindParent
( TreeNode<Type> *t,TreeNode<Type> *p ) {
//在根为 t 的树中找 p 的双亲,成为当前结点
TreeNode<Type> *q = t->firstChild;
while ( q != NULL && q != p ) {
//循根的长子的兄弟链,递归在子树中搜索
if (( int i = FindParent (* q,* p) ) != 0 )
return i;
q = q->nextSibling;
}
if ( q != NULL && q ==p )
{ current = t; return 1; }
else return 0; //未找到双亲,当前结点不变
}
template <class Type>
int Tree <Type>,,FirstChild ( ) {
//在树中找当前结点的长子,成为当前结点
if (current != NULL &&
current->firstChild != NULL )
{ current = current→firstChild ; return 1; }
current = NULL; return 0;
}
template <class Type>
int Tree <Type>,,NextSibling ( ) {
//在树中找当前结点的兄弟,成为当前结点
if ( current != NULL &&
current->nextSibling != NULL )
{ current = current->nextSibling; return 1; }
current = NULL; return 0;
}
template <class Type>
int Tree<Type>,,Find ( Type target ) {
if ( IsEmpty ( ) ) return 0;
return Find ( root,target );
}
template <class Type> int Tree <Type>::
Find ( TreeNode <Type> * p,Type target ) {
//在根为 p 的树中找值为 target 的结点,找到
//后该结点成为当前结点,否则当前结点不变 。
//函数返回成功标志, =1,成功 ; =0,失败
int result = 0;
if ( p->data == target )
{ result = 1; current = p; } //搜索成功
else //搜索失败
{ TreeNode<Type> *q = p->firstChild;
while ( q != NULL &&
! ( result = Find ( q,target ) ) )
q = q->nextSibling;
}
return result;
}
森林与二叉树的转换
森林与二叉树的对应关系
T1 T2 T3A F H
T1 T2 T3A
B C D G I J
E K
F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林
各棵树的二叉树表示
森林的二叉树表示
(1) 森林转化成二叉树的规则
?若 F 为空,即 n = 0，则
对应的 二叉树 B 为 空二叉树 。
?若 F 不空,则
对应 二叉树 B 的根 root (B) 是 F 中 第
一棵树 T1 的根 root (T1)；
其 左子树 为 B (T11,T12,…,T 1m)，其中，
T11,T12,…,T 1m 是 root (T1) 的子树；
其 右子树 为 B (T2,T3,…,T n)，其中，
T2,T3,…,T n 是除 T1 外 其它树构成的森林 。
(2) 二叉树转换为森林的规则
?如果 B 为空，则对应的 森林 F 也为空。
?如果 B 非空，则
F 中 第一棵树 T1 的根为 root；
T1 的根的子树森林 { T11,T12,…,T 1m }
是由 root 的 左子树 LB 转换而来,F 中除了
T1 之外 其余的树组成的森林 { T2,T3,…,T n }
是由 root 的 右子树 RB 转换而成的森林。
树的二叉树表示
树的遍历
? 深度优先遍历
? 先根次序遍历
? 后根次序遍历
? 广度优先遍历 AB
CE
D
A
B C D
E F G G
F
(1) 树的先根次序遍历的递归算法
template <class Type>
void Tree<Type>,,PreOrder ( ) {
//以当前指针 current为根,先根次序遍历
if ( IsEmpty ( ) == 0 ) {
visit ( ); //访问根结点
TreeNode<Type> *p = current;
current = current ->firstChild; //第一棵子树
while ( current != NULL ) {
PreOrder ( ); //递归先根遍历子树
current = current ->nextSibling;
}
current = p; //恢复当前指针
}
}
(2) 树的后根次序遍历的递归算法
template <class Type> void Tree<Type>,,
PostOrder ( ) {
//以当前指针 current为根,按后根次序遍历树
if ( IsEmpty ( ) == 0 ) {
TreeNode<Type> *p = current;
current = current ->firstChild;
while ( current != NULL ) {
PostOrder ( );
current = current->nextSibling;
}
current = p; visit ( );
//恢复当前指针,最后访问根结点
}
}
(3) 广度优先 (层次次序 )遍历
template <class Type>
void Tree<Type>,,LevelOrder ( ) {
//按广度优先次序分层遍历树,树的根结点是
//当前指针 current。 算法中用到一个队列 。
Queue<TreeNode<Type>*> Qu(DefaultSize);
TreeNode<Type> *p;
if ( current != NULL ) { //当前指针不空
p = current; //保存当前指针
Qu.EnQueue ( current );
while ( Qu.IsEmpty ( ) == 0 ) {
current = Qu.getFront( ); DeQueue ( );
visit ( ); //队列中取一个并访问之
current = current ->firstChild ;
//待访问结点的子女结点进队列
while ( current != NULL ) {
Qu.EnQueue ( current );
current = current->nextSibling;
}
}
current = p; //恢复算法开始的当前指针
}
}
森林的遍历
森林的二叉树表示
(1) 先根次序遍历的规则,
?若森林 F 为空,
返回；否则
?访问 F 的第一棵
树的根结点；
?先根次序遍历第
一棵树的子树森林；
?先根次序遍历其
它树组成的森林。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(2) 中根次序遍历的规则：
?若森林 F 为空，
返回；否则
?中根次序遍历第
一棵树的子树森林；
?访问 F 的第一棵
树的根结点；
?中根次序序遍历
其它树组成的森林。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(3) 后根次序遍历的规则：
?若森林 F 为空，
返回；否则
?后根次序遍历第
一棵树的子树森林；
?后根次序遍历其
它树组成的森林；
?访问 F 的第一棵
树的根结点。
A
B
C
E
D
H
I
K J
F
G
森林的遍历
森林的二叉树表示
(4) 广度优先遍历 (层次
序遍历 ),
?若森林 F 为空，
返回；否则
?依次遍历各棵树
的根结点；
?依次遍历各棵树
根结点的所有子女；
?依次遍历这些子
女结点的子女结点 。 ??
A
B
C
E
D
H
I
K J
F
G
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两
结点的路径上的分支数。树的路径长度是
各叶结点到根结点的路径长度之和。
1 1
2 23 3
4 45 56
6
7
78
8树的路径长度
PL = 3*1+2*3 = 9 树的路径长度
PL = 1*1+2*1+3*1+4*1 = 10
n 个结点的二叉树的路径长度不小于
下述数列前 n 项的和，即
其路径长度最小者为
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
带权路径长度 (Weighted Path Length,WPL)
树的带权路径长度是树的各叶结点所带的权
值与该结点到根的路径长度的乘积的和。
?
?
?
??
1
0
n
i
ii lwW P L
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
??????????? 332222110
具有不同带权路径长度的扩充二叉树
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
带权路径长度达到最小
2
2
24
4
45 5
5
7
7
7
霍夫曼树
? 带权路径长度达到最小的扩充二叉树即为
霍夫曼树。
? 在霍夫曼树中，权值大的结点离根最近。
霍夫曼算法
(1) 由给定的 n 个权值 {w0,w1,w2,…,wn-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,Tn-1 }，其中每棵扩充二叉树 Ti 只有一
个带权值 wi 的根结点,其左、右子树均为空。
(2) 重复以下步骤,直到 F 中仅剩下一棵
树为止：
① 在 F 中选取两棵 根结点的权值最小 的
扩充二叉树,做为左、右子树 构造一棵新
的二叉树。置新的二叉树的 根结点的权值
为其左、右子树上根结点的权值之和 。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
霍夫曼树的构造过程
F, {7} {5} {2} {4} F, {7} {5} {6}
7 5 2 4
初始
合并 {2} {4}
F, {7} {11}
7 5
2 4
7 5
2 4
6
6
11
合并 {5} {6}
F, {18}
5
合并 {5} {6} 2
7
4
6
11
18
扩充二叉树的类定义
const int DefaultSize = 20;
template <class Type> class ExtBinTree;
template <class Type> class Element {
friend class ExtBinTree;
private:
Type data;
Element<Type> * leftChild,* rightChild;
};
template <class Type> class ExtBinTree {
public:
ExtBinTree (ExtBinTree<Type>& bt1,
ExtBinTree<Type> & bt2 ) {
root->leftChild = bt1.root;
root->rightChild = bt2.root;
root->data.key = bt1.root->data.key +
bt2.root->data.key;
}
protected:
Element<Type> *root; //二叉树的根
}
建立霍夫曼树的算法
template <class Type>
void HuffmanTree (Type *fr,int n,
ExtBinTree <Type> & newtree ) {
ExtBinTree <Type> & first,& second;
ExtBinTree <Type> Node[DafualtSize];
MinHeap < ExtBinTree <Type> > hp;
if ( n > DefaultSize ) {
cerr <<,大小 n, << n <<,超出了数组
边界, << endl; return;
}
for ( int i = 0; i < n; i++ ) {
Node[i].root->data.key = fr[i];
Node[i].root->leftChild =
Node[i].root ->rightChild = NULL;
}
hp.MinHeap ( Node,n );
//建立存储扩充二叉树森林的最小堆
for ( int i = 0; i < n-1; i++ ) {
//做 n-1趟,逐步形成霍夫曼树
hp.RemoveMin ( first ); //选择最小
hp.RemoveMin ( second ); //选择次小
newtree = new ExtBinTree<Type>
(first,second); //合并
hp.Insert ( newtree );
//重新插入到最小堆中
}
}
霍夫曼编码
主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现
的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A, 00 T, 10 C, 01 S, 11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36.
若按各个字符出现的概率不同而给予不等
长编码，可望减少总编码长度。
各字符出现概率为 { 2/18,7/18,4/18,5/18 },
化整为 { 2,7,4,5 }.
以它们为各叶结点上的权值,建立霍夫曼
树。 左分支 赋 0,右分支 赋 1，得霍夫曼编
码 (变长编码 )。
A, 0 T, 10 C, 110 S, 111
它的总 编码长度, 7*1+5*2+( 2+4 )*3 = 35。
比等长编码的情形要短。
总编码长度正好等于霍夫
曼树的带权路径长度 WPL。
霍夫曼编码是一种 无前缀
编码 。解码时不会混淆。
霍夫曼编码树
2 4
5
7
0
0
0
1
1
1
