用C++来实现AVL树的程序,要求建立,插入,删除,单旋,双旋,前序和后序遍历

7.6 AVL树

创新互联专注于高州企业网站建设,成都响应式网站建设,电子商务商城网站建设。高州网站建设公司,为高州等地区提供建站服务。全流程按需定制设计，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务

7.6.1 AVL树的定义

高度平衡的二叉搜索树

一棵AVL树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。

高度不平衡的二叉搜索树 高度平衡的二叉搜索树

结点的平衡因子balance (balance factor)

1、每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子balance 。

2、根据AVL树的定义，任一结点的平衡因子只能取 -1，0和 1。

3、如果一个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树。

4、如果一棵二叉搜索树是高度平衡的，它就成为 AVL树。如果它有n个结点，其高度可保持在O(log2n)，平均搜索长度也可保持在O(log2n)。

AVL树的类定义

template class Type class AVLTree {

public:

struct AVLNode {

Type data;

AVLNode *left, *right;

int balance;

AVLNode ( ) : left (NULL), right (NULL), balance (0) { }

AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL )

: data (d), left (l), right (r), balance (0) { }

};

protected:

Type RefValue;

AVLNode *root;

int Insert ( AVLNode* tree, Type x, int taller );

void RotateLeft ( AVLNode *Tree, AVLNode* NewTree );

void RotateRight ( AVLNode *Tree, AVLNode* NewTree );

void LeftBalance ( AVLNode* Tree, int taller );

void RightBalance(AVLNode* Tree, int taller);

int Depth ( AVLNode *t ) const;

public:

AVLTree ( ) : root (NULL) { }

AVLNode ( Type Ref ) : RefValue (Ref), root (NULL) { }

int Insert ( Type x ) {

int taller;

return Insert ( root, x, taller );

}

friend istream operator ( istream in, AVLTreetype Tree );

friend ostream operator ( ostream out, const AVLTreetype Tree );

int Depth ( ) const;

}

7.6.2 平衡化旋转

1、如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。

此时必须调整树的结构，使之平衡化。

2、平衡化旋转有两类：

单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡)

3、每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的高度差)。

4、如果在某一结点发现高度不平衡，停止回溯。

5、从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。

6、 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。

7、如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。

右单旋转

左单旋转

左右双旋转

右左双旋转

1、左单旋转 (RotateLeft )

(1)如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成+2，出现不平衡。

(2)沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。

(3)以结点C为旋转轴，让结点A反时针旋转。

左单旋转的算法

template class Type void AVLTreetype:: RotateLeft ( AVLNode *Tree, AVLNode* NewTree ) {

NewTree = Tree→right;

Tree→right = NewTree→left;

NewTree→left = Tree;

}

2、右单旋转 (RotateRight )

(1)在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 -2，造成了不平衡。

(2) 为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。

(3) 以结点B为旋转轴，将结点A顺时针旋转。

右单旋转的算法

template class Type void AVLTreetype:: RotateRight( AVLNode *Tree, AVLNode* NewTree) {

NewTree = Tree→left;

Tree→left = NewTree→right;

NewTree→right = Tree;

}

3、先左后右双旋转 (RotationLeftRight)

(1)在子树F或G中插入新结点，该子树的高度增1。结点A的平衡因子变为 -2，发生了不平衡。

(2) 从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“?”的折线上，因此需要进行先左后右的双旋转。

(3)首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转。

(4) 再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转。使之平衡化。

左平衡化的算法

template class Type void AVLTreetype:: LeftBalance ( AVLNode * Tree, int taller ) {

AVLNode *leftsub = Tree→left, *rightsub;

switch ( leftsub→balance ) {

case -1 :

Tree→balance = leftsub→balance = 0;

RotateRight ( Tree, Tree );

taller = 0;

break;

case 0 :

cout “树已经平衡化.\n";

break;

case 1 :

rightsub = leftsub→right;

switch ( rightsub→balance ) {

case -1:

Tree→balance = 1;

leftsub→balance = 0;

break;

case 0 :

Tree→balance = leftsub→balance = 0;

break;

case 1 :

Tree→balance = 0;

leftsub→balance = -1;

break;

}

rightsub→balance = 0;

RotateLeft ( leftsub, Tree→left );

RotateRight ( Tree, Tree );

taller = 0;

}

}

4、先右后左双旋转 (RotationRightLeft)

(1)右左双旋转是左右双旋转的镜像。

(2) 在子树F或G中插入新结点，该子树高度增1。结点A的平衡因子变为2，发生了不平衡。

(3) 从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“?”的折线上，需要进行先右后左的双旋转。

(4)首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。

(5) 再做左单旋转：以结点D为旋转轴，将结点A反时针旋转，恢复树的平衡。

右平衡化的算法

template class Type void AVLTreetype:: RightBalance ( AVLNode * Tree, int taller ) {

AVLNode *rightsub = Tree→right, *leftsub;

switch ( rightsub→balance ) {

case 1 :

Tree→balance = rightsub→balance = 0;

RotateLeft ( Tree, Tree );

taller = 0;

break;

case 0 :

cout “树已经平衡化.\n";

break;

case -1 :

leftsub = rightsub→left;

switch ( leftsub→balance ) {

case 1 :

Tree→balance = -1;

rightsub→balance = 0;

break;

case 0 :

Tree→balance = rightsub→balance = 0;

break;

case -1 :

Tree→balance = 0;

rightsub→balance = 1;

break;

}

leftsub→balance = 0;

RotateRight ( rightsub, Tree→left );

RotateLeft ( Tree, Tree );

taller = 0;

}

}

7.6.3 AVL树的插入和删除

AVL树的插入:

1、在向一棵本来是高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| 1，则出现了不平衡，需要做平衡化处理。

