2009-7-25 1
第 6章 树和森林非线性数据结构实际中有许多树型结构的问题，用树型数据结构来解决非常自然树型结构在计算机领域的应用非常广泛
6.1 树和森林的概念树的定义：
树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树，
否则：
（ 1）有一个特定的称之为根 ( root )的结点，它只有直接后继，
但没有直接前驱；
（ 2）除根以外的其他结点可划分为若干个互不相交的有限集合，
每个集合又是一棵树，并且称之为根的子树 ( subTree )。每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。
2009-7-25 2
树的示意图：
根结点根结点叶结点分支结点子树子树子树
Level 0
Level 1
Level 2
Level 3
结点的层次
2009-7-25 3
树的基本术语结点的度 ( degree )：结点所拥有的子树数目子女 ( child ) 结点：简称子结点双亲 ( parent) 结点：简称父结点 ( father )
兄弟 ( sibling)结点：具有同一个父结点的结点根 ( root ) 结点：
分支 ( branch )结点：又称非终端结点叶 ( leaf ) 结点：又称终端结点结点的层次 ( level ):根结点的层次为 0，子结点的层次等于其父结点的层次加一树的高度 ( depth ):等于树中最大的结点层次数。空树的高度为－ 1
树的度 ( degree ):等于树中最大的结点度数有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，
否则就成为另一棵树了。
无序树：树中结点的各子树之间的先后次序无意义，可以互换森林 ( forest ):若干棵树的集合
2009-7-25 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
2009-7-25 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 数组表示）
顺序存储结构用于动态性较小的完全二叉树的存储不失为一种简单有效的方法，但不通用。树型数据结构一般采用链式存储方式来存储。
2009-7-25 6
6.3.2 二叉树的链式存储结构 —— 二叉（三叉）链表结构二叉链表结构：
左子指针 数据元素 右子指针三叉链表结构：
左子指针 数据元素 右子指针父指针
leftChild data rightChild
leftChild data father rightChild
2009-7-25 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;//数据元素
}
2009-7-25 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 结点的右子结点指针
2009-7-25 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 树的所有结点
}
2009-7-25 10
二叉树的基本操作
（ 1）初始化操作 ——一般由构造函数实现
（ 2）建立一棵二叉树
（ 3）撤销一棵二叉树 ——可以由析构函数实现
（ 4）插入一个新结点
（ 5）删除一个结点
（ 6）查找
（ 7）判树空
（ 8）读取结点数据
（ 9）修改结点数据
（ 10）求二叉树的某一或某些性能（如结点数、高度、平衡度等）
（ 11）求根结点、父结点、左子结点、右子结点等结点的指针
（ 12）调整一棵二叉树，优化某一或某些性能
（ 13）二叉树遍历操作
（ 14）其他操作
2009-7-25 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）其他
2009-7-25 12
6.4 二叉树遍历 (Binary Tree Traversal ) 操作遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的访问可以是输出、修改等操作，根据实际需要而定。
遍历操作可以从一种非线性结构中得到相应的线性序列。
有不同顺序的遍历操作，对于二叉树有三种遍历操作：
先序遍历（ NLR） 中序遍历（ LNR） 后序遍历（ LRN）
访问根结点 中序遍历左子树 后序遍历左子树先序遍历左子树 访问根结点 后序遍历右子树先序遍历右子树 中序遍历右子树 访问根结点可以看出，上述三种顺序的二叉树遍历操作都是递归定义的，
因此用递归算法实现很容易。
2009-7-25 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 ); //先序遍历右子树
}
}
2009-7-25 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 。
2009-7-25 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 ;
}
2009-7-25 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 ;
}
2009-7-25 17
7.4 二叉搜索树 (Binary Search Tree ) P235
定义：一棵二叉树称之为二叉搜索树，如果它满足以下条件：
它或者是空树；
或者左子树中结点的关键码均小于根结点的关键码，
并且右子树中结点的关键码均大于根结点的关键码,
并且左子树和右子树均为二叉搜索树。
显然，二叉搜索树的中序遍历的输出序列是一严格递增的有序序列二叉搜索数的类定义：
2009-7-25 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 ;
}
2009-7-25 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 );
2009-7-25 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> ;
}
2009-7-25 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 ) ;
//关键码大于根结点的关键码，递归搜索右子数
}
2009-7-25 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
}
}
2009-7-25 23
在上述算法中有一个指针的引用 fp,
BstNode<Type> * & fp ;
通过指针的引用可以从函数中返回一个被函数改变了的指针。
假定对上述算法作如下调用：
Template <class Type> int BST<Type>,,Find( const Type & x ) const
//
{ return Find( key,root,fatherptr ) == NULL ; }
2009-7-25 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 等于根结点的关键码，则不作插入操作
}
2009-7-25 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 ;
}
}
通过本算法创建的二叉搜索树可能会很不平衡，极端情况下将退化成为一单链表，从而失去了二叉搜索树高搜索效率的优点，因此需作调整。
2009-7-25 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 ) ;//最后将该结点删除
}
2009-7-25 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 为根指针的二叉搜索树中查找关键码最小的结点，并返
//回该结点的指针
{
//原理：从根结点开始沿着左链往下查找，第一个左子树为空的结点就是
//树中的关键码最小的结点
}
课堂作业：完成上述算法
2009-7-25 28
7.6 AVL树 —— 高度平衡的二叉搜索树前述的二叉搜索树的插入和建立（通过插入实现）算法不考虑树的平衡问题，因此有可能产生高度不平衡的二叉搜索树，极端情况下将退化成一个单链表，失去了二叉搜索树的优点。因此在二叉搜索树的插入过程中必须调整树的结构，使之平衡化。
AVL树的定义：
一棵 AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树的高度之差的绝对值不超过 1 。
结点的平衡因子 ( balance factor ),
balance ＝ 该结点的右子树高度 － 该结点的左子树高度对于 AVL树,| balance | <= 1
即 balance 只能取 － 1,0,1 三者之一平衡化方法 ——平衡化旋转方法：
单旋转：左单旋转（左旋） RotateLeft
右单旋转（右旋） RotateRight
双旋转：先左后右双旋转（左平衡 LeftBalance ）
先右后左双旋转（右平衡 RightBalance ）
2009-7-25 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 ) { }
} ;
2009-7-25 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 ;
}
2009-7-25 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）
2009-7-25 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
左单旋转处理右单旋转处理
2009-7-25 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的左子树
}
2009-7-25 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树作右单旋转处理）
2009-7-25 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树是平
//衡的），因此这种情况不可能发生，因此不用理会它
2009-7-25 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 ;
}
2009-7-25 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 ;//平衡处理完后，新树的高度与原树一样
}
}
2009-7-25 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树左单旋转
2009-7-25 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 ; //在每插入一个结点后都进行平衡处理的话，
//此情况不可能发生
2009-7-25 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 ;}}
2009-7-25 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
}
}
2009-7-25 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 ;
}
}
2009-7-25 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 ;
}
}
2009-7-25 44
else success = 0 ; // x== tree -> data,即值为 x 的结点已存在，
//无需插入操作，认为插入操作失败
return success ;
}
2009-7-25 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树（因此可能需作平衡处理）
2009-7-25 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 ;
}
}
2009-7-25 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 ; }
2009-7-25 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 返回删除过程是否改变了右子树的高度
2009-7-25 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 ;
}
}
2009-7-25 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 结点存在，删除肯定成功
}
2009-7-25 51
2009-7-25 52
2009-7-25 53
2009-7-25 54
2009-7-25 55
2009-7-25 56
2009-7-25 57
2009-7-25 58
2009-7-25 59
2009-7-25 60
2009-7-25 61
2009-7-25 62
2009-7-25 63
2009-7-25 64
方格模板
2009-7-25 65
2009-7-25 66
2009-7-25 67
2009-7-25 68
2009-7-25 69
2009-7-25 70
2009-7-25 71
2009-7-25 72
2009-7-25 73
2009-7-25 74
2009-7-25 75
2009-7-25 76
2009-7-25 77
2009-7-25 78
2009-7-25 79
2009-7-25 80
2009-7-25 81
2009-7-25 82
2009-7-25 83
2009-7-25 84
2009-7-25 85
2009-7-25 86
2009-7-25 87
2009-7-25 88
2009-7-25 89
2009-7-25 90
第 6章 树和森林非线性数据结构实际中有许多树型结构的问题，用树型数据结构来解决非常自然树型结构在计算机领域的应用非常广泛
6.1 树和森林的概念树的定义：
树是由 n ( n>=0 ) 个结点组成的有限集合。若 n = 0 则称为空树，
否则：
（ 1）有一个特定的称之为根 ( root )的结点，它只有直接后继，
但没有直接前驱；
（ 2）除根以外的其他结点可划分为若干个互不相交的有限集合，
每个集合又是一棵树，并且称之为根的子树 ( subTree )。每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。
2009-7-25 2
树的示意图：
根结点根结点叶结点分支结点子树子树子树
Level 0
Level 1
Level 2
Level 3
结点的层次
2009-7-25 3
树的基本术语结点的度 ( degree )：结点所拥有的子树数目子女 ( child ) 结点：简称子结点双亲 ( parent) 结点：简称父结点 ( father )
兄弟 ( sibling)结点：具有同一个父结点的结点根 ( root ) 结点：
分支 ( branch )结点：又称非终端结点叶 ( leaf ) 结点：又称终端结点结点的层次 ( level ):根结点的层次为 0，子结点的层次等于其父结点的层次加一树的高度 ( depth ):等于树中最大的结点层次数。空树的高度为－ 1
树的度 ( degree ):等于树中最大的结点度数有序树：树中结点的各子树之间的先后次序是有意义的，不能互换，
否则就成为另一棵树了。
无序树：树中结点的各子树之间的先后次序无意义，可以互换森林 ( forest ):若干棵树的集合
2009-7-25 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
2009-7-25 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 数组表示）
顺序存储结构用于动态性较小的完全二叉树的存储不失为一种简单有效的方法，但不通用。树型数据结构一般采用链式存储方式来存储。
2009-7-25 6
6.3.2 二叉树的链式存储结构 —— 二叉（三叉）链表结构二叉链表结构：
左子指针 数据元素 右子指针三叉链表结构：
左子指针 数据元素 右子指针父指针
leftChild data rightChild
leftChild data father rightChild
2009-7-25 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;//数据元素
}
2009-7-25 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 结点的右子结点指针
2009-7-25 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 树的所有结点
}
2009-7-25 10
二叉树的基本操作
（ 1）初始化操作 ——一般由构造函数实现
（ 2）建立一棵二叉树
（ 3）撤销一棵二叉树 ——可以由析构函数实现
（ 4）插入一个新结点
（ 5）删除一个结点
（ 6）查找
（ 7）判树空
（ 8）读取结点数据
（ 9）修改结点数据
（ 10）求二叉树的某一或某些性能（如结点数、高度、平衡度等）
（ 11）求根结点、父结点、左子结点、右子结点等结点的指针
（ 12）调整一棵二叉树，优化某一或某些性能
（ 13）二叉树遍历操作
（ 14）其他操作
2009-7-25 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）其他
2009-7-25 12
6.4 二叉树遍历 (Binary Tree Traversal ) 操作遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的访问可以是输出、修改等操作，根据实际需要而定。
遍历操作可以从一种非线性结构中得到相应的线性序列。
有不同顺序的遍历操作，对于二叉树有三种遍历操作：
先序遍历（ NLR） 中序遍历（ LNR） 后序遍历（ LRN）
访问根结点 中序遍历左子树 后序遍历左子树先序遍历左子树 访问根结点 后序遍历右子树先序遍历右子树 中序遍历右子树 访问根结点可以看出，上述三种顺序的二叉树遍历操作都是递归定义的，
因此用递归算法实现很容易。
2009-7-25 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 ); //先序遍历右子树
}
}
2009-7-25 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 。
2009-7-25 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 ;
}
2009-7-25 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 ;
}
2009-7-25 17
7.4 二叉搜索树 (Binary Search Tree ) P235
定义：一棵二叉树称之为二叉搜索树，如果它满足以下条件：
它或者是空树；
或者左子树中结点的关键码均小于根结点的关键码，
并且右子树中结点的关键码均大于根结点的关键码,
并且左子树和右子树均为二叉搜索树。
显然，二叉搜索树的中序遍历的输出序列是一严格递增的有序序列二叉搜索数的类定义：
2009-7-25 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 ;
}
2009-7-25 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 );
2009-7-25 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> ;
}
2009-7-25 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 ) ;
//关键码大于根结点的关键码，递归搜索右子数
}
2009-7-25 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
}
}
2009-7-25 23
在上述算法中有一个指针的引用 fp,
BstNode<Type> * & fp ;
通过指针的引用可以从函数中返回一个被函数改变了的指针。
假定对上述算法作如下调用：
Template <class Type> int BST<Type>,,Find( const Type & x ) const
//
{ return Find( key,root,fatherptr ) == NULL ; }
2009-7-25 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 等于根结点的关键码，则不作插入操作
}
2009-7-25 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 ;
}
}
通过本算法创建的二叉搜索树可能会很不平衡，极端情况下将退化成为一单链表，从而失去了二叉搜索树高搜索效率的优点，因此需作调整。
2009-7-25 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 ) ;//最后将该结点删除
}
2009-7-25 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 为根指针的二叉搜索树中查找关键码最小的结点，并返
//回该结点的指针
{
//原理：从根结点开始沿着左链往下查找，第一个左子树为空的结点就是
//树中的关键码最小的结点
}
课堂作业：完成上述算法
2009-7-25 28
7.6 AVL树 —— 高度平衡的二叉搜索树前述的二叉搜索树的插入和建立（通过插入实现）算法不考虑树的平衡问题，因此有可能产生高度不平衡的二叉搜索树，极端情况下将退化成一个单链表，失去了二叉搜索树的优点。因此在二叉搜索树的插入过程中必须调整树的结构，使之平衡化。
AVL树的定义：
一棵 AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树的高度之差的绝对值不超过 1 。
结点的平衡因子 ( balance factor ),
balance ＝ 该结点的右子树高度 － 该结点的左子树高度对于 AVL树,| balance | <= 1
即 balance 只能取 － 1,0,1 三者之一平衡化方法 ——平衡化旋转方法：
单旋转：左单旋转（左旋） RotateLeft
右单旋转（右旋） RotateRight
双旋转：先左后右双旋转（左平衡 LeftBalance ）
先右后左双旋转（右平衡 RightBalance ）
2009-7-25 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 ) { }
} ;
2009-7-25 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 ;
}
2009-7-25 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）
2009-7-25 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
左单旋转处理右单旋转处理
2009-7-25 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的左子树
}
2009-7-25 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树作右单旋转处理）
2009-7-25 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树是平
//衡的），因此这种情况不可能发生，因此不用理会它
2009-7-25 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 ;
}
2009-7-25 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 ;//平衡处理完后，新树的高度与原树一样
}
}
2009-7-25 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树左单旋转
2009-7-25 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 ; //在每插入一个结点后都进行平衡处理的话，
//此情况不可能发生
2009-7-25 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 ;}}
2009-7-25 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
}
}
2009-7-25 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 ;
}
}
2009-7-25 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 ;
}
}
2009-7-25 44
else success = 0 ; // x== tree -> data,即值为 x 的结点已存在，
//无需插入操作，认为插入操作失败
return success ;
}
2009-7-25 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树（因此可能需作平衡处理）
2009-7-25 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 ;
}
}
2009-7-25 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 ; }
2009-7-25 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 返回删除过程是否改变了右子树的高度
2009-7-25 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 ;
}
}
2009-7-25 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 结点存在，删除肯定成功
}
2009-7-25 51
2009-7-25 52
2009-7-25 53
2009-7-25 54
2009-7-25 55
2009-7-25 56
2009-7-25 57
2009-7-25 58
2009-7-25 59
2009-7-25 60
2009-7-25 61
2009-7-25 62
2009-7-25 63
2009-7-25 64
方格模板
2009-7-25 65
2009-7-25 66
2009-7-25 67
2009-7-25 68
2009-7-25 69
2009-7-25 70
2009-7-25 71
2009-7-25 72
2009-7-25 73
2009-7-25 74
2009-7-25 75
2009-7-25 76
2009-7-25 77
2009-7-25 78
2009-7-25 79
2009-7-25 80
2009-7-25 81
2009-7-25 82
2009-7-25 83
2009-7-25 84
2009-7-25 85
2009-7-25 86
2009-7-25 87
2009-7-25 88
2009-7-25 89
2009-7-25 90
