2011-7-18 1
第 6章 树和森林
非线性数据结构
实际中有许多树型结构的问题，用树型数据结构来解决非常自然
树型结构在计算机领域的应用非常广泛
6.1 树和森林的概念
树的定义：
树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树，
否则：
（ 1）有一个特定的称之为根 ( root )的结点，它只有直接后继，
但没有直接前驱；
（ 2）除根以外的其他结点可划分为若干个互不相交的有限集合，
每个集合又是一棵树，并且称之为根的子树 ( subTree )。每
棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多
个直接后继。
2011-7-18 2
树的示意图：
根
结
点
根结点
叶结点
分支结点
子树
子树
子树
Level 0
Level 1
Level 2
Level 3
结点的层次
2011-7-18 3
树的基本术语
结点的度 ( degree )：结点所拥有的子树数目
子女 ( child ) 结点：简称子结点
双亲 ( parent) 结点：简称父结点 ( father )
兄弟 ( sibling)结点：具有同一个父结点的结点
根 ( root ) 结点：
分支 ( branch )结点：又称非终端结点
叶 ( leaf ) 结点：又称终端结点
结点的层次 ( level ):根结点的层次为 0，子结点的层次等于其父结
点的层次加一
树的高度 ( depth ):等于树中最大的结点层次数。空树的高度为－ 1
树的度 ( degree ):等于树中最大的结点度数
有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，
否则就成为另一棵树了。
无序树：树中结点的各子树之间的先后次序无意义，可以互换
森林 ( forest ):若干棵树的集合
2011-7-18 4
6.2 二叉树 ( Binary Tree )
二叉树是树的基础，一般的树可以转化为二叉树来处理。
6.2.1 二叉树的定义
一棵二叉树是一有限结点的集合，该集合或者为空（空二叉
树），或者是由一个根结点及其下的两棵互不相交的子二叉树构
成，其中左边的称为左子树，右边的称为右子树。
二叉树是一棵度数 <= 2 的有序树。
6.2.2 二叉树的性质
（ 1）二叉树的第 i 层的结点数 <=
（ 2）高度为 k 的二叉树的最大结点数＝ ( k >= -1)
满二叉树 ( Full Binary Tree )：叶结点在同一层，非叶结点的度数均
为 2 的二叉树（参见图 6.3a ）
完全二叉树 ( Complete Binary Tree ),按从上到下、从左到右顺序
编号一棵满二叉树，并按从大到小的顺序连续删除
该满二叉树的若干个结点后剩下的二叉树称为一棵
完全二叉树（参见图 6.3b ）
2 i
2k+1- 1
2011-7-18 5
完全二叉树的性质和顺序存储结构
（ 1）具有 n 个结点的完全二叉树的高度 = log2 ( n + 1 ) – 1
（ 2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一
个一维数组中，则有：
结点 i 的左子结点下标 = 2* i + 1 < n
结点 i 的右子结点下标 = 2* i + 2 < n
结点 i 的父结点下标 = ( i – 1 ) / 2 的下取整值
另外注意：根结点（下标为 0）无父结点
由上可知，完全二叉树的父 ——左子、父 ——右子之间的
关系可以通过相应结点的下标之间的简单数学关系完全地表示
出来，因此可以采用顺序存储结构来存储完全二叉树。（参见
教材 6.3.1 数组表示）
顺序存储结构用于动态性较小的完全二叉树的存储不失为
一种简单有效的方法，但不通用。树型数据结构一般采用链式存
储方式来存储。
2011-7-18 6
6.3.2 二叉树的链式存储结构 —— 二叉（三叉）链表结构
二叉链表结构：
左子指针 数据元素 右子指针
三叉链表结构：
左子指针 数据元素 右子指针
父指针
leftChild data rightChild
leftChild data father rightChild
2011-7-18 7
二叉链表结构的二叉树结点（简称二叉树结点）的类定义：
template <class Type> class BinaryTree;//二叉树类声明
template <class Type> class BinTreeNode//二叉树结点类定义
{
friend class BinaryTree<Type>;//二叉树类是二叉树结点类的友元
public:
BinTreeNode( ),leftChild(NULL),rightChild(NULL) { }
//构造函数
BinTreeNode( Type item,BinTreeNode<Type> * left = NULL,
BinTreeNode<Type> * right = NULL):data(item),
leftChild(left),rightChild(right) { }//构造函数
… // 其他成员函数
private:
BinTreeNode<Type> * leftChild,* rightChild ;
//左子指针、右子指针
Type data;//数据元素
}
2011-7-18 8
二叉链表结构的二叉树的类定义
template <class Type> class BinaryTree
{ public:
BinaryTree( ), root(NULL) { }//创建一棵空二叉树
BinaryTree( Type value ), RefValue(value),root(NULL) { }
virtual ~ BinaryTree( ) { destroy ( root ) }//删除一棵二叉树
virtual int IsEmpty( ) { return root == NULL ;}//判树空
virtual BinTreeNode<Type> * Parent( BinTreeNode<Type>
*current ) { return root == NULL || root == current?NULL,
Parent( root,current ) ;}//求 *current 结点的父结点指针
virtual BinTreeNode<Type> * LeftChild( BinTreeNode<Type>
* current ) { return current != NULL? Current ->leftChild,NULL ; }
//求 *current 结点的左子结点指针
virtual BinTreeNode<Type> * RightChild( BinTreeNode<Type>
* current ) { return current != NULL? Current ->rightChild,NULL ; }
//求 *current 结点的右子结点指针
2011-7-18 9
virtual int Insert( const Type & item );//插入值为 item 的新结点
virtual int Find( const Type & item ) const ;//查找值为 item 的结点
const BinTreeNode<Type> * GetRoot( ) const { return root ; } //求根结点的指针
friend istream & operator >> ( istream & in,BinTreeNode<Type> & Tree );
//重载操作：输入数据元素并建立一棵二叉树 Tree
friend ostream & operator << ( ostream & out,BinTreeNode<Type> & Tree ) ;
//重载操作：输出一棵二叉树 Tree
Private:
BinTreeNode<Type> * root;//根结点指针
Type RefValue;//数据输入结束标志，仅用于输入
BinTreeNode<Type> * Parent( BinTreeNode<Type> * start,
BinTreeNode<Type> * current );
//求 start 树中 *current 结点的父结点指针
int Insert( BinTreeNode<Type> * & current,const Type & item );
//在 current 树中插入值为 item 的新结点
void Traverse(BinTreeNode<Type> * current,ostream & out ) const;
//遍历输出 current 二叉树
int Find ( BinTreeNode<Type> * current,const Type & item ) const ;
//在 current 树中查找值为 item 的结点
void destroy(( BinTreeNode<Type> * current );
//删除 current 树的所有结点
}
2011-7-18 10
二叉树的基本操作
（ 1）初始化操作 ——一般由构造函数实现
（ 2）建立一棵二叉树
（ 3）撤销一棵二叉树 ——可以由析构函数实现
（ 4）插入一个新结点
（ 5）删除一个结点
（ 6）查找
（ 7）判树空
（ 8）读取结点数据
（ 9）修改结点数据
（ 10）求二叉树的某一或某些性能（如结点数、高度、平衡度等）
（ 11）求根结点、父结点、左子结点、右子结点等结点的指针
（ 12）调整一棵二叉树，优化某一或某些性能
（ 13）二叉树遍历操作
（ 14）其他操作
2011-7-18 11
根据所定义的操作不同，可以有不同性能的二叉树
（ 1）线索化二叉树 ( Threaded Binary Tree )：在二叉树结点中增加前
驱指针和后继指针，使得在二叉树中查找当前结点的在某种遍
历方式下的前驱和后继结点很方便
（ 2）堆 ( Heap )：用来实现高效率的优先级队列的二叉树，采用顺序
存储结构。其特点是：树中任一结点的关键码均小（大）于或
等于它的左子结点和右子结点的关键码，称为最小（大）堆。
（ 3）霍夫曼树 (Huffman Tree ),带权路径长度 WPL 最小的（扩充）
二叉树。 WPL----Weighted Path Length
（ 4）二叉排序树 (Binary Sorting Tree )
二叉搜索树 (Binary Search Tree )
中序遍历为严格递增的二叉树。这种树可以提高搜索（查找）
效率。
（ 5）最优二叉搜索树：平均搜索长度最小的二叉搜索树。
（ 6） AVL 树：高度平衡的二叉搜索树，可以提高搜索效率，减小平
均搜索长度
（ 7）其他
2011-7-18 12
6.4 二叉树遍历 (Binary Tree Traversal ) 操作
遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的
访问可以是输出、修改等操作，根据实际需要而定。
遍历操作可以从一种非线性结构中得到相应的线性序列。
有不同顺序的遍历操作，对于二叉树有三种遍历操作：
先序遍历（ NLR） 中序遍历（ LNR） 后序遍历（ LRN）
访问根结点 中序遍历左子树 后序遍历左子树
先序遍历左子树 访问根结点 后序遍历右子树
先序遍历右子树 中序遍历右子树 访问根结点
可以看出，上述三种顺序的二叉树遍历操作都是递归定义的，
因此用递归算法实现很容易。
2011-7-18 13
二叉树的先序遍历操作递归算法
template <class Type> void BinaryTree<Type>:,PreOrder ( )
//公共函数：先序遍历二叉树，通过调用私有函数 PreOrder 实现
{
PreOrder ( root );
}
template <class Type> void BinaryTree<Type>,,
PreOrder ( BinTreeNode<Type> * current )
//私有函数：先序遍历根结点指针为 current 的二叉树
{ if ( current ! = NULL )
{//若二叉树不空，则先序遍历之
Visit ( current ); //访问根结点 *current
PreOrder ( current -> leftChild ); //先序遍历左子树
PreOrder ( current -> rightChild ); //先序遍历右子树
}
}
2011-7-18 14
二叉树定义中部分成员函数的实现：
template <class Type> void BinaryTree<Type>,,
destroy ( BinTreeNode<Type> * current )
//私有函数：若指针 current 不空，则删除根指针为 current 的子树
{ if ( current ! = NULL )
{ destroy ( current -> leftChild ) ; //删除左子树
destroy ( current -> rightChild ) ; //删除右子树
delete current ; } } //删除根结点 *current 。后序遍历
template <class Type> BinTreeNode<Type> * BinaryTree<Type>,:
Parent ( BinTreeNode<Type> * start,BinTreeNode<Type> * current )
//私有函数：在根结点为 *start 的二叉树中查找结点 *current 的父结点，若存
//在则返回其指针，否则返回 NULL
{ 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 ) ; }
//否则递归搜索右子树，若找到则返回其指针，否则返回 NULL 。
2011-7-18 15
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> ostream & operator << ( ostream & out,
BinaryTree<Type> & Tree )
//重载 inserting 操作符, << ‖, 用于直接输出一棵二叉树
{ out << ―Preorder traversal of binary tree,\n‖ ;
Tree, Traverse ( Tree, Root,out ) ; //先序遍历输出
out << endl ;
return out ;
}
2011-7-18 16
template <class Type> istream & operator >> ( istream & in,
BinaryTree<Type> & Tree )
//重载 abstracting 操作符, >> ‖,用于输入数据元素并同时创建一
棵
//二叉树 Tree
{
Type item ;
cout << ― Construct binary tree, \n ‖ ;
cout << ― input data ( end with ‖ << Tree.RefValue << ― ), ‖ ;
in >> item ;
while ( item != Tree.RefValue )
{
Tree.Insert ( item ) ; //将数据元素 item 插入到二叉树 Tree 中
cout << ― Input data ( end with ‖ << Tree.RefValue << ― ), ‖ ;
in >> item ;
}
return in ;
}
2011-7-18 17
7.4 二叉搜索树 (Binary Search Tree ) P235
定义：一棵二叉树称之为二叉搜索树，如果它满足以下条件：
它或者是空树；
或者左子树中结点的关键码均小于根结点的关键码，
并且右子树中结点的关键码均大于根结点的关键码,
并且左子树和右子树均为二叉搜索树。
显然，二叉搜索树的中序遍历的输出序列是一严格递增的有序序列
二叉搜索数的类定义：
2011-7-18 18
#include < iostream, h >
template <class Type> class BST ; //二叉搜索树类的前视声明
template <class Type> class BstNode, public BinTreeNode
//二叉搜索树结点类的定义。二叉搜索树的结点类是一般二叉树结点
//类的公有继承
{
friend class BST<Type>;//二叉搜索树类是二叉搜索树结点类的友元类
public:
BstNode( ),
leftChild( NULL ),rightChild( NULL ) { }
BstNode( const Type d ),
data( d ),leftChild( NULL ),rightChild( NULL ) { }
BstNode( const Type d=0,BstNode * L=NULL,BstNode *
R=NULL ), data( d ),leftChild( L ),rightChild( R ) { }
~BstNode( ) { }
protected,
Type data ;
BstNode<Type> * leftChild,* rightChild ;
}
2011-7-18 19
Template <class Type> class BST, BinaryTree
//
{ public:
BST ( ), root ( NULL ) { }
BST ( Type value ), RefValue(value),root(NULL) { }
~BST ( ) { MakeEmpty( root ) ；｝
const BST & operator = ( const BST & Tree ) ;
void MakeEmpty( ) ;
int Find( const Type & x ) const
{ return Find( x,root ) == NULL ; }
Type Min( ) ;
Type Max( ) ;
void Insert( const Type & x ) { Insert( x,root ) ; }
void Remove( const Type & x ) { Remove( x,root ) ; }
BstNode<Type> * Split( Type i,BST <Type> & B,
Type & x,BST<Type> & C );
2011-7-18 20
private:
BstNode<Type> * root ;
Type RefValue ;
BstNode<Type> * lastfound ;
void MakeEmpty( BstNode<Type> * & ptr ) ;
void Insert( const Type & x,BstNode<Type> * & ptr );
void Remove(const Type & x,BstNode<Type> * & ptr ) ;
BstNode<Type> * Find( const Type & x,
BstNode<Type> * ptr ) const ;
BstNode<Type> * Min( BstNode<Type> * ptr ) const ;
BstNode<Type> * Max( BstNode<Type> * ptr ) const ;
friend class BSTIterator<Type> ;
}
2011-7-18 21
7.4.2 二叉搜索树的搜索（查找）算法
（ 1）二叉搜索树的递归搜索算法
template <class Type> BstNode<Type> * BST<Type>,:
Find ( const Type & x,BstNode<Type> * ptr ) const
//私有函数，在以 ptr 为根指针的二叉搜索树中查找关键码为 x 的结
//点，若找到，则返回该结点的指针，否则返回空指针 NULL
{
if ( ptr == NULL ) return NULL ;
//根指针为空（即空树）返回空指针
else if ( x == ptr -> data ) return ptr ;
//根结点即为所查结点，查找成功，返回根结点指针
else if ( x < ptr -> data ) return Find ( x,ptr -> leftChild ) ;
//关键码小于根结点的关键码，递归搜索左子数
else return Find ( x,ptr -> rightChild ) ;
//关键码大于根结点的关键码，递归搜索右子数
}
2011-7-18 22
（ 2）二叉搜索树的非递归搜索算法（迭代搜索算法）
template <class Type> BstNode<Type> * BST<Type>,:
Find ( const Type & x,BstNode<Type> * ptr,* & fp ) const
//私有函数，入口时 fp=NULL,ptr 为根指针。本算法在以 ptr 为根指针的二
//叉搜索树中查找关键码为 x 的结点。若找到，则函数返回该结点的指针，
//否则函数返回空指针 NULL，一般情况下 fp 返回该结点的父结点的指针
{ if ( ptr == NULL ) return NULL ;//空树，返回 NULL
else //非空树，继续搜索
{ BstNode<Type> * temp = ptr ;//从根结点开始搜索
while (( temp != NULL ) && ( temp -> data != x ) )
//若当前结点存在且不是所找结点，则继续搜索
{ fp = temp ;//父结点指针
if ( temp -> data < x ) temp = temp -> rightChild ;//关键码 x 大于当
//前结点的关键码，则从当前结点开始沿右链前进一步
else temp = temp -> leftChild ; //关键码 x 小于当前结点的关键
//码，则从当前结点开始沿左链前进一步
}
if ( temp -> data == x ) return temp ;//搜索成功，返回结点指针
else return NULL ;//树中不存在所找结点，搜索失败，返回 NULL
}
}
2011-7-18 23
在上述算法中有一个指针的引用 fp,
BstNode<Type> * & fp ;
通过指针的引用可以从函数中返回一个被函数改变了的指针。
假定对上述算法作如下调用：
Template <class Type> int BST<Type>,,Find( const Type & x ) const
//
{ return Find( key,root,fatherptr ) == NULL ; }
2011-7-18 24
7.4.3 二叉搜索树的插入算法
template <class Type> void BST<Type>,,
Insert ( const Type & x,BstNode<Type> * & ptr )
//私有函数，在以 ptr 为根指针的二叉搜索树中插入关键码为 x 的结点。若在
//树中已存在关键码为 x 的结点，则不作插入。要求插入后仍然是一棵二叉
//搜索树。注意 ptr 是一个指针的引用参数，它可以自动改变相应的实参，实
//现操作效果的返回。如本算法中可以自动改变插入结点的父结点的左子指
//针或右子指针或根结点指针
{ if ( ptr == NULL ) //若原树为空树，则把关键码为 x 的结点就作为根结点
{ ptr = new BstNode<Type>( x,NULL ) ;//创建一新结点并作为根结点
if ( ptr == NULL )//检查内存分配是否成功
{ cerr << ―Out of space ‖ << endl ; exit(1) ;}
}
else if ( x < ptr -> data ) Insert( x,ptr -> leftChild ) ;
//若原树不空且 x 小于根结点的关键码，则递归插入左子树中
else if ( x > ptr -> data ) Insert( x,ptr -> rightChild ) ;
//若原树不空且 x 大于根结点的关键码，则递归插入右子树中
//若 x 等于根结点的关键码，则不作插入操作
}
2011-7-18 25
建立二叉搜索树的算法
template <class Type> BST<Type>,,BST ( Type value )
//构造函数，本算法通过输入一元素插入一结点的方法，将一输入的数据元
//素序列（以 value 作为结束标志）构建成一棵二叉搜索树
{ Type x ;
root = NULL ;//置空树
RefValue = value ;//设置输入结束标志
cin >> x ;//输入一个数据元素
while ( x != RefValue )//若输入的元素不是结束标志则继续
{ Insert ( x,root ) ;
//将输入的元素插入到根指针为 root 的二叉搜索树中。在插入第一
//个元素前根指针 root 为空，插入后 root 指向第一个结点,root 在
// Insert 函数中被改变。这是因为 root 所对应的形参是一个非常态
//的引用参数
cin >> x ;
}
}
通过本算法创建的二叉搜索树可能会很不平衡，极端情况下将退化成为一单
链表，从而失去了二叉搜索树高搜索效率的优点，因此需作调整。
2011-7-18 26
二叉搜索树的删除算法
template <class Type> void BST<Type>,:
Remove( const Type & x,BstNode<Type> * & ptr )
//私有函数，删除根指针为 ptr 的二叉搜索树中关键码为 x 的结点。要求删除
//后仍然是一棵根指针为 ptr 的二叉搜索树，并且不增加树的高度
{ BstNode<Type> * temp ;
if ( ptr != NULL )
if ( x < ptr -> data ) Remove( x,ptr -> leftChild ) ;
// x 结点在左子树中，递归删除左子树中的 x 结点
else if ( x > ptr -> data ) Remove( x,ptr -> rightChild ) ;
// x 结点在右子树中，递归删除右子树中的 x 结点
else if ( ptr -> leftChild != NULL && ptr -> rightChild !=NULL)
// x 结点就是根结点，删除根结点。若根的左右子树均不空
{ temp = Min( ptr -> rightChild ) ;
//则从右子树中查找最小结点
ptr -> data = temp -> data ;
//并用该结点数据代替根结点的数据
Remove( ptr -> data,ptr -> rightChild ) ;//最后将该结点删除
}
2011-7-18 27
else//否则根结点的左右子树不全
{ temp = ptr ;
if ( ptr -> leftChild == NULL ) ptr = ptr -> rightChild ;
//若无左子树，则直接将根指针指向右子结点以删除
//根结点。若此时又无右子树，则 ptr 变为空指针
else if ( ptr -> rightChild == NULL ) ptr = ptr -> leftChild ;
//若有左子树但无右子树，则直接将根指针指向左子
//结点以删除根结点
delete temp ;//释放被删除的根结点
}
}
template <class Type> BstNode<Type> * BST<Type>,:
Min( BstNode<Type> * ptr ) const
//私有函数，在以 ptr 为根指针的二叉搜索树中查找关键码最小的结点，并返
//回该结点的指针
{
//原理：从根结点开始沿着左链往下查找，第一个左子树为空的结点就是
//树中的关键码最小的结点
}
课堂作业：完成上述算法
2011-7-18 28
7.6 AVL树 —— 高度平衡的二叉搜索树
前述的二叉搜索树的插入和建立（通过插入实现）算法不考虑树
的平衡问题，因此有可能产生高度不平衡的二叉搜索树，极端情
况下将退化成一个单链表，失去了二叉搜索树的优点。因此在二
叉搜索树的插入过程中必须调整树的结构，使之平衡化。
AVL树的定义：
一棵 AVL树或者是空树，或者是具有下列性质的二叉搜索树：它
的左子树和右子树的高度之差的绝对值不超过 1 。
结点的平衡因子 ( balance factor ),
balance ＝ 该结点的右子树高度 － 该结点的左子树高度
对于 AVL树,| balance | <= 1
即 balance 只能取 － 1, 0, 1 三者之一
平衡化方法 ——平衡化旋转方法：
单旋转：左单旋转（左旋） RotateLeft
右单旋转（右旋） RotateRight
双旋转：先左后右双旋转（左平衡 LeftBalance ）
先右后左双旋转（右平衡 RightBalance ）
2011-7-18 29
AVL树的类定义：
template <class Type> class AVLTree
{ public:
struct AVLNode
//用 struct 定义 AVL树的结点类。在 struct 中缺省的访问级别
//是公有 ( public )的，而在 class 中缺省的访问级别是私有
//( private )的，除此之外 struct 和 class 是等价的
{ Type data ;
AVLNode<Type> * left,* right ;
int balance ;
AVLNode( ), left( NULL ),right( NULL ),balance( 0 ) { }
AVLNode( Type d,AVLNode<Type> * l = NULL,
AVLNode<Type> * r = NULL ),
data( d ),left( l ),right( r ),balance( 0 ) { }
} ;
2011-7-18 30
protected:
Type RefValue ;//结束标志，用于输入数据元素序列
AVLNode<Type> * root ;
int Insert( AVLNode<Type> * & tree,Type x,int & taller ) ;
void RotateLeft(AVLNode<Type> * Tree,AVLNode<Type> * & NewTree) ;
void RotateRight(AVLNode<Type> * Tree,AVLNode<Type> * &NewTree);
void LeftBalance( AVLNode<Type> * & Tree,int & taller ) ;
void RightBalance( AVLNode<Type> * & Tree,int & taller ) ;
int Depth( AVLNode<Type> * t ) const ;
public:
AVLTree( ), root( NULL ) {}
AVLTree( Type Ref ), RefValue( Ref ),root( NULL ) { }
int Insert( Type x ) { int taller ; return Insert( root,x,taller ) ; }
friend istream & operator >> ( istream & in,AVLTree<Type> & Tree ) ;
friend ostream & operator << (ostream & out,const AVLTree<Type> &Tree);
int Depth( ) const ;
}
2011-7-18 31
7.6.2 平衡化旋转处理
A 原树为 AVL树,在右子树中插入结点
（ 1）若向子树 E中插入一个结点导致
B C 子树 E的高度增加 1 —此时需要
作左单旋转处理（右右增 1）
D E （ 2）若向子树 D中插入一个结点导致
子树 D的高度增加 1—此时需要
作先右后左双旋转处理（右左增 1）
A 原树为 AVL树，在左子树中插入结点
（ 1）若向子树 E中插入一个结点导致
B C 子树 E的高度增加 1—此时需要
作右单旋转处理（左左增 1）
D E （ 2）若向子树 D中插入一个结点导致
子树 D的高度增加 1—此时需要
作先左后右双旋转处理（左右增 1）
2011-7-18 32
左右单旋转处理,（ 升 C 移 D 降 A）（ 升 B 移 E 降 A ）
A
B C
D E
C
A
B D
E
A
CB
ED
B
D A
E C
左单旋转处理
右单旋转处理
2011-7-18 33
template <class Type> void AVLTree<Type>,:
RotateLeft(AVLNode * Tree,AVLNode * & NewTree)
//对以 Tree 为根指针的二叉搜索树作左单旋转处理，使其成为一棵
//AVL 树。处理后的 AVL树的根指针为 NewTree
{ NewTree = Tree -> right ;//升 C，使 C成为新的根结点
Tree -> right = NewTree -> left ;//移 D，使 D子树成为 A的右子树
NewTree -> left = Tree ;//降 A，使 A子树成为 C的左子树
}
template <class Type> void AVLTree<Type>,:
RotateRight(AVLNode * Tree,AVLNode * & NewTree)
//对以 Tree 为根指针的二叉搜索树作右单旋转处理，使其成为一棵
//AVL 树。处理后的 AVL树的根指针为 NewTree
{ NewTree = Tree -> left ;//升 C，使 C成为新的根结点
Tree -> left = NewTree -> right ;//移 D，使 D子树成为 A的右子树
NewTree -> right = Tree ;//降 A，使 A子树成为 C的左子树
}
2011-7-18 34
先左后右双旋转处理
A
B C
D E
GF
A
C
B
E
D F
G
升 E降 B移 F
（对 B子树作左单旋转处理）
E
A
CG
B
D F
升 E降 A移 G
（对 A树作右单旋转处理）
2011-7-18 35
template <class Type> void AVLTree<Type>,:
LeftBalance(AVLNode * & Tree,int & taller )
//左平衡处理函数，当在左子树中插入一个结点后导致不平衡时调用该函数
//输入时 Tree 为左子树太高的非 AVL树的根指针，
//输入时 taller 应为 1,表示插入操作导致树的高度增加
//输出时 Tree 为平衡处理后的 AVL树的根指针
//输出时 taller 为 0表示处理后的新树的高度与插入前的高度一致。
{ if ( Tree -> balance < -1 )//左子树太高导致的不平衡
{AVLNode<Type> * leftsub = Tree -> left ;//定义左子树 B的指针
AVLNode<Type> * rightsub ;
switch( leftsub -> balance )
{ case –1, //新结点插入在 D子树中并使其高度增加，导致 A树的
//不平衡,需作右单旋转处理（参见图 7.25,P250 ）
Tree -> balance = 0 ;//处理后 A结点的平衡因子＝ 0
leftsub -> balance = 0 ; //处理后 B结点的平衡因子＝ 0
RotateRight( Tree,Tree ) ;//作右单旋转处理
taller = 0 ;//处理后 A树的高度不增加，上一层无需再处理
break ;
case 0, break ; //B结点的平衡因子等于 0并使其高度增加，说明新插
//入的结点就是 B结点，但插入 B结点不会使 A树不平衡（因插入前 A树是平
//衡的），因此这种情况不可能发生，因此不用理会它
2011-7-18 36
case 1, //新结点插入在 E 子树中并使 E子树和 B子树的高度增加，
//导致 A树的不平衡，需作先左后右双旋转平衡处理,
//参见图 7.26,P250
rightsub = leftsub -> right ;//rightsub 为 E子树的根指针
switch ( rightsub -> balance )
{ case –1, //新结点插入在 F子树中并使其高度增加，
//参见图 7.26 (d)
Tree -> balance = 1 ;//平衡处理后 A结点的平衡因子
leftsub -> balance = 0 ;//平衡处理后 B结点的平衡因子
break ;
case 0, // F子树与 G子树等高的情况，将图 7.26 (d) 中 G子树
//的高度改为 h 后计算 A结点和 B结点的平衡因子
Tree -> balance = 0 ;leftsub -> balance = 0 ;break;
//E 结点的平衡因子为 0，并且 E子树高度又增加，这只有一种情况，
//即插入的新结点就是 E结点,F和 G都是空树，并且 D和 C也是空树
case 1, // 新结点插入在 G子树中并使其高度增加，
//将图 7.26 (d) 中 G子树的高度改为 h, F子树的高度
//改为 h-1 后计算 A结点和 B结点的平衡因子
Tree -> balance = 0 ;leftsub -> balance = -1 ;break ;
}
2011-7-18 37
rightsub -> balance = 0 ;
//平衡处理后 E结点（新树的根结点）的平衡因子等于 0
RotateLeft ( leftsub,Tree -> left ) ;
//先对图 7.26(b) 中的 B子树进行左单旋转处理，处理后成为图 7.26(c)
RotateRight ( Tree,Tree ) ;
//后对图 7.26(c) 中的 A树进行右单旋转处理，处理后成为图 7.26(d)
taller = 0 ;//平衡处理完后，新树的高度与原树一样
}
}
2011-7-18 38
先右后左双旋转处理
A
B
C
D E
F G
A
B D
C
EG
F
D
A C
B F G E
升 D降 C移 G
C子树右单旋转
升 D降 A移 F
A树左单旋转
2011-7-18 39
template <class Type> void AVLTree<Type>,:
RightBalance(AVLNode * & Tree,int & taller )
//右平衡处理函数，当在右子树中插入一个结点后导致不平衡时调用该函数
//输入时 Tree 为右子树太高的非 AVL树的根指针
//输出时 Tree 为平衡处理后的 AVL树的根指针
//Taller 置为 0表示下一步无需再旋转。
{ if ( Tree -> balance >1 )//右子树太高导致的不平衡
AVLNode<Type> * rightsub = Tree -> right ;//定义右子树 C的指针
AVLNode<Type> * leftsub ;
switch( rightsub -> balance )
{ case 1, //右子树 C的根结点的平衡因子等于 1，则 C 的
//右子树 E 高于其左子树 D,需作左单旋转处理
//（参见图 7.24,P249 ）
Tree -> balance = 0 ;//处理后 A结点的平衡因子＝ 0
rightsub -> balance = 0 ; //处理后 C结点的平衡因子＝ 0
RotateLeft( Tree,Tree ) ;//作左单旋转处理
taller = 0 ;//表示下一步无需再旋转
break ;
case 0, break ; //在每插入一个结点后都进行平衡处理的话，
//此情况不可能发生
2011-7-18 40
case -1, // E 子树低于 D 子树的情况,参见图 7.27,P251
leftsub = rightsub -> left ;//leftsub 为 D子树的根指针
switch ( leftsub -> balance )
{ case 1, //G子树高于 F子树的情况，参见图 7.27 (d)
Tree -> balance = -1 ;//平衡处理后 A结点的平衡因子
rightsub -> balance = 0 ;//平衡处理后 C结点的平衡因子
break ;
case 0, // F子树与 G子树等高的情况，将图 7.27 (d) 中 F子树
//的高度改为 h 后计算 A结点和 C结点的平衡因子
Tree -> balance = 0 ;rightsub -> balance = 0 ;break;
case -1, // G子树低于 F子树情况，将图 7.27 (d) 中 G子树的
//高度改为 h -1,F子树的高度改为 h 后计算 A结点
//和 C结点的平衡因子
Tree -> balance = 0 ;rightsub -> balance = 1 ;break ;
}
leftsub -> balance = 0 ;//平衡处理后 D结点的平衡因子
RotateRight ( rightsub,Tree -> right ) ;//先对图 7.27(b) 中的
//C子树进行右单旋转处理，处理后成为图 7.27(c)
RotateLeft ( Tree,Tree ) ; //后对图 7.27(c) 中的 A树进行左单
//旋转处理，处理后成为图 7.27(d)
taller = 0 ;}}
2011-7-18 41
7.6.3 AVL树的插入操作算法
template <class Type> int AVLTree<Type>,:
Insert( AVLNode * & tree,Type x,int & taller )
//在以 tree 为根指针的 AVL树中插入值为 x 的新结点
//输入时 taller = 0
//如果插入成功，则函数返回 1，否则 函数返回 0
//若 tree 树中已存在值为 x 的结点或者内存分配失败，则插入操作失败
//如果插入后 tree 树的高度增加，则 taller 返回 1，否则 taller 返回 0
//要求成功插入后仍然是一棵 AVL树（因此可能需作平衡处理）
//成功插入后的新树的根指针仍为 tree
{ int success ;
if ( tree == NULL ) // tree 树为空树，则创建新结点并作为根结点即可
{ tree = new AVLNode( x ) ;
success = tree != NULL? 1, 0 ;
if ( success )//内存分配成功
{ taller = 1 ;//tree 树高度增加
tree -> balance = 0 ;// tree 树的平衡因子等于 0
}
}
2011-7-18 42
else if ( x < tree -> data ) // tree 树不空且 x 小于根结点的关键码
{ success = Insert( tree -> left,x,taller ) ;//递归插入左子树中
if ( success && taller )//插入成功并且左子树的高度增加了
switch ( tree -> balance )
{ case –1,// tree 树根结点的平衡因子原为－ 1，其左子树
//的高度增 1后，使得插入后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其左子树的
//高度增 1后，使得插入后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度增加了
tree -> balance = -1 ; break ;
case 1,// tree 树根结点的平衡因子原为 1，其左子树的
//高度增 1后，使得插入后的 tree 树根结点的平衡
//因子等于 0，因此对 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未增加
tree -> balance = 0 ; taller = 0 ; break ;
}
}
2011-7-18 43
else if ( x > tree -> data ) // tree 树不空且 x 大于根结点的关键码
{ success = Insert( tree -> right,x,taller ) ;//递归插入右子树中
if ( success && taller )//插入成功并且右子树的高度增加了
switch ( tree -> balance )
{ case 1,// tree 树根结点的平衡因子原为 1，其右子树
//的高度增 1后，使得插入后 tree 树根结点的平衡
//因子等于 2，因此对 tree 树需作右平衡处理
RightBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度增 1后，使得插入后的 tree 树根结点的平
//衡因子等于 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度增加了
tree -> balance = 1 ; break ;
case -1,// tree 树根的平衡因子原为 -1，其右子树的
//高度增 1后，使得插入后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未增加
tree -> balance = 0 ; taller = 0 ; break ;
}
}
2011-7-18 44
else success = 0 ; // x== tree -> data,即值为 x 的结点已存在，
//无需插入操作，认为插入操作失败
return success ;
}
2011-7-18 45
7.6.4 AVL树的删除操作算法
template <class Type> int AVLTree<Type>,:
Remove( AVLNode * & tree,Type x,int & taller )
//在以 tree 为根指针的 AVL树中删除值为 x 的新结点
//输入时 taller = 0
//如果删除成功，则函数返回 1，否则 函数返回 0
//若 tree 树中不存在值为 x 的结点，则删除操作失败
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求成功删除后仍然是一棵 AVL树（因此可能需作平衡处理）
//成功删除后的新树的根指针仍为 tree
{ int success ;
if ( tree == NULL ) success = 0 ;
// tree 树为空树，则删除失败（树中不存在所找结点）
else if ( x == tree -> data ) success = RootRemove( tree,taller ) ;
//所找结点即为根结点，则删除根结点。删除后的新树的根指针仍为 tree
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求成功删除后仍然是一棵 AVL树（因此可能需作平衡处理）
2011-7-18 46
else if ( x < tree -> data ) // tree 树不空且 x 小于根结点的关键码
{ success = Remove( tree -> left,x,taller ) ;//递归删除左子树中的 x
if ( success && taller )//删除成功并且左子树的高度降低了
switch ( tree -> balance )
{ case 1,// tree 树根结点的平衡因子原为 1，其左子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于 2，因此对 tree 树需作右平衡处理
RightBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其左子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = 1 ; taller = 0 ; break ;
case -1,// tree 树根的平衡因子原为－ 1，其左子树的
//高度减 1后，使得删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller = 1 ; break ;
}
}
2011-7-18 47
else if ( x > tree -> data ) // tree 树不空且 x 大于根结点的关键码
{ success = Remove( tree -> right,x,taller );//递归删除右子树中的 x
if ( success && taller )//删除成功并且右子树的高度降低了
switch ( tree -> balance )
{ case -1,// tree 树根结点的平衡因子原为－ 1，其右子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = -1 ; taller = 0 ; break ;
case 1,// tree 树根的平衡因子原为 1，其右子树的
//高度减 1后，使删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller =1 ; break ;
}
}
return success ; }
2011-7-18 48
7.6.5 AVL树根结点的删除操作算法
template <class Type> int AVLTree<Type>,:
RootRemove( AVLNode * & tree,int & taller )
//删除以 tree 为根指针的 AVL树的根结点
//输入时 taller = 0
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求删除后仍然是一棵 AVL树（因此可能需作平衡处理）
//删除后的新树的根指针仍为 tree
{ int success,bal ;
AVLNode * temp ;
if ( tree -> left != NULL && tree -> right !=NULL)
//若根的左右子树均不空
{ temp = Min( tree -> right ) ; //则从右子树中查找最小结点
bal = tree -> balance ;
tree -> data = temp -> data ;//并用该结点数据代替根结点的数据
tree -> balance = bal ;
success = Remove(tree -> right,tree -> data,taller ) ;
//最后将该结点删除，间接递归调用 Remove,删除后的右子树仍是一
//棵 AVL树，并由 taller 返回删除过程是否改变了右子树的高度
2011-7-18 49
if ( success && taller )//删除成功并且右子树的高度降低了
switch ( tree -> balance )
{ case -1,// tree 树根结点的平衡因子原为－ 1，其右子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = -1 ; taller = 0 ; break ;
case 1,// tree 树根的平衡因子原为 1，其右子树的
//高度减 1后，使删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller =1 ; break ;
}
}
2011-7-18 50
else//否则根结点的左右子树不全
{temp = tree ;
if ( tree -> left == NULL && tree -> right == NULL )//根结点为叶结点
{ tree = NULL ; taller = 1 ; }//删除后成为空树，高度降低
else if ( tree -> left == NULL ) //若无左子树，则右子树不空并且只有
//一个结点，因 tree 树是一棵 AVL树
{ tree = tree -> right ;//直接将右结点作为根结点
tree -> balance = 0 ;//新根结点无左右子树，因此平衡因子等于 0
taller = 1 ;//删除操作降低了 tree 树的高度
}
else //右子树空，左子树不空情况。此时左子树只有一个结点，
//因 tree 树是一棵 AVL树
{ tree = tree -> left ; //直接将左结点作为根结点
tree -> balance = 0 ; //新根结点无左右子树，因此平衡因子等于 0
taller = 1 ; //删除操作降低了 tree 树的高度
}
delete temp ;//释放被删除的根结点
}
return 1 ;// x 结点存在，删除肯定成功
}
2011-7-18 51
2011-7-18 52
2011-7-18 53
2011-7-18 54
2011-7-18 55
2011-7-18 56
2011-7-18 57
2011-7-18 58
2011-7-18 59
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
方格模板
2011-7-18 65
2011-7-18 66
2011-7-18 67
2011-7-18 68
2011-7-18 69
2011-7-18 70
2011-7-18 71
2011-7-18 72
2011-7-18 73
2011-7-18 74
2011-7-18 75
2011-7-18 76
2011-7-18 77
2011-7-18 78
2011-7-18 79
2011-7-18 80
2011-7-18 81
2011-7-18 82
2011-7-18 83
2011-7-18 84
2011-7-18 85
2011-7-18 86
2011-7-18 87
2011-7-18 88
2011-7-18 89
2011-7-18 90
第 6章 树和森林
非线性数据结构
实际中有许多树型结构的问题，用树型数据结构来解决非常自然
树型结构在计算机领域的应用非常广泛
6.1 树和森林的概念
树的定义：
树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树，
否则：
（ 1）有一个特定的称之为根 ( root )的结点，它只有直接后继，
但没有直接前驱；
（ 2）除根以外的其他结点可划分为若干个互不相交的有限集合，
每个集合又是一棵树，并且称之为根的子树 ( subTree )。每
棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多
个直接后继。
2011-7-18 2
树的示意图：
根
结
点
根结点
叶结点
分支结点
子树
子树
子树
Level 0
Level 1
Level 2
Level 3
结点的层次
2011-7-18 3
树的基本术语
结点的度 ( degree )：结点所拥有的子树数目
子女 ( child ) 结点：简称子结点
双亲 ( parent) 结点：简称父结点 ( father )
兄弟 ( sibling)结点：具有同一个父结点的结点
根 ( root ) 结点：
分支 ( branch )结点：又称非终端结点
叶 ( leaf ) 结点：又称终端结点
结点的层次 ( level ):根结点的层次为 0，子结点的层次等于其父结
点的层次加一
树的高度 ( depth ):等于树中最大的结点层次数。空树的高度为－ 1
树的度 ( degree ):等于树中最大的结点度数
有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，
否则就成为另一棵树了。
无序树：树中结点的各子树之间的先后次序无意义，可以互换
森林 ( forest ):若干棵树的集合
2011-7-18 4
6.2 二叉树 ( Binary Tree )
二叉树是树的基础，一般的树可以转化为二叉树来处理。
6.2.1 二叉树的定义
一棵二叉树是一有限结点的集合，该集合或者为空（空二叉
树），或者是由一个根结点及其下的两棵互不相交的子二叉树构
成，其中左边的称为左子树，右边的称为右子树。
二叉树是一棵度数 <= 2 的有序树。
6.2.2 二叉树的性质
（ 1）二叉树的第 i 层的结点数 <=
（ 2）高度为 k 的二叉树的最大结点数＝ ( k >= -1)
满二叉树 ( Full Binary Tree )：叶结点在同一层，非叶结点的度数均
为 2 的二叉树（参见图 6.3a ）
完全二叉树 ( Complete Binary Tree ),按从上到下、从左到右顺序
编号一棵满二叉树，并按从大到小的顺序连续删除
该满二叉树的若干个结点后剩下的二叉树称为一棵
完全二叉树（参见图 6.3b ）
2 i
2k+1- 1
2011-7-18 5
完全二叉树的性质和顺序存储结构
（ 1）具有 n 个结点的完全二叉树的高度 = log2 ( n + 1 ) – 1
（ 2）若将一棵按前述原则编号的完全二叉树，按其编号顺序存入一
个一维数组中，则有：
结点 i 的左子结点下标 = 2* i + 1 < n
结点 i 的右子结点下标 = 2* i + 2 < n
结点 i 的父结点下标 = ( i – 1 ) / 2 的下取整值
另外注意：根结点（下标为 0）无父结点
由上可知，完全二叉树的父 ——左子、父 ——右子之间的
关系可以通过相应结点的下标之间的简单数学关系完全地表示
出来，因此可以采用顺序存储结构来存储完全二叉树。（参见
教材 6.3.1 数组表示）
顺序存储结构用于动态性较小的完全二叉树的存储不失为
一种简单有效的方法，但不通用。树型数据结构一般采用链式存
储方式来存储。
2011-7-18 6
6.3.2 二叉树的链式存储结构 —— 二叉（三叉）链表结构
二叉链表结构：
左子指针 数据元素 右子指针
三叉链表结构：
左子指针 数据元素 右子指针
父指针
leftChild data rightChild
leftChild data father rightChild
2011-7-18 7
二叉链表结构的二叉树结点（简称二叉树结点）的类定义：
template <class Type> class BinaryTree;//二叉树类声明
template <class Type> class BinTreeNode//二叉树结点类定义
{
friend class BinaryTree<Type>;//二叉树类是二叉树结点类的友元
public:
BinTreeNode( ),leftChild(NULL),rightChild(NULL) { }
//构造函数
BinTreeNode( Type item,BinTreeNode<Type> * left = NULL,
BinTreeNode<Type> * right = NULL):data(item),
leftChild(left),rightChild(right) { }//构造函数
… // 其他成员函数
private:
BinTreeNode<Type> * leftChild,* rightChild ;
//左子指针、右子指针
Type data;//数据元素
}
2011-7-18 8
二叉链表结构的二叉树的类定义
template <class Type> class BinaryTree
{ public:
BinaryTree( ), root(NULL) { }//创建一棵空二叉树
BinaryTree( Type value ), RefValue(value),root(NULL) { }
virtual ~ BinaryTree( ) { destroy ( root ) }//删除一棵二叉树
virtual int IsEmpty( ) { return root == NULL ;}//判树空
virtual BinTreeNode<Type> * Parent( BinTreeNode<Type>
*current ) { return root == NULL || root == current?NULL,
Parent( root,current ) ;}//求 *current 结点的父结点指针
virtual BinTreeNode<Type> * LeftChild( BinTreeNode<Type>
* current ) { return current != NULL? Current ->leftChild,NULL ; }
//求 *current 结点的左子结点指针
virtual BinTreeNode<Type> * RightChild( BinTreeNode<Type>
* current ) { return current != NULL? Current ->rightChild,NULL ; }
//求 *current 结点的右子结点指针
2011-7-18 9
virtual int Insert( const Type & item );//插入值为 item 的新结点
virtual int Find( const Type & item ) const ;//查找值为 item 的结点
const BinTreeNode<Type> * GetRoot( ) const { return root ; } //求根结点的指针
friend istream & operator >> ( istream & in,BinTreeNode<Type> & Tree );
//重载操作：输入数据元素并建立一棵二叉树 Tree
friend ostream & operator << ( ostream & out,BinTreeNode<Type> & Tree ) ;
//重载操作：输出一棵二叉树 Tree
Private:
BinTreeNode<Type> * root;//根结点指针
Type RefValue;//数据输入结束标志，仅用于输入
BinTreeNode<Type> * Parent( BinTreeNode<Type> * start,
BinTreeNode<Type> * current );
//求 start 树中 *current 结点的父结点指针
int Insert( BinTreeNode<Type> * & current,const Type & item );
//在 current 树中插入值为 item 的新结点
void Traverse(BinTreeNode<Type> * current,ostream & out ) const;
//遍历输出 current 二叉树
int Find ( BinTreeNode<Type> * current,const Type & item ) const ;
//在 current 树中查找值为 item 的结点
void destroy(( BinTreeNode<Type> * current );
//删除 current 树的所有结点
}
2011-7-18 10
二叉树的基本操作
（ 1）初始化操作 ——一般由构造函数实现
（ 2）建立一棵二叉树
（ 3）撤销一棵二叉树 ——可以由析构函数实现
（ 4）插入一个新结点
（ 5）删除一个结点
（ 6）查找
（ 7）判树空
（ 8）读取结点数据
（ 9）修改结点数据
（ 10）求二叉树的某一或某些性能（如结点数、高度、平衡度等）
（ 11）求根结点、父结点、左子结点、右子结点等结点的指针
（ 12）调整一棵二叉树，优化某一或某些性能
（ 13）二叉树遍历操作
（ 14）其他操作
2011-7-18 11
根据所定义的操作不同，可以有不同性能的二叉树
（ 1）线索化二叉树 ( Threaded Binary Tree )：在二叉树结点中增加前
驱指针和后继指针，使得在二叉树中查找当前结点的在某种遍
历方式下的前驱和后继结点很方便
（ 2）堆 ( Heap )：用来实现高效率的优先级队列的二叉树，采用顺序
存储结构。其特点是：树中任一结点的关键码均小（大）于或
等于它的左子结点和右子结点的关键码，称为最小（大）堆。
（ 3）霍夫曼树 (Huffman Tree ),带权路径长度 WPL 最小的（扩充）
二叉树。 WPL----Weighted Path Length
（ 4）二叉排序树 (Binary Sorting Tree )
二叉搜索树 (Binary Search Tree )
中序遍历为严格递增的二叉树。这种树可以提高搜索（查找）
效率。
（ 5）最优二叉搜索树：平均搜索长度最小的二叉搜索树。
（ 6） AVL 树：高度平衡的二叉搜索树，可以提高搜索效率，减小平
均搜索长度
（ 7）其他
2011-7-18 12
6.4 二叉树遍历 (Binary Tree Traversal ) 操作
遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的
访问可以是输出、修改等操作，根据实际需要而定。
遍历操作可以从一种非线性结构中得到相应的线性序列。
有不同顺序的遍历操作，对于二叉树有三种遍历操作：
先序遍历（ NLR） 中序遍历（ LNR） 后序遍历（ LRN）
访问根结点 中序遍历左子树 后序遍历左子树
先序遍历左子树 访问根结点 后序遍历右子树
先序遍历右子树 中序遍历右子树 访问根结点
可以看出，上述三种顺序的二叉树遍历操作都是递归定义的，
因此用递归算法实现很容易。
2011-7-18 13
二叉树的先序遍历操作递归算法
template <class Type> void BinaryTree<Type>:,PreOrder ( )
//公共函数：先序遍历二叉树，通过调用私有函数 PreOrder 实现
{
PreOrder ( root );
}
template <class Type> void BinaryTree<Type>,,
PreOrder ( BinTreeNode<Type> * current )
//私有函数：先序遍历根结点指针为 current 的二叉树
{ if ( current ! = NULL )
{//若二叉树不空，则先序遍历之
Visit ( current ); //访问根结点 *current
PreOrder ( current -> leftChild ); //先序遍历左子树
PreOrder ( current -> rightChild ); //先序遍历右子树
}
}
2011-7-18 14
二叉树定义中部分成员函数的实现：
template <class Type> void BinaryTree<Type>,,
destroy ( BinTreeNode<Type> * current )
//私有函数：若指针 current 不空，则删除根指针为 current 的子树
{ if ( current ! = NULL )
{ destroy ( current -> leftChild ) ; //删除左子树
destroy ( current -> rightChild ) ; //删除右子树
delete current ; } } //删除根结点 *current 。后序遍历
template <class Type> BinTreeNode<Type> * BinaryTree<Type>,:
Parent ( BinTreeNode<Type> * start,BinTreeNode<Type> * current )
//私有函数：在根结点为 *start 的二叉树中查找结点 *current 的父结点，若存
//在则返回其指针，否则返回 NULL
{ 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 ) ; }
//否则递归搜索右子树，若找到则返回其指针，否则返回 NULL 。
2011-7-18 15
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> ostream & operator << ( ostream & out,
BinaryTree<Type> & Tree )
//重载 inserting 操作符, << ‖, 用于直接输出一棵二叉树
{ out << ―Preorder traversal of binary tree,\n‖ ;
Tree, Traverse ( Tree, Root,out ) ; //先序遍历输出
out << endl ;
return out ;
}
2011-7-18 16
template <class Type> istream & operator >> ( istream & in,
BinaryTree<Type> & Tree )
//重载 abstracting 操作符, >> ‖,用于输入数据元素并同时创建一
棵
//二叉树 Tree
{
Type item ;
cout << ― Construct binary tree, \n ‖ ;
cout << ― input data ( end with ‖ << Tree.RefValue << ― ), ‖ ;
in >> item ;
while ( item != Tree.RefValue )
{
Tree.Insert ( item ) ; //将数据元素 item 插入到二叉树 Tree 中
cout << ― Input data ( end with ‖ << Tree.RefValue << ― ), ‖ ;
in >> item ;
}
return in ;
}
2011-7-18 17
7.4 二叉搜索树 (Binary Search Tree ) P235
定义：一棵二叉树称之为二叉搜索树，如果它满足以下条件：
它或者是空树；
或者左子树中结点的关键码均小于根结点的关键码，
并且右子树中结点的关键码均大于根结点的关键码,
并且左子树和右子树均为二叉搜索树。
显然，二叉搜索树的中序遍历的输出序列是一严格递增的有序序列
二叉搜索数的类定义：
2011-7-18 18
#include < iostream, h >
template <class Type> class BST ; //二叉搜索树类的前视声明
template <class Type> class BstNode, public BinTreeNode
//二叉搜索树结点类的定义。二叉搜索树的结点类是一般二叉树结点
//类的公有继承
{
friend class BST<Type>;//二叉搜索树类是二叉搜索树结点类的友元类
public:
BstNode( ),
leftChild( NULL ),rightChild( NULL ) { }
BstNode( const Type d ),
data( d ),leftChild( NULL ),rightChild( NULL ) { }
BstNode( const Type d=0,BstNode * L=NULL,BstNode *
R=NULL ), data( d ),leftChild( L ),rightChild( R ) { }
~BstNode( ) { }
protected,
Type data ;
BstNode<Type> * leftChild,* rightChild ;
}
2011-7-18 19
Template <class Type> class BST, BinaryTree
//
{ public:
BST ( ), root ( NULL ) { }
BST ( Type value ), RefValue(value),root(NULL) { }
~BST ( ) { MakeEmpty( root ) ；｝
const BST & operator = ( const BST & Tree ) ;
void MakeEmpty( ) ;
int Find( const Type & x ) const
{ return Find( x,root ) == NULL ; }
Type Min( ) ;
Type Max( ) ;
void Insert( const Type & x ) { Insert( x,root ) ; }
void Remove( const Type & x ) { Remove( x,root ) ; }
BstNode<Type> * Split( Type i,BST <Type> & B,
Type & x,BST<Type> & C );
2011-7-18 20
private:
BstNode<Type> * root ;
Type RefValue ;
BstNode<Type> * lastfound ;
void MakeEmpty( BstNode<Type> * & ptr ) ;
void Insert( const Type & x,BstNode<Type> * & ptr );
void Remove(const Type & x,BstNode<Type> * & ptr ) ;
BstNode<Type> * Find( const Type & x,
BstNode<Type> * ptr ) const ;
BstNode<Type> * Min( BstNode<Type> * ptr ) const ;
BstNode<Type> * Max( BstNode<Type> * ptr ) const ;
friend class BSTIterator<Type> ;
}
2011-7-18 21
7.4.2 二叉搜索树的搜索（查找）算法
（ 1）二叉搜索树的递归搜索算法
template <class Type> BstNode<Type> * BST<Type>,:
Find ( const Type & x,BstNode<Type> * ptr ) const
//私有函数，在以 ptr 为根指针的二叉搜索树中查找关键码为 x 的结
//点，若找到，则返回该结点的指针，否则返回空指针 NULL
{
if ( ptr == NULL ) return NULL ;
//根指针为空（即空树）返回空指针
else if ( x == ptr -> data ) return ptr ;
//根结点即为所查结点，查找成功，返回根结点指针
else if ( x < ptr -> data ) return Find ( x,ptr -> leftChild ) ;
//关键码小于根结点的关键码，递归搜索左子数
else return Find ( x,ptr -> rightChild ) ;
//关键码大于根结点的关键码，递归搜索右子数
}
2011-7-18 22
（ 2）二叉搜索树的非递归搜索算法（迭代搜索算法）
template <class Type> BstNode<Type> * BST<Type>,:
Find ( const Type & x,BstNode<Type> * ptr,* & fp ) const
//私有函数，入口时 fp=NULL,ptr 为根指针。本算法在以 ptr 为根指针的二
//叉搜索树中查找关键码为 x 的结点。若找到，则函数返回该结点的指针，
//否则函数返回空指针 NULL，一般情况下 fp 返回该结点的父结点的指针
{ if ( ptr == NULL ) return NULL ;//空树，返回 NULL
else //非空树，继续搜索
{ BstNode<Type> * temp = ptr ;//从根结点开始搜索
while (( temp != NULL ) && ( temp -> data != x ) )
//若当前结点存在且不是所找结点，则继续搜索
{ fp = temp ;//父结点指针
if ( temp -> data < x ) temp = temp -> rightChild ;//关键码 x 大于当
//前结点的关键码，则从当前结点开始沿右链前进一步
else temp = temp -> leftChild ; //关键码 x 小于当前结点的关键
//码，则从当前结点开始沿左链前进一步
}
if ( temp -> data == x ) return temp ;//搜索成功，返回结点指针
else return NULL ;//树中不存在所找结点，搜索失败，返回 NULL
}
}
2011-7-18 23
在上述算法中有一个指针的引用 fp,
BstNode<Type> * & fp ;
通过指针的引用可以从函数中返回一个被函数改变了的指针。
假定对上述算法作如下调用：
Template <class Type> int BST<Type>,,Find( const Type & x ) const
//
{ return Find( key,root,fatherptr ) == NULL ; }
2011-7-18 24
7.4.3 二叉搜索树的插入算法
template <class Type> void BST<Type>,,
Insert ( const Type & x,BstNode<Type> * & ptr )
//私有函数，在以 ptr 为根指针的二叉搜索树中插入关键码为 x 的结点。若在
//树中已存在关键码为 x 的结点，则不作插入。要求插入后仍然是一棵二叉
//搜索树。注意 ptr 是一个指针的引用参数，它可以自动改变相应的实参，实
//现操作效果的返回。如本算法中可以自动改变插入结点的父结点的左子指
//针或右子指针或根结点指针
{ if ( ptr == NULL ) //若原树为空树，则把关键码为 x 的结点就作为根结点
{ ptr = new BstNode<Type>( x,NULL ) ;//创建一新结点并作为根结点
if ( ptr == NULL )//检查内存分配是否成功
{ cerr << ―Out of space ‖ << endl ; exit(1) ;}
}
else if ( x < ptr -> data ) Insert( x,ptr -> leftChild ) ;
//若原树不空且 x 小于根结点的关键码，则递归插入左子树中
else if ( x > ptr -> data ) Insert( x,ptr -> rightChild ) ;
//若原树不空且 x 大于根结点的关键码，则递归插入右子树中
//若 x 等于根结点的关键码，则不作插入操作
}
2011-7-18 25
建立二叉搜索树的算法
template <class Type> BST<Type>,,BST ( Type value )
//构造函数，本算法通过输入一元素插入一结点的方法，将一输入的数据元
//素序列（以 value 作为结束标志）构建成一棵二叉搜索树
{ Type x ;
root = NULL ;//置空树
RefValue = value ;//设置输入结束标志
cin >> x ;//输入一个数据元素
while ( x != RefValue )//若输入的元素不是结束标志则继续
{ Insert ( x,root ) ;
//将输入的元素插入到根指针为 root 的二叉搜索树中。在插入第一
//个元素前根指针 root 为空，插入后 root 指向第一个结点,root 在
// Insert 函数中被改变。这是因为 root 所对应的形参是一个非常态
//的引用参数
cin >> x ;
}
}
通过本算法创建的二叉搜索树可能会很不平衡，极端情况下将退化成为一单
链表，从而失去了二叉搜索树高搜索效率的优点，因此需作调整。
2011-7-18 26
二叉搜索树的删除算法
template <class Type> void BST<Type>,:
Remove( const Type & x,BstNode<Type> * & ptr )
//私有函数，删除根指针为 ptr 的二叉搜索树中关键码为 x 的结点。要求删除
//后仍然是一棵根指针为 ptr 的二叉搜索树，并且不增加树的高度
{ BstNode<Type> * temp ;
if ( ptr != NULL )
if ( x < ptr -> data ) Remove( x,ptr -> leftChild ) ;
// x 结点在左子树中，递归删除左子树中的 x 结点
else if ( x > ptr -> data ) Remove( x,ptr -> rightChild ) ;
// x 结点在右子树中，递归删除右子树中的 x 结点
else if ( ptr -> leftChild != NULL && ptr -> rightChild !=NULL)
// x 结点就是根结点，删除根结点。若根的左右子树均不空
{ temp = Min( ptr -> rightChild ) ;
//则从右子树中查找最小结点
ptr -> data = temp -> data ;
//并用该结点数据代替根结点的数据
Remove( ptr -> data,ptr -> rightChild ) ;//最后将该结点删除
}
2011-7-18 27
else//否则根结点的左右子树不全
{ temp = ptr ;
if ( ptr -> leftChild == NULL ) ptr = ptr -> rightChild ;
//若无左子树，则直接将根指针指向右子结点以删除
//根结点。若此时又无右子树，则 ptr 变为空指针
else if ( ptr -> rightChild == NULL ) ptr = ptr -> leftChild ;
//若有左子树但无右子树，则直接将根指针指向左子
//结点以删除根结点
delete temp ;//释放被删除的根结点
}
}
template <class Type> BstNode<Type> * BST<Type>,:
Min( BstNode<Type> * ptr ) const
//私有函数，在以 ptr 为根指针的二叉搜索树中查找关键码最小的结点，并返
//回该结点的指针
{
//原理：从根结点开始沿着左链往下查找，第一个左子树为空的结点就是
//树中的关键码最小的结点
}
课堂作业：完成上述算法
2011-7-18 28
7.6 AVL树 —— 高度平衡的二叉搜索树
前述的二叉搜索树的插入和建立（通过插入实现）算法不考虑树
的平衡问题，因此有可能产生高度不平衡的二叉搜索树，极端情
况下将退化成一个单链表，失去了二叉搜索树的优点。因此在二
叉搜索树的插入过程中必须调整树的结构，使之平衡化。
AVL树的定义：
一棵 AVL树或者是空树，或者是具有下列性质的二叉搜索树：它
的左子树和右子树的高度之差的绝对值不超过 1 。
结点的平衡因子 ( balance factor ),
balance ＝ 该结点的右子树高度 － 该结点的左子树高度
对于 AVL树,| balance | <= 1
即 balance 只能取 － 1, 0, 1 三者之一
平衡化方法 ——平衡化旋转方法：
单旋转：左单旋转（左旋） RotateLeft
右单旋转（右旋） RotateRight
双旋转：先左后右双旋转（左平衡 LeftBalance ）
先右后左双旋转（右平衡 RightBalance ）
2011-7-18 29
AVL树的类定义：
template <class Type> class AVLTree
{ public:
struct AVLNode
//用 struct 定义 AVL树的结点类。在 struct 中缺省的访问级别
//是公有 ( public )的，而在 class 中缺省的访问级别是私有
//( private )的，除此之外 struct 和 class 是等价的
{ Type data ;
AVLNode<Type> * left,* right ;
int balance ;
AVLNode( ), left( NULL ),right( NULL ),balance( 0 ) { }
AVLNode( Type d,AVLNode<Type> * l = NULL,
AVLNode<Type> * r = NULL ),
data( d ),left( l ),right( r ),balance( 0 ) { }
} ;
2011-7-18 30
protected:
Type RefValue ;//结束标志，用于输入数据元素序列
AVLNode<Type> * root ;
int Insert( AVLNode<Type> * & tree,Type x,int & taller ) ;
void RotateLeft(AVLNode<Type> * Tree,AVLNode<Type> * & NewTree) ;
void RotateRight(AVLNode<Type> * Tree,AVLNode<Type> * &NewTree);
void LeftBalance( AVLNode<Type> * & Tree,int & taller ) ;
void RightBalance( AVLNode<Type> * & Tree,int & taller ) ;
int Depth( AVLNode<Type> * t ) const ;
public:
AVLTree( ), root( NULL ) {}
AVLTree( Type Ref ), RefValue( Ref ),root( NULL ) { }
int Insert( Type x ) { int taller ; return Insert( root,x,taller ) ; }
friend istream & operator >> ( istream & in,AVLTree<Type> & Tree ) ;
friend ostream & operator << (ostream & out,const AVLTree<Type> &Tree);
int Depth( ) const ;
}
2011-7-18 31
7.6.2 平衡化旋转处理
A 原树为 AVL树,在右子树中插入结点
（ 1）若向子树 E中插入一个结点导致
B C 子树 E的高度增加 1 —此时需要
作左单旋转处理（右右增 1）
D E （ 2）若向子树 D中插入一个结点导致
子树 D的高度增加 1—此时需要
作先右后左双旋转处理（右左增 1）
A 原树为 AVL树，在左子树中插入结点
（ 1）若向子树 E中插入一个结点导致
B C 子树 E的高度增加 1—此时需要
作右单旋转处理（左左增 1）
D E （ 2）若向子树 D中插入一个结点导致
子树 D的高度增加 1—此时需要
作先左后右双旋转处理（左右增 1）
2011-7-18 32
左右单旋转处理,（ 升 C 移 D 降 A）（ 升 B 移 E 降 A ）
A
B C
D E
C
A
B D
E
A
CB
ED
B
D A
E C
左单旋转处理
右单旋转处理
2011-7-18 33
template <class Type> void AVLTree<Type>,:
RotateLeft(AVLNode * Tree,AVLNode * & NewTree)
//对以 Tree 为根指针的二叉搜索树作左单旋转处理，使其成为一棵
//AVL 树。处理后的 AVL树的根指针为 NewTree
{ NewTree = Tree -> right ;//升 C，使 C成为新的根结点
Tree -> right = NewTree -> left ;//移 D，使 D子树成为 A的右子树
NewTree -> left = Tree ;//降 A，使 A子树成为 C的左子树
}
template <class Type> void AVLTree<Type>,:
RotateRight(AVLNode * Tree,AVLNode * & NewTree)
//对以 Tree 为根指针的二叉搜索树作右单旋转处理，使其成为一棵
//AVL 树。处理后的 AVL树的根指针为 NewTree
{ NewTree = Tree -> left ;//升 C，使 C成为新的根结点
Tree -> left = NewTree -> right ;//移 D，使 D子树成为 A的右子树
NewTree -> right = Tree ;//降 A，使 A子树成为 C的左子树
}
2011-7-18 34
先左后右双旋转处理
A
B C
D E
GF
A
C
B
E
D F
G
升 E降 B移 F
（对 B子树作左单旋转处理）
E
A
CG
B
D F
升 E降 A移 G
（对 A树作右单旋转处理）
2011-7-18 35
template <class Type> void AVLTree<Type>,:
LeftBalance(AVLNode * & Tree,int & taller )
//左平衡处理函数，当在左子树中插入一个结点后导致不平衡时调用该函数
//输入时 Tree 为左子树太高的非 AVL树的根指针，
//输入时 taller 应为 1,表示插入操作导致树的高度增加
//输出时 Tree 为平衡处理后的 AVL树的根指针
//输出时 taller 为 0表示处理后的新树的高度与插入前的高度一致。
{ if ( Tree -> balance < -1 )//左子树太高导致的不平衡
{AVLNode<Type> * leftsub = Tree -> left ;//定义左子树 B的指针
AVLNode<Type> * rightsub ;
switch( leftsub -> balance )
{ case –1, //新结点插入在 D子树中并使其高度增加，导致 A树的
//不平衡,需作右单旋转处理（参见图 7.25,P250 ）
Tree -> balance = 0 ;//处理后 A结点的平衡因子＝ 0
leftsub -> balance = 0 ; //处理后 B结点的平衡因子＝ 0
RotateRight( Tree,Tree ) ;//作右单旋转处理
taller = 0 ;//处理后 A树的高度不增加，上一层无需再处理
break ;
case 0, break ; //B结点的平衡因子等于 0并使其高度增加，说明新插
//入的结点就是 B结点，但插入 B结点不会使 A树不平衡（因插入前 A树是平
//衡的），因此这种情况不可能发生，因此不用理会它
2011-7-18 36
case 1, //新结点插入在 E 子树中并使 E子树和 B子树的高度增加，
//导致 A树的不平衡，需作先左后右双旋转平衡处理,
//参见图 7.26,P250
rightsub = leftsub -> right ;//rightsub 为 E子树的根指针
switch ( rightsub -> balance )
{ case –1, //新结点插入在 F子树中并使其高度增加，
//参见图 7.26 (d)
Tree -> balance = 1 ;//平衡处理后 A结点的平衡因子
leftsub -> balance = 0 ;//平衡处理后 B结点的平衡因子
break ;
case 0, // F子树与 G子树等高的情况，将图 7.26 (d) 中 G子树
//的高度改为 h 后计算 A结点和 B结点的平衡因子
Tree -> balance = 0 ;leftsub -> balance = 0 ;break;
//E 结点的平衡因子为 0，并且 E子树高度又增加，这只有一种情况，
//即插入的新结点就是 E结点,F和 G都是空树，并且 D和 C也是空树
case 1, // 新结点插入在 G子树中并使其高度增加，
//将图 7.26 (d) 中 G子树的高度改为 h, F子树的高度
//改为 h-1 后计算 A结点和 B结点的平衡因子
Tree -> balance = 0 ;leftsub -> balance = -1 ;break ;
}
2011-7-18 37
rightsub -> balance = 0 ;
//平衡处理后 E结点（新树的根结点）的平衡因子等于 0
RotateLeft ( leftsub,Tree -> left ) ;
//先对图 7.26(b) 中的 B子树进行左单旋转处理，处理后成为图 7.26(c)
RotateRight ( Tree,Tree ) ;
//后对图 7.26(c) 中的 A树进行右单旋转处理，处理后成为图 7.26(d)
taller = 0 ;//平衡处理完后，新树的高度与原树一样
}
}
2011-7-18 38
先右后左双旋转处理
A
B
C
D E
F G
A
B D
C
EG
F
D
A C
B F G E
升 D降 C移 G
C子树右单旋转
升 D降 A移 F
A树左单旋转
2011-7-18 39
template <class Type> void AVLTree<Type>,:
RightBalance(AVLNode * & Tree,int & taller )
//右平衡处理函数，当在右子树中插入一个结点后导致不平衡时调用该函数
//输入时 Tree 为右子树太高的非 AVL树的根指针
//输出时 Tree 为平衡处理后的 AVL树的根指针
//Taller 置为 0表示下一步无需再旋转。
{ if ( Tree -> balance >1 )//右子树太高导致的不平衡
AVLNode<Type> * rightsub = Tree -> right ;//定义右子树 C的指针
AVLNode<Type> * leftsub ;
switch( rightsub -> balance )
{ case 1, //右子树 C的根结点的平衡因子等于 1，则 C 的
//右子树 E 高于其左子树 D,需作左单旋转处理
//（参见图 7.24,P249 ）
Tree -> balance = 0 ;//处理后 A结点的平衡因子＝ 0
rightsub -> balance = 0 ; //处理后 C结点的平衡因子＝ 0
RotateLeft( Tree,Tree ) ;//作左单旋转处理
taller = 0 ;//表示下一步无需再旋转
break ;
case 0, break ; //在每插入一个结点后都进行平衡处理的话，
//此情况不可能发生
2011-7-18 40
case -1, // E 子树低于 D 子树的情况,参见图 7.27,P251
leftsub = rightsub -> left ;//leftsub 为 D子树的根指针
switch ( leftsub -> balance )
{ case 1, //G子树高于 F子树的情况，参见图 7.27 (d)
Tree -> balance = -1 ;//平衡处理后 A结点的平衡因子
rightsub -> balance = 0 ;//平衡处理后 C结点的平衡因子
break ;
case 0, // F子树与 G子树等高的情况，将图 7.27 (d) 中 F子树
//的高度改为 h 后计算 A结点和 C结点的平衡因子
Tree -> balance = 0 ;rightsub -> balance = 0 ;break;
case -1, // G子树低于 F子树情况，将图 7.27 (d) 中 G子树的
//高度改为 h -1,F子树的高度改为 h 后计算 A结点
//和 C结点的平衡因子
Tree -> balance = 0 ;rightsub -> balance = 1 ;break ;
}
leftsub -> balance = 0 ;//平衡处理后 D结点的平衡因子
RotateRight ( rightsub,Tree -> right ) ;//先对图 7.27(b) 中的
//C子树进行右单旋转处理，处理后成为图 7.27(c)
RotateLeft ( Tree,Tree ) ; //后对图 7.27(c) 中的 A树进行左单
//旋转处理，处理后成为图 7.27(d)
taller = 0 ;}}
2011-7-18 41
7.6.3 AVL树的插入操作算法
template <class Type> int AVLTree<Type>,:
Insert( AVLNode * & tree,Type x,int & taller )
//在以 tree 为根指针的 AVL树中插入值为 x 的新结点
//输入时 taller = 0
//如果插入成功，则函数返回 1，否则 函数返回 0
//若 tree 树中已存在值为 x 的结点或者内存分配失败，则插入操作失败
//如果插入后 tree 树的高度增加，则 taller 返回 1，否则 taller 返回 0
//要求成功插入后仍然是一棵 AVL树（因此可能需作平衡处理）
//成功插入后的新树的根指针仍为 tree
{ int success ;
if ( tree == NULL ) // tree 树为空树，则创建新结点并作为根结点即可
{ tree = new AVLNode( x ) ;
success = tree != NULL? 1, 0 ;
if ( success )//内存分配成功
{ taller = 1 ;//tree 树高度增加
tree -> balance = 0 ;// tree 树的平衡因子等于 0
}
}
2011-7-18 42
else if ( x < tree -> data ) // tree 树不空且 x 小于根结点的关键码
{ success = Insert( tree -> left,x,taller ) ;//递归插入左子树中
if ( success && taller )//插入成功并且左子树的高度增加了
switch ( tree -> balance )
{ case –1,// tree 树根结点的平衡因子原为－ 1，其左子树
//的高度增 1后，使得插入后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其左子树的
//高度增 1后，使得插入后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度增加了
tree -> balance = -1 ; break ;
case 1,// tree 树根结点的平衡因子原为 1，其左子树的
//高度增 1后，使得插入后的 tree 树根结点的平衡
//因子等于 0，因此对 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未增加
tree -> balance = 0 ; taller = 0 ; break ;
}
}
2011-7-18 43
else if ( x > tree -> data ) // tree 树不空且 x 大于根结点的关键码
{ success = Insert( tree -> right,x,taller ) ;//递归插入右子树中
if ( success && taller )//插入成功并且右子树的高度增加了
switch ( tree -> balance )
{ case 1,// tree 树根结点的平衡因子原为 1，其右子树
//的高度增 1后，使得插入后 tree 树根结点的平衡
//因子等于 2，因此对 tree 树需作右平衡处理
RightBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度增 1后，使得插入后的 tree 树根结点的平
//衡因子等于 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度增加了
tree -> balance = 1 ; break ;
case -1,// tree 树根的平衡因子原为 -1，其右子树的
//高度增 1后，使得插入后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未增加
tree -> balance = 0 ; taller = 0 ; break ;
}
}
2011-7-18 44
else success = 0 ; // x== tree -> data,即值为 x 的结点已存在，
//无需插入操作，认为插入操作失败
return success ;
}
2011-7-18 45
7.6.4 AVL树的删除操作算法
template <class Type> int AVLTree<Type>,:
Remove( AVLNode * & tree,Type x,int & taller )
//在以 tree 为根指针的 AVL树中删除值为 x 的新结点
//输入时 taller = 0
//如果删除成功，则函数返回 1，否则 函数返回 0
//若 tree 树中不存在值为 x 的结点，则删除操作失败
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求成功删除后仍然是一棵 AVL树（因此可能需作平衡处理）
//成功删除后的新树的根指针仍为 tree
{ int success ;
if ( tree == NULL ) success = 0 ;
// tree 树为空树，则删除失败（树中不存在所找结点）
else if ( x == tree -> data ) success = RootRemove( tree,taller ) ;
//所找结点即为根结点，则删除根结点。删除后的新树的根指针仍为 tree
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求成功删除后仍然是一棵 AVL树（因此可能需作平衡处理）
2011-7-18 46
else if ( x < tree -> data ) // tree 树不空且 x 小于根结点的关键码
{ success = Remove( tree -> left,x,taller ) ;//递归删除左子树中的 x
if ( success && taller )//删除成功并且左子树的高度降低了
switch ( tree -> balance )
{ case 1,// tree 树根结点的平衡因子原为 1，其左子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于 2，因此对 tree 树需作右平衡处理
RightBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其左子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = 1 ; taller = 0 ; break ;
case -1,// tree 树根的平衡因子原为－ 1，其左子树的
//高度减 1后，使得删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller = 1 ; break ;
}
}
2011-7-18 47
else if ( x > tree -> data ) // tree 树不空且 x 大于根结点的关键码
{ success = Remove( tree -> right,x,taller );//递归删除右子树中的 x
if ( success && taller )//删除成功并且右子树的高度降低了
switch ( tree -> balance )
{ case -1,// tree 树根结点的平衡因子原为－ 1，其右子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = -1 ; taller = 0 ; break ;
case 1,// tree 树根的平衡因子原为 1，其右子树的
//高度减 1后，使删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller =1 ; break ;
}
}
return success ; }
2011-7-18 48
7.6.5 AVL树根结点的删除操作算法
template <class Type> int AVLTree<Type>,:
RootRemove( AVLNode * & tree,int & taller )
//删除以 tree 为根指针的 AVL树的根结点
//输入时 taller = 0
//如果删除后 tree 树的高度降低，则 taller 返回 1，否则 taller 返回 0
//要求删除后仍然是一棵 AVL树（因此可能需作平衡处理）
//删除后的新树的根指针仍为 tree
{ int success,bal ;
AVLNode * temp ;
if ( tree -> left != NULL && tree -> right !=NULL)
//若根的左右子树均不空
{ temp = Min( tree -> right ) ; //则从右子树中查找最小结点
bal = tree -> balance ;
tree -> data = temp -> data ;//并用该结点数据代替根结点的数据
tree -> balance = bal ;
success = Remove(tree -> right,tree -> data,taller ) ;
//最后将该结点删除，间接递归调用 Remove,删除后的右子树仍是一
//棵 AVL树，并由 taller 返回删除过程是否改变了右子树的高度
2011-7-18 49
if ( success && taller )//删除成功并且右子树的高度降低了
switch ( tree -> balance )
{ case -1,// tree 树根结点的平衡因子原为－ 1，其右子树
//的高度减 1后，使得删除后 tree 树根结点的平衡
//因子等于－ 2，因此对 tree 树需作左平衡处理
LeftBalance( tree,taller ) ; break ;
case 0,// tree 树根结点的平衡因子原为 0，其右子树的
//高度减 1后，使得删除后的 tree 树根结点的平
//衡因子等于－ 1，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，并且 tree 树的高度未降低
tree -> balance = -1 ; taller = 0 ; break ;
case 1,// tree 树根的平衡因子原为 1，其右子树的
//高度减 1后，使删除后的 tree 树根结点的平衡
//因子等于 0，因此 tree 树仍是一棵 AVL树，
//无需作平衡处理，但 tree 树的高度降低了
tree -> balance = 0 ; taller =1 ; break ;
}
}
2011-7-18 50
else//否则根结点的左右子树不全
{temp = tree ;
if ( tree -> left == NULL && tree -> right == NULL )//根结点为叶结点
{ tree = NULL ; taller = 1 ; }//删除后成为空树，高度降低
else if ( tree -> left == NULL ) //若无左子树，则右子树不空并且只有
//一个结点，因 tree 树是一棵 AVL树
{ tree = tree -> right ;//直接将右结点作为根结点
tree -> balance = 0 ;//新根结点无左右子树，因此平衡因子等于 0
taller = 1 ;//删除操作降低了 tree 树的高度
}
else //右子树空，左子树不空情况。此时左子树只有一个结点，
//因 tree 树是一棵 AVL树
{ tree = tree -> left ; //直接将左结点作为根结点
tree -> balance = 0 ; //新根结点无左右子树，因此平衡因子等于 0
taller = 1 ; //删除操作降低了 tree 树的高度
}
delete temp ;//释放被删除的根结点
}
return 1 ;// x 结点存在，删除肯定成功
}
2011-7-18 51
2011-7-18 52
2011-7-18 53
2011-7-18 54
2011-7-18 55
2011-7-18 56
2011-7-18 57
2011-7-18 58
2011-7-18 59
2011-7-18 60
2011-7-18 61
2011-7-18 62
2011-7-18 63
2011-7-18 64
方格模板
2011-7-18 65
2011-7-18 66
2011-7-18 67
2011-7-18 68
2011-7-18 69
2011-7-18 70
2011-7-18 71
2011-7-18 72
2011-7-18 73
2011-7-18 74
2011-7-18 75
2011-7-18 76
2011-7-18 77
2011-7-18 78
2011-7-18 79
2011-7-18 80
2011-7-18 81
2011-7-18 82
2011-7-18 83
2011-7-18 84
2011-7-18 85
2011-7-18 86
2011-7-18 87
2011-7-18 88
2011-7-18 89
2011-7-18 90