2、在AVL树上定义了重载操作“”和“”，以及中序遍历的算法。利用这些操作可以执行AVL树的建立和结点数据的输出。

3、 算法从一棵空树开始，通过输入一系列对象的关键码，逐步建立AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。

例，输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和调整过程如下。

从空树开始的建树过程

1、下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。

2、 在发现不平衡时立即执行相应的平衡化旋转操作，使得树中各结点重新平衡化。

3、 在程序中，用变量success记载新结点是否存储分配成功，并用它作为函数的返回值。

4、算法从树的根结点开始，递归向下找插入位置。在找到插入位置(空指针)后，为新结点动态分配存储空间，将它作为叶结点插入，并置success为1，再将taller置为1，以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。

template class Type int AVLTreetype:: Insert ( AVLNode* tree, Type x, int taller ) {

int success;

if ( tree == NULL ) {

tree = new AVLNode (x);

success = tree != NULL ? 1 : 0;

if ( success ) taller = 1;

}

else if ( x tree→data ) {

success = Insert ( tree→left, x, taller );

if ( taller )

switch ( tree→balance ) {

case -1 :

LeftBalance ( tree, taller );

break;

case 0 :

tree→balance = -1;

break;

case 1 :

tree→balance = 0;

taller = 0;

break;

}

}

else {

success = Insert ( tree→right, x, taller );

if ( taller )

switch ( tree→balance ) {

case -1 :

tree→balance = 0;

taller = 0;

break;

case 0 :

tree→balance = 1;

break;

case 1 :

RightBalance ( tree, taller );

break;

}

}

return success;

}

AVL树的重载操作 、 和遍历算法的实现 :

template class Type istream operator ( istream in, AVLTreetype Tree ) {

Type item;

cout “构造AVL树 :\n";

cout “输入数据(以" Tree.RefValue “结束): ";

in item;

while ( item != Tree.RefValue ) {

Tree.Insert (item);

cout “输入数据(以" Tree.RefValue “结束): ";

in item;

}

return in;

}

template class Type void AVLTree type

:: Traverse ( AVLNode *ptr, ostream out ) const { //AVL树中序遍历并输出数据

if ( ptr != NULL ) {

Traverse ( ptr→left, out );

out ptr→data ' ';

Traverse ( ptr→right, out );

}

}

template class Type ostream operator ( ostream out, const AVLTreetype Tree ) {

out “AVL树的中序遍历.\n";

Tree.Traverse ( Tree.root, out );

out endl;

return out;

}

AVL树的删除

1、如果被删结点x最多只有一个子女，那么问题比较简单。如果被删结点x有两个子女，首先搜索 x 在中序次序下的直接前驱 y (同样可以找直接后继)。再把 结点y 的内容传送给结点x，现在问题转移到删除结点 y。 把结点y当作被删结点x。

2、 将结点x从树中删去。因为结点x最多有一个子女，我们可以简单地把x的双亲结点中原来指向x的指针改指到这个子女结点；如果结点x没有子女，x双亲结点的相应指针置为NULL。然后将原来以结点x为根的子树的高度减1，

3、必须沿x通向根的路径反向追踪高度的变化对路 径上各个结点的影响。

4、 用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance，有时还要依赖子女的 balance 。

5、 布尔变量 shorter 的值初始化为True。然后对于从 x 的双亲到根的路径上的各个结点 p，在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成False，算法终止。

6、case 1 : 当前结点p的balance为0。如果它的左子树或右子树被缩短，则它的 balance改为1或-1，同时 shorter 置为False。

7、case 2 : 结点p的balance不为0，且较高的子树被缩短，则p的balance改为0，同时 shorter 置为True。

8、case 3 : 结点p的balance不为0，且较矮的子树又被缩短，则在结点p发生不平衡。需要进行平衡化旋转来恢复平衡。令p的较高的子树的根为 q (该子树未被缩短)，根据q的balance ，有如下3种平衡化操作。

9、case 3a : 如果q的balance为0，执行一个单旋转来恢复结点p的平衡，置shorter为False。

10、 case 3b : 如果q的balance与p的balance相同，则执行一个单旋转来恢复平衡，结点p和q的balance均改为0，同时置shorter为True。

11、case 3c : 如果p与q的balance相反，则执行一个双旋转来恢复平衡，先围绕 q 转再围绕 p 转。新的根结点的balance置为0，其它结点的balance相应处理，同时置shorter为True。

12、 在case 3a, 3b和3c的情形中，旋转的方向取决于是结点p的哪一棵子树被缩短。

7.6.4 AVL树的高度

1、设在新结点插入前AVL树的高度为h，结点个数为n，则插入一个新结点的时间是O(h)。对于AVL树来说，h多大？

2、设 Nh 是高度为 h 的AVL树的最小结点数。根的一棵子树的高度为 h-1，另一棵子树的高度为 h-2，这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h 0

3、可以证明，对于 h ? 0，有 Nh = Fh+3 -1 成立。

4、有n个结点的AVL树的高度不超过

5、在AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。

6、 二叉搜索树适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统，用二叉搜索树来组织索引不太合适。

7、 在文件检索系统中大量使用的是用B_树或B+树做文件索引。

设计非递归算法，利用平衡因子求二叉平衡树的高度

看这个图从根节点开始如果平衡因子大于1就选左节点，小于1就选右节点，等于0终止。使用while循环就可以了，循环结束时的循环次数就是树的高度。

int loop=0;

当前节点=根节点

while(true)

{

loop++;

if(当前节点的平衡因子0)

{当前节点=左子树}

else if(当前节点的平衡因子0)

{当前节点=右子树}

else

{退出循环}

}

loop就是树高度

C++或Basic编程

1）数据数据的概念十分广泛，它通常是对客观事物的数量、特征、性质的描述。对计算机而言，数据是计算机所能处理的一切数值、字符、图形或其他特定符号的总称，是计算机加工处理的“原料”和它所生产的“产品”(计算的结果)。2）数据元素数据元素是数据的基本单位，也称作结点和记录。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。3）数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。 1、 数据结构（Data Structure）

数据结构是指同一数据对象中个数据元素之间存在的关系（相互间存在一种或多种特定关系的数据元素的集合）。

根据数据结构的形式定义，数据结构是一个二元组：

S（Data-Structure）=(D，R)

其中：D是数据元素的有限集，R是D上关系的有限集。

逻辑结构与物理结构

数据之间的相互关系称为逻辑结构。通常分为三类基本结构：

（一）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。

（二）线性结构：结构中的数据元素之间存在一对一的关系。

（三）非线性结构：

树型结构——结构中的数据元素之间存在一对多的关系。

图状结构或网状结构——结构中的数据元素之间存在多对多的关系。

数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。

（一般我们将数据的逻辑结构称为是数据结构，）

存储结构可分为：顺序存储与链式存储。

顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系；

链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系。

数据的逻辑结构与存储结构密切相关。

2.1.2 线性表

1）线性表定义

线性表(Linear List) ：由n(n≧)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：

L = (a1，a2，…an)

这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

2）线性表特点

线性表的逻辑结构有以下特点：

在数据元素的非空有限集中

Ø 存在唯一的一个被称作“第一个”的数据元素

Ø 存在唯一的一个被称作“最后一个”的数据元素

Ø 除第一个外，集合中的每个数据元素均只有一个前驱

Ø 除最后一个外，集合中的每个数据元素均只有一个后继

3）线性表的基本运算

线性表的主要运算有：

插入：在两个确定元素之间插入一个新元素；

删除：删除线性表中的某个元素；

查找：按某种要求查找线性表中的一个元素，需要时还可以进行更新；

排序：按给定要求对表中元素重新排序；

还有初始化、求长度等。

在不同问题的线性表中，需要进行的运算也不相同，实际应用中还可能涉及建立线性表、修改表中元素数值（编辑）等运算，但是基本上可以由上述四种运算组成。

4）顺序存储线性表

（1）顺序存储结构

把线性表的数据元素，按顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表，也称为向量式存储结构。

假设线性表的每个元素需占用个存储单元，且线性表在内存中的首地址为，则线性表中第个数据元素的存储地址为：

则线性表中第个数据元素的存储位置和第个数据元素的存储位置之间满足下列关系：

这种存储结构只要知道数据元素序号，就很容易找到第个数据元素。它的主要特点有：一、各数据元素存储地址上相邻；二、无论序号为何值，找到第个元素的时间相同。

这种存储结构在高级语言中可以用一维数组的形式实现。

（2）顺序存储结构的优缺点

优点

Ø 逻辑相邻，物理相邻；

Ø 可随机存取任一元素；

Ø 存储空间使用紧凑。

缺点

Ø 插入、删除操作需要移动大量的元素；

Ø 预先分配空间需按最大空间分配，利用不充分；

Ø 表容量难以扩充。

5）线性链表

特点：

Ø 用一组任意的存储单元存储线性表的数据元素；

Ø 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素；

Ø 每个数据元素，除存储本身信息外，还需存储其直接后继的信息。

数据元素由两部分组成：

Ø 数据域：存放元素本身信息；

Ø 指针域：指示直接后继的存储地址。

线性链表一般在第一个结点之前附加一个头结点：

2.1.3 栈与队

栈和队是两种特殊的线性表，它们的运算规则较一般线性表由更多的约束和限制，因此称作限定性数据结构。

1）栈的结构和运算

（1）栈的定义

栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。

假设栈，则称为栈底元素，为栈顶元素。栈中元素按的次序进栈，的顺序退栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO，last in first out）。

栈的存储结构也有顺序与链式两种，称为顺序栈与链栈。

（2）顺序栈

由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。

栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示栈顶位置。如果用m来表示栈的最大容量，则top=0表示栈空，此时出栈，则下溢（underflow）；top=m表示栈满，此时入栈，则上溢（overflow）。

（3）栈的应用

表达式求值

表达式求值步骤：首先在OS栈中放入表达式结束符“；”，

l 若为操作数，将其压入NS栈；

l 若为运算符，比较当前OS栈的栈顶元素：

ü 若当前运算符的优先数大于OS栈顶的运算符，则将当前运算符压入OS栈；

ü 若当前运算符的优先数不大于OS栈顶运算符，则从NS栈中弹出两个操作数x,y，再从OS中弹出一个运算符，，并将结果T送入NS栈。

ü 若当前运算符为“；”，且OS栈顶也为“；”，则表示表达式处理结束，此时，NS栈顶元素即为此表达式值。

过程嵌套和递归调用

过程嵌套调用如图所示：

当调用子过程时，必须把断点的信息及地址保存起来，当子过程执行完毕，返回时，取用这些信息，找到返回地址，从此断点继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出。

递归调用

函数直接或间接地调用自身叫递归调用，这主要时用递归工作栈来实现的。下面举一个简单的例子来说明递归调用。

例 一段递归调用的C语言程序如下：

void print(int w)

{

int I;

if (w!=0)

{

print (w-1);

for (I=1; I=w; ++I)

printf(“%3d,”,w);

printf(“/n”);

}

}

在这段程序中，递归调用的执行过程如图所示：

2） 队的结构和运算

（1）队的定义

队是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。

队尾(rear)——允许插入的一端

队头(front)——允许删除的一端

队的特点是：先进先出(FIFO)

（2）顺序队

存在问题：

设数组维数为M，则：

当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出

l当front¹-1,rear=M-1时，再有元素入队发生溢出——假溢出

解决方案：

l 队首固定，每次出队剩余元素向下移动——浪费时间

l 循环队列

Ø 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;

Ø 实现：利用“模”运算

入队： rear=(rear+1)%M; sq[rear]=x;

出队： front=(front+1)%M; x=sq[front];

Ø 队满、队空判定条件

front=rear

解决方案：

n 另外设一个标志以区别队空、队满

n 少用一个元素空间：

队空：front==rear

队满：(rear+1)%M==front

2.1.4 数组

1）数组的定义

（1）定义

数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。用线性表的一般表示形式定义二维数组为：

其中，K由个结点组成：

R由以下两种关系组成：

（2）数组特点

l 数组结构固定

l 数据元素同构

（3）数组运算

数组一旦被定义，它的维数和数据元素的个数就已经固定，不能插入和删除，所以数组运算只有：

l 给定一组下标，存取相应的数据元素

l 给定一组下标，修改数据元素的值

2）数组的顺序存储结构

由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。

又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

根据不同的存放形式，可以分为按行优先和按列优先顺序存放。

（1）按行优先顺序存放

按行优先顺序存放，对二维数组来说就是按行进行切分，如图所示：

假设每个数据元素只占一个单元地址，则元素的存放地址可以通过以下关系式计算：

（2）按列优先顺序存放

如果数组按列切分，就得到按列优先顺序存放方式。如图所示：

元素的存放地址可以通过以下关系式计算：

2.1.5 树与二叉树

1）树的定义及其存储结构

（1）树的定义和术语

定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

(1)有且仅有一个特定的称为根(Root)的结点；

(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。

基本术语:

l 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支；

l 结点的度(degree)——结点拥有的子树数；

l 叶子(leaf)——度为0的结点；

l 孩子(child)——结点子树的根称为该结点的孩子；

l 双亲(parents)——孩子结点的上层结点叫该结点的双亲；

l 兄弟(sibling)——同一双亲的孩子；

l 树的度——一棵树中最大的结点度数；

l 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……；

l 深度(depth)——树中结点的最大层次数；

l 森林(forest)——m(m=0)棵互不相交的树的集合；

（2）树的存储结构

树的存储结构有多种形式，这里只讨论链式存储结构。因为树是多分支非线性表，因此采用多重链表结构，即每个结点设有多个指针域，其中每个指针指向一棵子树的根结点。对于每一个结点的结构类型有两种形式：结点异构型、结点同构型。

结点异构型，是根据每个结点的子树数设置相应的指针域，由于每个结点的度数不同，则同一棵树中，结点形式也不同。这种结构形式虽然能节省存储空间，但运算不方便。

结点同构型，是每个结点的指针域个数均为树的度数。这种形式运算方便，但会使链表中出现很多空链域，浪费空间。

当树的度数k=2时，空链域的比例最低，这就是要介绍的二叉树。

2）二叉树及其性质

二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

（1）二叉树定义及其存储结构

定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。

二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。

图2-8 二叉树

存储结构：通常用具有两个指针域的链表作为二叉树的存储结构，其中，每个结点由数据域（data）、左指针域（L child）和右指针域（R child）组成，如图所示：

图2-9 二叉链表

这就是二叉链表，还有三叉链表就是在这一基础上增加一个双亲结点指针。

（2）二叉树的基本性质

（1） 在二叉树的第层上，至多有个结点。

（2） 深度为h的二叉树中，至多含有个结点。

（3） 对任意一棵二叉树，若有个子结点，个度为2的结点，则必有。

（3）几种特殊形式的二叉树

l 满二叉树

一棵深度为h且有2h-1个结点的二叉树称为满二叉树。

l 完全二叉树

如果深度为h、有n个结点的二叉树中的结点能够与深度为h的顺序编号的满二叉树从1到n标号的结点相对应，则该树称为完全二叉树。

完全二叉树的特点是：

所有的叶结点都出现在第h层或h－1层。

错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。

满二叉树是完全二叉树的特例。

（1） 平衡二叉树

所有结点的平衡因子为-1、0、1。

（4）一般树转换为二叉树

为了使一般树也能象二叉树一样用二叉树链表表示，必须找出树与二叉树之间的对应关系。将一般树转换为二叉树的方法为：

（1） 在兄弟结点之间加一连线；

（2） 对每个结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系；

（3） 以树根为轴心将整棵树顺时针旋转45度。

任何一棵树转换为二叉树，其根结点的右子树必为空。

3）二叉树的遍历

遍历——按一定规律走遍树的各个结点，每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。

常用方法

先序遍历（DLR）：先访问根结点,然后分别先序遍历左子树、右子树

中序遍历（LDR）：先中序遍历左子树，然后访问根结点，最后中序遍历右子树

后序遍历（LRD）：先后序遍历左、右子树，然后访问根结点

2.2 工程手册的数据处理

基本要求：

（1）熟悉工程手册的数据处理方法；（2）掌握数表的程序化方法；（3）了解线图的程序化方法；（4）掌握最小二乘法拟合方法及其应用；（4）能用高级程序设计语言（如C语言）编写前述相应数据处理方法的基本程序并上机通过。

教学内容：

（1）数表的程序化；（2）线图的程序化；（3）建立经验公式的方法。

重点与难点：

重点：（1）查表程序设计；（2）一元函数的插值；（3）最小二乘法拟合。

难点：（1）抛物线插值中结点的选取；（2）插值程序设计及上机调试；（3）最小二乘法拟合程序设计及上机调试。

学时安排：

讲课4学时，课外上机练习不少于2学时。

在机械设计过程中，往往需要从有关的工程手册或设计规范中查找各种设计数据（资料）。这些数据在手册或规范中一般是以数表和线图的形式存放（记录）的。在进行机械CAD时，首先要把这些数表、线图形式的数据计算机化，即把它们存入计算机外、内存储器中，并设计相应的自动检索程序。

从总体上说，这些设计资料的计算机处理有以下三种方法：

（1）程序化：在应用程序内部对这些数表和线图进行处理，包括数组法和拟合公式法。

（2）数据文件法：将数表或线图中得数据编成一个独立的数据文件，存入外存，供设计解题时调用。高级程序设计语言本身一般均具备相应的数据文件处理功能。

（3）数据库法：将数表或线图中的数据暗数据库中的规定进行文件结构化，即建成数据库。

本章重点讨论程序化方法，补充介绍有关数据文件法的基本内容，数据库存储方法在后面第5章中介绍。

2.2.1 数表的程序化

l 数表的形式：

从函数角度看有：

单变量表：e.g. T.3-1～T.3-3

双变量表：e.g. T.3-4～T.3-5 单值表：e.g. T.3-3～T.3-6

多变量表：e.g. T.3-6 多值表：e.g. T.3-1～T.3-2

无变量表：e.g. 齿轮标准模数（m）系列值。

l 数表数据的形成（来源）及处理原则：

（1）有些本来就有精确的计算公式，为了便于手工设计使用，才制成表格供设计时查用（如各种数学用表）——力求找到原来的理论计算公式或经验公式→编入应用程序。（最简单的方法）。

（2）对大多数数表而言，或本来就无法表达成公式，或一时难以找到原来公式——程序化处理。

l 数表程序化方法：

1） 数组法：适于只需要用数表中所列数据（离散点、型值点或结点数据），

2） 插值法（拟合公式法）：对于需要用到数表中各离散点中间的数据。

1）数组法实例

本教材共介绍了六个实例，这里选取二个重点介绍，其余四个自己分析。

例1 平键和键槽的剖面尺寸，见图2-10和表2-1（摘引自GB/T 1095-1979）

它是单变量多值表。查表时，设计计算出的轴径dgiven→D(范围) →b,h,t,t1。可使用一维数组，D的范围可用其上限表示。变量及数组的定义：

int i;

float dgiven,b,h,t,t1;

float D[12]={10.0,12.0,…,85.0};

float kb[12]=…

.

.

.

float kt[12]=…

图2-10 平键和键槽的剖面图

表2-1 平键和键槽的尺寸表

图2-11平键和键槽的剖面尺寸查询流程

尺寸查取流程图见图2-11。

要求：用C（Turbo C or Visual C++等均可）语言编程实现该数表数据存储及查询。

例2 齿轮传动工况系数KA，见表2-2。

表2-2 齿轮传动工况系数KA

图2-12 齿轮传动工况系数KA查询流程

根据原动机机、工作机的工况→KA，使用二维数组：KK[i][j]，i=0～2:表示原动机工况，j=0～2:表示工作机工况。

变量及数组定义：

float KA;

int i,j;

float;

KK[3][3]={{1.0,1.25,1.75},{1.25,1.5,2.0},{1.5,1.75,2.25}};

查表程序流程图见图2-12。

要求：用C（Turbo C or Visual C++等均可）语言编程实现该数表数据存储及查询。

例3 说明：多变量单值表

① P1值需用三维数组NN（4,4,14），可以将P1值→数据文件→NN数组。

② 降维处理：三维→二个二维。

2） 一元函数的插值

设有一用数据表格给出的列表函数y=f(x)，如下表2-3：

表2-3 列表函数y=f(x)

表中只有几个离散点（或型值点、结点）的数据，当自变量为结点间的中间值时，就要用到插值法求取其函数值。

基本思想：在插值点附近选取几个合适的结点，过这些点构造一个简单函数g(x)，在此小段上用g(x)代替原来函数f(x)，这样插值点的函数值就用g(x)的值来代替，如图2-13。

图2-13 一元函数插值

插值的实质问题：如何构造一个既简单又具有足够精度的函数f(x)。

插值方法类型：线性插值、抛物线插值。

（1）线性插值

方法步骤：（1）选xi,xi+1,满足xix xi+1；（2）过(xi,yi)及(xi+1,yi+1)两点构造直线g(x)→f(x)。

误差问题：存在误差，当自变量间隔较小，而插值精度不要很高时，可以满足要求。

x(n),y(n)——一维数值，n——结点数。C语言下标从0开始。xgiven,ygiven——已知的x 插入值及求出的函数值。

图2-14 线性插值流程

（2）抛物线插值

在f(x)上选取三点（xi-1,yi-1）,（xi,yi）,（xi+1,yi+1），构造抛物线g(x)→f(x)。比线性插值精度好。

关键问题：根据插值点x选取合适的三个点。选取方法归纳为（“靠近原则”）：

设插值点为x，且xi-1x≤xi，i=3,4,…,n-1,

（1）若|x-xi-1|≤|x-xi|，即x靠近xi-1点或居于xi-1与 xi之中点，则选xi-2，xi-1，xi三个点，上式中i=i-1；

（2）若|x-xi-1||x-xi|，即x靠近xi点，则选xi-1，xi，xi+1三个点，上式中i=I；

（3）若x1≤x≤x2，即x靠近表头，则选x1，x2，x3三个点，上式中i=2；

（4）若x n-1≤x≤xn，即x靠近表尾，则选xn-2，xn-1，xn三个点，上式中i=n-1。

程序流程图见下图2-15。

图2-15 抛物线插值流程

要求：将线性插值与抛物线插值统一编程。

3）二元函数的插值

有二元列表函数f(xi,yi)，i=1,2,…,n，如下表2-4。

表2-4 二元列表函数

插值几何意义：在3D空间中选定几个点，通过这些点构造一块曲面g(x,y)，用它近似地表示在这区间内原有的曲面f (x,y)，从而得到插值后的函数值Zk=g(xk,yk) ， 如图2-15所示。

插值方式类型，在一元函数插值方法的基础上延伸，有以下几种：

（1）直线－直线插值

最最基本、最简单、精度最低。

如图所示，g(x,y)形成：以AB、CD为导线，作//yoz平面的直母线（EF）直线的运动→柱状面。

插值步骤：

图2-15 二元函数插值

图2-16 抛物线插值流程

(a)根据k点的(xk,yk)→周围四点a,b,c,d，满足xa=xc,xb=xd,ya=yb,yc=yd,xaxkxb,yaykyb；

(b)A,B,C,D，过A,B用线性插值→E，过C,D用线性插值→F；

(c)过E,F用线性插值→K点。

（2）抛物线－直线插值

将导线AB、CD→抛物线ABE，CDF。插值步骤：

（1）据k点的（xk,yk）→a,b,c,d＋e,f；

（2）据a,b,c,d,e,f→A,B,C,D,E,F，过A,B,E 用抛物线插值→U点，过C,D,F用抛物线插值→V点；

（3）U,V用线性插值→K点。

（3）抛物线－抛物线插值

（1）据k点的（xk,yk）→a,b,c,d+e,f＋r,s,t；

（2）据a,b,c,d, e,f,r,s,t→A,B,C,D,E,F,R,S,T，

过A,B,E用抛物线插值→U点，过C,D,F用抛物线插值→V点，过R,S,T用抛物线插值→W点；

(3) 过U,V,W用抛物线插值→K点。

上述三种插值方法统一的程序流程图见P44图3-10，三种方法由变量II控制。

要求：读懂该流程图，有余力的学生编程上机。

2.2.2 数表的公式拟合

工程实际中常需要用一定的数学方法将一系列测试数据或统计数据拟合成近似的经验公式——曲线拟合。

插值法的实质是在几何上用严格通过各结点的曲线或曲面来近似代替列表函数曲线或曲面。但通过试（实）验所得的数据离散性很大，误差比较大，因此，插值法建立的公式必然保留了所有误差，此外，要构造这样的函数的复杂度或难度比较大。有鉴于此，采用构造近似曲线、曲面，此曲线、曲面并不严格通过所有结点，而是尽可能反映所给数据的趋势，这种利用所给数据建立拟合或近似曲线或曲面经验公式的过程称为曲线、曲面拟合或公式拟合。

本节介绍最常用最基本的单变量曲线拟合方法——最小二乘法。（其他常用的还有Bezier法、三次参数样条法、B样条法等）。

1）最小二乘法拟合的基本思想

根据离散点的大致分布规律，先确定拟合函数的类型，如多项式函数、指数函数、对数函数等，计算出各数据点横坐标处的函数值与纵坐标之间的偏差的平方，求其和并使之为最小值，从而解出函数的待定系数。

已知由线图或实验所得m个点的值为：(x1,y1)，(x1,y1)，……，(xm,ym)，设拟合函数公式为：y=f(x)，则每一结点处的偏差为： (i=1,2,…,m)，偏差的平方和为：

求 min 函数f(x)的待定系数→ f(x)

拟合函数的类型，常选取初等函数，如对数函数、指数函数、代数多项式等。一般是根据数据曲线形态判断所采用的函数类型。最常用的是代数多项式拟合。本节只讨论在选定函数类型的情况下如何确定各系数值的问题。

2）最小二乘法的（代数）多项式拟合

设拟合公式为： (n次多项式)

已知m个点的值(x1,y1)，(x1,y1)，……，(xm,ym),且mn，结点偏差的平方和为：

为使 j=0,1,2,…,n

其中：（k=1,2,…,2m+1）

这是一个关于的n+1个线性方程组，求解该方程组→→f(x)

常用二次三项式拟合公式：

例1 介绍

程序流程图，见P.44图3-13

要求：看懂该流程图，该流程图中采用了高斯消去法解联立方法（详见3.3.4节），有余力的学生编程上机。

平衡二叉树的操作（高手进）

以前做的。

一、 需求分析

1． 本程序是是利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找、插入和删除。

2． 初始，平衡二叉树为空树，可以按先序输入平衡二叉树，以输入0结束，中间以回车隔开，创建好二叉树后，可以对其查找，再对其插入，输入0结束插入，再可以对其删除，输入0结束，每次插入或删除一个结点后，更新平衡二叉树的显示。

3． 本程序以用户和计算机的对话方式执行，根据计算机终端显示：“提示信息”下，用户可由键盘输入要执行的操作。

4． 测试数据（附后）

二、 概要设计

1． 抽象数据类型动态查找表的定义如下：

ADT DynamicSearchTable{

数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：

InitDSTable(DT);

操作结果：构造一个空的动态查找表DT。

DestroyDSTable(DT);

初试条件：动态查找表DT存在。

操作结果: 销毁动态查找表DT。

SearchDSTable(DT,key);

初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。

操作结果: 若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。

InsertDSTable(DT,e);

初试条件：动态查找表DT存在，e为待插入的数据元素。

操作结果: 若DT中不存在其关键字等于e. key的数据元素，则插入e到DT。

DeleteDSTable(DT,key);

初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。

操作结果: 若DT中存在其关键字等于key的数据元素，则删除之。

TraverseDSTable(DT,Visit());

初试条件：动态查找表DT存在，Visit()是结点操作的应用函数。

操作结果: 按某种次序对DT的每个结点调用函数Visit()一次且至多

一次。一但Visit()失败，则操作失败。

}ADT DynamicSearchTable

2． 本程序包含两个模块：

Void main(){

Do{

接受命令（根据提示输入终点城市和起点城市的序号）；

处理命令；

}while(“命令”=“退出”)；

}

3．本程序只有两个模块，调用关系简单

主程序模块

平衡二叉树的模块

三、 详细设计

1． 根据题目要求和查找的基本特点，其结点类型

typedef struct BSTnode{

int data;

int bf;

struct BSTnode *lchild,*rchild;

}BSTnode,*bstree;

#define LH +1

#define EH 0

#define RH -1

/-----------------------------************对平衡二叉树的操作

bstree InsertAVL(bstree T, int e)；

////////在平衡二叉树中插入结点。

int FindAVL(bstree p,int e)；

////////查找平衡二叉树中是否有结点e。

bstree DeleteAVL(bstree T,int e)

////////删除平衡平衡二叉树的结点e，并保持平衡二叉树的性质。

int Preordertraverse(bstree T)

////////按先序遍历平衡二叉树。

/------------------------************平衡二叉树的操作的详细算法

bstree InsertAVL(bstree T, int e)

{

bstree p;

//插入新结点，树长高置taller为TRUE

if(!T) {

T=(bstree)malloc(sizeof(BSTnode));

T-data=e;

T-lchild=T-rchild=NULL;

T-bf=EH;

taller=TRUE;

}

else {

//树中存在和e有相同关键字的结点则不再插入

if(e==T-data){

taller=FALSE;

return NULL;

}

//值小于则继续在树的左子树中搜索

if(e T-data){

//插入到左子树且左子树长高

p=InsertAVL(T-lchild,e);

if(p){

T-lchild=p;

if(taller) {

switch(T-bf){ //检查*T的平衡度

case LH: //原本左子树比右子树高，需要做左平衡处理

T=LeftBalance(T);

taller=FALSE;

break;

case EH: //原本左子树和右子树同高，现因左子树争高而使树增高

T-bf=LH;

taller=TRUE;

break;

case RH: //原本右子树比左子树高，现在左右子树等高

T-bf=EH;

taller=FALSE;

break;

}///////switch(T-bf)

}///////if(taller)

}/////if(p)

}///////if(e T-data)

//继续在*T的右子树中搜索

else{

//插入到右子树且使右子树长高

p=InsertAVL(T-rchild,e);

if (p){

T-rchild=p;

if(taller) {

switch(T-bf){ //检查*T的平衡度

case LH: //原本左子树比右子树高，现在左右子树等高

T-bf=EH;

taller=FALSE;

break;

case EH: //原本左子树和右子树同高，现因右子树增高而使树增高

T-bf=RH;

taller=TRUE;

break;

case RH: //原本右子树比左子树高，需要做右平衡处理

T=RightBalance(T);

taller=FALSE;

break;

}//////switch(T-bf)

}/////if(taller)

}/////if (p)

}//////if(e T-data)

}///////else

return T;

}

int Preordertraverse(bstree T){

if(T){

printf(" %d %d\n",T-data,T-bf);

Preordertraverse(T-lchild);

Preordertraverse(T-rchild);

}

return 1;

}

int FindAVL(bstree p,int e){

if(p==NULL)return NULL;

else if(e==p-data) return true;

else if(ep-data){

p=p-lchild;

return FindAVL(p, e);

}////左子树上查找

else {

p=p-rchild;

return FindAVL( p, e);

}////右子树上查找

}

bstree DeleteAVL(bstree T,int e){

//删除后要保证该二叉树还是平衡的

int n,m=0;/////标记

bstree q;

if(!T)return NULL;

else {

if(e==T-data) {////直接删除

n=Delete(T,e);

m=n;

if(m!=0) {

q=T;

DeleteAVL(T,m);

q-data=m;}

}

else {

if(eT-data){////在左子树上寻找

DeleteAVL(T-lchild,e);

if(shorter){

switch(T-bf){

case LH:T-bf=EH;shorter=true;break;

case EH:T-bf=RH;shorter=false;break;

case RH:Delete_Rightbalance(T);shorter=true;break;

}////switch(T-bf)

}/////if(shorter)

}/////if(eT-data)

else{ /////////在右子树上寻找

DeleteAVL(T-rchild,e);

if(shorter)

switch(T-bf){

case LH:Delete_Leftbalance(T);shorter=true;break;

case EH:T-bf=LH;shorter=false;break;

case RH:T-bf=EH;shorter=true;break;

}////////switch(T-bf)

}////////在右子数上寻找完

}////////在左右子上完

}///////////删除完

return T;

}

2． 主程序和其他伪码算法

void main(){

while(e!=0){

if(e!=0) InsertAVL(T,e);

}

while(d!=0){

if(d!=0) InsertAVL(T,d);

Preordertraverse(T);

}

c=FindAVL(T,t);

if(c==1)printf("有要查找的节点\n");

else printf("无要查找的节点\n");

do{

DeleteAVL(T,b);

Preordertraverse(T);

}while(b==1);

}

///右旋

bstree R_Rotate(bstree p){

bstree lc;

lc=p-lchild;

p-lchild=lc-rchild;

lc-rchild=p;

p=lc;

return p;

}

////左旋

bstree L_Rotate(bstree p){

bstree rc;

rc=p-rchild;

p-rchild=rc-lchild;

rc-lchild=p;

p=rc;

return p;

}

/////左平衡处理

bstree LeftBalance(bstree T){

bstree lc,rd;

lc=T-lchild; //lc指向*T的左子树根结点

switch(lc-bf) { //检查*T的左子树平衡度，并做相应的平衡处理

case LH: //新结点插入在*T的左孩子的左子树上，要做单右旋处理

T-bf=lc-bf=EH;

T=R_Rotate(T);

break;

case RH: //新结点插入在*T的左孩子的右子树上，要做双旋处理

rd=lc-rchild; //rd指向*T的左孩子的右子树根

switch(rd-bf){ //修改*T及其左孩子的平衡因子

case LH:

T-bf=RH;

lc-bf=EH;

break;

case EH:

T-bf=lc-bf=EH;

break;

case RH:

T-bf=EH;

lc-bf=LH;

break;

}//////////switch(rd-bf)

rd-bf=EH;

T-lchild=L_Rotate(T-lchild); //对*T的左孩子做左旋平衡处理

T=R_Rotate(T); //对*T做右旋处理

}////////switch(lc-bf)

return T;

}

////右平衡处理

bstree RightBalance(bstree T)

{

bstree rc,ld;

rc=T-rchild; //rc指向*T的右子树根结点

switch(rc-bf) { //检查*T的右子树平衡度，并做相应的平衡处理

case RH: //新结点插入在*T的右孩子的右子树上，要做单右旋处理

T-bf=rc-bf=EH;

T=L_Rotate(T);

break;

case LH: //新结点插入在*T的右孩子的左子树上，要做双旋处理

ld=rc-lchild; //ld指向*T的右孩子的左子树根

switch(ld-bf){ //修改*T及其右孩子的平衡因子

case LH:

T-bf=EH;

rc-bf=RH;

break;

case EH:

T-bf=rc-bf=EH;

break;

case RH:

T-bf=LH;

rc-bf=EH;

break;

}///switch(ld-bf)

ld-bf=EH;

T-rchild=R_Rotate(T-rchild); //对*T的右孩子做右旋平衡处理

T=L_Rotate(T); //对*T做左旋处理

}/////switch(rc-bf)

return T;

}

int Delete(bstree T,int e){

//删除结点

bstree p,q;

e=0;

p=T;

if(!T-rchild) {//右子数为空需要重接它的左子数

T=T-lchild;

free(p);

shorter=true;

}

else if(!T-lchild) {//重接它的右子数

T=T-rchild;

free(p);

shorter=true;

}

else{ //左右子数均不空

q=T-lchild;

while(q-rchild!=NULL){//转左，然后向右到尽头

q=q-rchild;

}

e=q-data;

}

return e;

}

void Delete_Rightbalance(bstree T){

///////////删除在左子树上的，相当于插入在右子树

bstree rc=T-rchild,ld;

switch(rc-bf){

case LH://///////双旋 ，先右旋后左旋

ld=rc-lchild;

rc-lchild=ld-rchild;

ld-rchild=rc;

T-rchild=rc-lchild;

rc-lchild=T;

switch(ld-bf) {

case LH:T-bf=EH;

rc-bf=RH;

break;

case EH:T-bf=rc-bf=EH;

break;

case RH:T-bf=LH;

rc-bf=EH;

break;

}

ld-bf=EH;

T=rc;

shorter=true;break;

case EH:///////删除在左子树，相当于插入在右子树，左单旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=LH;

T-bf=RH;

T=rc;

shorter=EH;break;

case RH:///////删除在左子树，相当于插入在右子树，左单旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=T-bf=EH;

T=rc;

shorter=true;break;

}

}

void Delete_Leftbalance(bstree T)/////删除右子树上的，相当于插入在左子树上

{

bstree p1,p2;

p1=T-lchild;

switch(p1-bf) {

case LH:T-lchild=p1-rchild;//////右旋

p1-rchild=T;

p1-bf=T-bf=EH;

T=p1;

shorter=true;

break;

case EH:T-lchild=p1-rchild;///////右旋

p1-rchild=T;

p1-bf=RH;

T-bf=LH;

T=p1;

shorter=false;

break;

case RH:p2=p1-rchild;//////////右双旋

p1-rchild=p2-lchild;

p2-lchild=p1;

T-lchild=p2-rchild;

p2-rchild=T;

switch(p2-bf){

case LH:T-bf=RH;p1-bf=EH;break;

case EH:T-bf=EH;p1-bf=EH;break;

case RH:T-bf=EH;p1-bf=LH;break;

}

p2-bf=EH;

T=p2;

shorter=true;break;

}

}

3． 函数的调用关系图

Main

InsertAVL Preordertraverse FindAVL DeleteAVL

四、 调试分析

1． 在开始对平衡二叉树的插入后，再做平衡处理时，特别是在做双向旋转平衡处理后的更新时，费了一些时间；

2． 在做平衡二叉树的删除时，当删除结点左右孩子均在时，开始直接用左子树的最大数代替，然后直接删除结点，结果导致删除了将要删除的结点及其孩子均删除了，后来将要删除的结点用左子树的最大树代替后，对左子树的最大结点做好标记，然后再做对其做删除处理。

3． 本程序算法基本简单，没有多大困难，就是在分析做双旋平衡处理的更新时，开始思路有些混乱，后来就好了；

五、 用户手册

1. 本程序的运行环境为DOS操作系统，执行文件为Balanced Tree.exe。

2. 进入演示程序后，按广度遍历输入平衡二叉树，中间以回车键隔开，输入0为结束；再输入要插入的结点，输入0结束，再输入要查找的结点，最后可以输入要删除的结点，输入0结束

六、 测试结果

先按广度遍历创建平衡二叉树（亦可一个一个的插入二叉树的结点）（50 20 60 10 30 55 70 5 15 25 58 90） ，输入0结束，然后可插入结点（39），其会显示插入后的二叉树，输入0，不再插入；输入要查找结点（6），输入要删除的结点（20），其显示如下：

七、 附录

Balance Tree.cpp

网站名称：平衡因子递归函数c语言 数据结构平衡因子怎么算
分享地址：http://azwzsj.com/article/dddgepd.html