7.6 AVL樹
創(chuàng)新互聯(lián)專注于高州企業(yè)網(wǎng)站建設,成都響應式網(wǎng)站建設,電子商務商城網(wǎng)站建設。高州網(wǎng)站建設公司,為高州等地區(qū)提供建站服務。全流程按需定制設計，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務
7.6.1 AVL樹的定義
高度平衡的二叉搜索樹
一棵AVL樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。
高度不平衡的二叉搜索樹 高度平衡的二叉搜索樹
結(jié)點的平衡因子balance (balance factor)
1、每個結(jié)點附加一個數(shù)字，給出該結(jié)點右子樹的高度減去左子樹的高度所得的高度差。這個數(shù)字即為結(jié)點的平衡因子balance 。
2、根據(jù)AVL樹的定義，任一結(jié)點的平衡因子只能取 -1，0和 1。
3、如果一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉搜索樹就失去了平衡，不再是AVL樹。
4、如果一棵二叉搜索樹是高度平衡的，它就成為 AVL樹。如果它有n個結(jié)點，其高度可保持在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 平衡化旋轉(zhuǎn)
1、如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。
此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化。
2、平衡化旋轉(zhuǎn)有兩類：
單旋轉(zhuǎn) (左旋和右旋) 雙旋轉(zhuǎn) (左平衡和右平衡)
3、每插入一個新結(jié)點時，AVL樹中相關結(jié)點的平衡狀態(tài)會發(fā)生改變。因此，在插入一個新結(jié)點后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點的平衡因子(左、右子樹的高度差)。
4、如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。
5、從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點。
6、 如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化。單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn)，其中一個是另一個的鏡像，其方向與不平衡的形狀相關。
7、如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。
右單旋轉(zhuǎn)
左單旋轉(zhuǎn)
左右雙旋轉(zhuǎn)
右左雙旋轉(zhuǎn)
1、左單旋轉(zhuǎn) (RotateLeft )
(1)如果在子樹E中插入一個新結(jié)點，該子樹高度增1導致結(jié)點A的平衡因子變成+2，出現(xiàn)不平衡。
(2)沿插入路徑檢查三個結(jié)點A、C和E。它們處于一條方向為“\”的直線上，需要做左單旋轉(zhuǎn)。
(3)以結(jié)點C為旋轉(zhuǎn)軸，讓結(jié)點A反時針旋轉(zhuǎn)。
左單旋轉(zhuǎn)的算法
template class Type void AVLTreetype:: RotateLeft ( AVLNode *Tree, AVLNode* NewTree ) {
NewTree = Tree→right;
Tree→right = NewTree→left;
NewTree→left = Tree;
}
2、右單旋轉(zhuǎn) (RotateRight )
(1)在左子樹D上插入新結(jié)點使其高度增1，導致結(jié)點A的平衡因子增到 -2，造成了不平衡。
(2) 為使樹恢復平衡，從A沿插入路徑連續(xù)取3個結(jié)點A、B和D，它們處于一條方向為“/”的直線上，需要做右單旋轉(zhuǎn)。
(3) 以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)。
右單旋轉(zhuǎn)的算法
template class Type void AVLTreetype:: RotateRight( AVLNode *Tree, AVLNode* NewTree) {
NewTree = Tree→left;
Tree→left = NewTree→right;
NewTree→right = Tree;
}
3、先左后右雙旋轉(zhuǎn) (RotationLeftRight)
(1)在子樹F或G中插入新結(jié)點，該子樹的高度增1。結(jié)點A的平衡因子變?yōu)?-2，發(fā)生了不平衡。
(2) 從結(jié)點A起沿插入路徑選取3個結(jié)點A、B和E，它們位于一條形如“?”的折線上，因此需要進行先左后右的雙旋轉(zhuǎn)。
(3)首先以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點B反時針旋轉(zhuǎn)，以E代替原來B的位置，做左單旋轉(zhuǎn)。
(4) 再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)，做右單旋轉(zhuǎn)。使之平衡化。
左平衡化的算法
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 “樹已經(jīng)平衡化.\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、先右后左雙旋轉(zhuǎn) (RotationRightLeft)
(1)右左雙旋轉(zhuǎn)是左右雙旋轉(zhuǎn)的鏡像。
(2) 在子樹F或G中插入新結(jié)點，該子樹高度增1。結(jié)點A的平衡因子變?yōu)?，發(fā)生了不平衡。
(3) 從結(jié)點A起沿插入路徑選取3個結(jié)點A、C和D，它們位于一條形如“?”的折線上，需要進行先右后左的雙旋轉(zhuǎn)。
(4)首先做右單旋轉(zhuǎn)：以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點C順時針旋轉(zhuǎn)，以D代替原來C的位置。
(5) 再做左單旋轉(zhuǎn)：以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點A反時針旋轉(zhuǎn)，恢復樹的平衡。
右平衡化的算法
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 “樹已經(jīng)平衡化.\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樹中插入一個新結(jié)點時，如果樹中某個結(jié)點的平衡因子的絕對值 |balance| 1，則出現(xiàn)了不平衡，需要做平衡化處理。
2、在AVL樹上定義了重載操作“”和“”，以及中序遍歷的算法。利用這些操作可以執(zhí)行AVL樹的建立和結(jié)點數(shù)據(jù)的輸出。
3、 算法從一棵空樹開始，通過輸入一系列對象的關鍵碼，逐步建立AVL樹。在插入新結(jié)點時使用了前面所給的算法進行平衡旋轉(zhuǎn)。
例，輸入關鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和調(diào)整過程如下。
從空樹開始的建樹過程
1、下面的算法將通過遞歸方式將新結(jié)點作為葉結(jié)點插入并逐層修改各結(jié)點的平衡因子。
2、 在發(fā)現(xiàn)不平衡時立即執(zhí)行相應的平衡化旋轉(zhuǎn)操作，使得樹中各結(jié)點重新平衡化。
3、 在程序中，用變量success記載新結(jié)點是否存儲分配成功，并用它作為函數(shù)的返回值。
4、算法從樹的根結(jié)點開始，遞歸向下找插入位置。在找到插入位置(空指針)后，為新結(jié)點動態(tài)分配存儲空間，將它作為葉結(jié)點插入，并置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時做必要的調(diào)整。
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樹的重載操作 、 和遍歷算法的實現(xiàn) :
template class Type istream operator ( istream in, AVLTreetype Tree ) {
Type item;
cout “構(gòu)造AVL樹 :\n";
cout “輸入數(shù)據(jù)(以" Tree.RefValue “結(jié)束): ";
in item;
while ( item != Tree.RefValue ) {
Tree.Insert (item);
cout “輸入數(shù)據(jù)(以" Tree.RefValue “結(jié)束): ";
in item;
}
return in;
}
template class Type void AVLTree type
:: Traverse ( AVLNode *ptr, ostream out ) const { //AVL樹中序遍歷并輸出數(shù)據(jù)
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、如果被刪結(jié)點x最多只有一個子女，那么問題比較簡單。如果被刪結(jié)點x有兩個子女，首先搜索 x 在中序次序下的直接前驅(qū) y (同樣可以找直接后繼)。再把 結(jié)點y 的內(nèi)容傳送給結(jié)點x，現(xiàn)在問題轉(zhuǎn)移到刪除結(jié)點 y。 把結(jié)點y當作被刪結(jié)點x。
2、 將結(jié)點x從樹中刪去。因為結(jié)點x最多有一個子女，我們可以簡單地把x的雙親結(jié)點中原來指向x的指針改指到這個子女結(jié)點；如果結(jié)點x沒有子女，x雙親結(jié)點的相應指針置為NULL。然后將原來以結(jié)點x為根的子樹的高度減1，
3、必須沿x通向根的路徑反向追蹤高度的變化對路 徑上各個結(jié)點的影響。
4、 用一個布爾變量 shorter 來指明子樹的高度是否被縮短。在每個結(jié)點上要做的操作取決于 shorter 的值和結(jié)點的 balance，有時還要依賴子女的 balance 。
5、 布爾變量 shorter 的值初始化為True。然后對于從 x 的雙親到根的路徑上的各個結(jié)點 p，在 shorter 保持為 True 時執(zhí)行下面的操作。如果 shorter 變成False，算法終止。
6、case 1 : 當前結(jié)點p的balance為0。如果它的左子樹或右子樹被縮短，則它的 balance改為1或-1，同時 shorter 置為False。
7、case 2 : 結(jié)點p的balance不為0，且較高的子樹被縮短，則p的balance改為0，同時 shorter 置為True。
8、case 3 : 結(jié)點p的balance不為0，且較矮的子樹又被縮短，則在結(jié)點p發(fā)生不平衡。需要進行平衡化旋轉(zhuǎn)來恢復平衡。令p的較高的子樹的根為 q (該子樹未被縮短)，根據(jù)q的balance ，有如下3種平衡化操作。
9、case 3a : 如果q的balance為0，執(zhí)行一個單旋轉(zhuǎn)來恢復結(jié)點p的平衡，置shorter為False。
10、 case 3b : 如果q的balance與p的balance相同，則執(zhí)行一個單旋轉(zhuǎn)來恢復平衡，結(jié)點p和q的balance均改為0，同時置shorter為True。
11、case 3c : 如果p與q的balance相反，則執(zhí)行一個雙旋轉(zhuǎn)來恢復平衡，先圍繞 q 轉(zhuǎn)再圍繞 p 轉(zhuǎn)。新的根結(jié)點的balance置為0，其它結(jié)點的balance相應處理，同時置shorter為True。
12、 在case 3a, 3b和3c的情形中，旋轉(zhuǎn)的方向取決于是結(jié)點p的哪一棵子樹被縮短。
7.6.4 AVL樹的高度
1、設在新結(jié)點插入前AVL樹的高度為h，結(jié)點個數(shù)為n，則插入一個新結(jié)點的時間是O(h)。對于AVL樹來說，h多大？
2、設 Nh 是高度為 h 的AVL樹的最小結(jié)點數(shù)。根的一棵子樹的高度為 h-1，另一棵子樹的高度為 h-2，這兩棵子樹也是高度平衡的。因此有 N-1 = 0 (空樹) N0 = 1 (僅有根結(jié)點) Nh = Nh-1 + Nh-2 +1 , h 0
3、可以證明，對于 h ? 0，有 Nh = Fh+3 -1 成立。
4、有n個結(jié)點的AVL樹的高度不超過
5、在AVL樹刪除一個結(jié)點并做平衡化旋轉(zhuǎn)所需時間為 O(log2n)。
6、 二叉搜索樹適合于組織在內(nèi)存中的較小的索引(或目錄)。對于存放在外存中的較大的文件系統(tǒng)，用二叉搜索樹來組織索引不太合適。
7、 在文件檢索系統(tǒng)中大量使用的是用B_樹或B+樹做文件索引。
看這個圖從根節(jié)點開始如果平衡因子大于1就選左節(jié)點，小于1就選右節(jié)點，等于0終止。使用while循環(huán)就可以了，循環(huán)結(jié)束時的循環(huán)次數(shù)就是樹的高度。
int loop=0;
當前節(jié)點=根節(jié)點
while(true)
{
loop++;
if(當前節(jié)點的平衡因子0)
{當前節(jié)點=左子樹}
else?if(當前節(jié)點的平衡因子0)
{當前節(jié)點=右子樹}
else
{退出循環(huán)}
}
loop就是樹高度
1）數(shù)據(jù)數(shù)據(jù)的概念十分廣泛，它通常是對客觀事物的數(shù)量、特征、性質(zhì)的描述。對計算機而言，數(shù)據(jù)是計算機所能處理的一切數(shù)值、字符、圖形或其他特定符號的總稱，是計算機加工處理的“原料”和它所生產(chǎn)的“產(chǎn)品”(計算的結(jié)果)。2）數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，也稱作結(jié)點和記錄。在計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。3）數(shù)據(jù)對象數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。 1、 數(shù)據(jù)結(jié)構(gòu)（Data Structure）
數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中個數(shù)據(jù)元素之間存在的關系（相互間存在一種或多種特定關系的數(shù)據(jù)元素的集合）。
根據(jù)數(shù)據(jù)結(jié)構(gòu)的形式定義，數(shù)據(jù)結(jié)構(gòu)是一個二元組：
S（Data-Structure）=(D，R)
其中：D是數(shù)據(jù)元素的有限集，R是D上關系的有限集。
邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
數(shù)據(jù)之間的相互關系稱為邏輯結(jié)構(gòu)。通常分為三類基本結(jié)構(gòu)：
（一）集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關系。
（二）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關系。
（三）非線性結(jié)構(gòu)：
樹型結(jié)構(gòu)——結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關系。
圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)——結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關系。
數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。
（一般我們將數(shù)據(jù)的邏輯結(jié)構(gòu)稱為是數(shù)據(jù)結(jié)構(gòu)，）
存儲結(jié)構(gòu)可分為：順序存儲與鏈式存儲。
順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關系；
鏈式存儲結(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關系。
數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關。
2.1.2 線性表
1）線性表定義
線性表(Linear List) ：由n(n≧)個數(shù)據(jù)元素(結(jié)點)a1，a2， …an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當n=0時稱為空表，常常將非空的線性表(n0)記作：
L = (a1，a2，…an)
這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。
2）線性表特點
線性表的邏輯結(jié)構(gòu)有以下特點：
在數(shù)據(jù)元素的非空有限集中
? 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素
? 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素
? 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)
? 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼
3）線性表的基本運算
線性表的主要運算有：
插入：在兩個確定元素之間插入一個新元素；
刪除：刪除線性表中的某個元素；
查找：按某種要求查找線性表中的一個元素，需要時還可以進行更新；
排序：按給定要求對表中元素重新排序；
還有初始化、求長度等。
在不同問題的線性表中，需要進行的運算也不相同，實際應用中還可能涉及建立線性表、修改表中元素數(shù)值（編輯）等運算，但是基本上可以由上述四種運算組成。
4）順序存儲線性表
（1）順序存儲結(jié)構(gòu)
把線性表的數(shù)據(jù)元素，按順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表，也稱為向量式存儲結(jié)構(gòu)。
假設線性表的每個元素需占用個存儲單元，且線性表在內(nèi)存中的首地址為，則線性表中第個數(shù)據(jù)元素的存儲地址為：
則線性表中第個數(shù)據(jù)元素的存儲位置和第個數(shù)據(jù)元素的存儲位置之間滿足下列關系：
這種存儲結(jié)構(gòu)只要知道數(shù)據(jù)元素序號，就很容易找到第個數(shù)據(jù)元素。它的主要特點有：一、各數(shù)據(jù)元素存儲地址上相鄰；二、無論序號為何值，找到第個元素的時間相同。
這種存儲結(jié)構(gòu)在高級語言中可以用一維數(shù)組的形式實現(xiàn)。
（2）順序存儲結(jié)構(gòu)的優(yōu)缺點
優(yōu)點
? 邏輯相鄰，物理相鄰；
? 可隨機存取任一元素；
? 存儲空間使用緊湊。
缺點
? 插入、刪除操作需要移動大量的元素；
? 預先分配空間需按最大空間分配，利用不充分；
? 表容量難以擴充。
5）線性鏈表
特點：
? 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素；
? 利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素；
? 每個數(shù)據(jù)元素，除存儲本身信息外，還需存儲其直接后繼的信息。
數(shù)據(jù)元素由兩部分組成：
? 數(shù)據(jù)域：存放元素本身信息；
? 指針域：指示直接后繼的存儲地址。
線性鏈表一般在第一個結(jié)點之前附加一個頭結(jié)點：
2.1.3 棧與隊
棧和隊是兩種特殊的線性表，它們的運算規(guī)則較一般線性表由更多的約束和限制，因此稱作限定性數(shù)據(jù)結(jié)構(gòu)。
1）棧的結(jié)構(gòu)和運算
（1）棧的定義
棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當表中沒有元素時稱為空棧。
假設棧，則稱為棧底元素，為棧頂元素。棧中元素按的次序進棧，的順序退棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為后進先出表（LIFO，last in first out）。
棧的存儲結(jié)構(gòu)也有順序與鏈式兩種，稱為順序棧與鏈棧。
（2）順序棧
由于棧是運算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適應。
棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的，所以可以將棧底位置設置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需用一個整型變量top來指示棧頂位置。如果用m來表示棧的最大容量，則top=0表示棧空，此時出棧，則下溢（underflow）；top=m表示棧滿，此時入棧，則上溢（overflow）。
（3）棧的應用
表達式求值
表達式求值步驟：首先在OS棧中放入表達式結(jié)束符“；”，
l 若為操作數(shù)，將其壓入NS棧；
l 若為運算符，比較當前OS棧的棧頂元素：
ü 若當前運算符的優(yōu)先數(shù)大于OS棧頂?shù)倪\算符，則將當前運算符壓入OS棧；
ü 若當前運算符的優(yōu)先數(shù)不大于OS棧頂運算符，則從NS棧中彈出兩個操作數(shù)x,y，再從OS中彈出一個運算符，，并將結(jié)果T送入NS棧。
ü 若當前運算符為“；”，且OS棧頂也為“；”，則表示表達式處理結(jié)束，此時，NS棧頂元素即為此表達式值。
過程嵌套和遞歸調(diào)用
過程嵌套調(diào)用如圖所示：
當調(diào)用子過程時，必須把斷點的信息及地址保存起來，當子過程執(zhí)行完畢，返回時，取用這些信息，找到返回地址，從此斷點繼續(xù)執(zhí)行。當程序中出現(xiàn)多重嵌套調(diào)用時，必須開辟一個棧，將各層斷點信息依次入棧，當各層子過程返回時，又以相反的次序從棧頂取出。
遞歸調(diào)用
函數(shù)直接或間接地調(diào)用自身叫遞歸調(diào)用，這主要時用遞歸工作棧來實現(xiàn)的。下面舉一個簡單的例子來說明遞歸調(diào)用。
例 一段遞歸調(diào)用的C語言程序如下：
void print(int w)
{
int I;
if (w!=0)
{
print (w-1);
for (I=1; I=w; ++I)
printf(“%3d,”,w);
printf(“/n”);
}
}
在這段程序中，遞歸調(diào)用的執(zhí)行過程如圖所示：
2） 隊的結(jié)構(gòu)和運算
（1）隊的定義
隊是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表。
隊尾(rear)——允許插入的一端
隊頭(front)——允許刪除的一端
隊的特點是：先進先出(FIFO)
（2）順序隊
存在問題：
設數(shù)組維數(shù)為M，則：
當front=-1,rear=M-1時，再有元素入隊發(fā)生溢出——真溢出
l當front1-1,rear=M-1時，再有元素入隊發(fā)生溢出——假溢出
解決方案：
l 隊首固定，每次出隊剩余元素向下移動——浪費時間
l 循環(huán)隊列
? 基本思想：把隊列設想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;
? 實現(xiàn)：利用“?！边\算
入隊： rear=(rear+1)%M; sq[rear]=x;
出隊： front=(front+1)%M; x=sq[front];
? 隊滿、隊空判定條件
front=rear
解決方案：
n 另外設一個標志以區(qū)別隊空、隊滿
n 少用一個元素空間：
隊空：front==rear
隊滿：(rear+1)%M==front
2.1.4 數(shù)組
1）數(shù)組的定義
（1）定義
數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個線性表。用線性表的一般表示形式定義二維數(shù)組為：
其中，K由個結(jié)點組成：
R由以下兩種關系組成：
（2）數(shù)組特點
l 數(shù)組結(jié)構(gòu)固定
l 數(shù)據(jù)元素同構(gòu)
（3）數(shù)組運算
數(shù)組一旦被定義，它的維數(shù)和數(shù)據(jù)元素的個數(shù)就已經(jīng)固定，不能插入和刪除，所以數(shù)組運算只有：
l 給定一組下標，存取相應的數(shù)據(jù)元素
l 給定一組下標，修改數(shù)據(jù)元素的值
2）數(shù)組的順序存儲結(jié)構(gòu)
由于計算機的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。
又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數(shù)組。
根據(jù)不同的存放形式，可以分為按行優(yōu)先和按列優(yōu)先順序存放。
（1）按行優(yōu)先順序存放
按行優(yōu)先順序存放，對二維數(shù)組來說就是按行進行切分，如圖所示：
假設每個數(shù)據(jù)元素只占一個單元地址，則元素的存放地址可以通過以下關系式計算：
（2）按列優(yōu)先順序存放
如果數(shù)組按列切分，就得到按列優(yōu)先順序存放方式。如圖所示：
元素的存放地址可以通過以下關系式計算：
2.1.5 樹與二叉樹
1）樹的定義及其存儲結(jié)構(gòu)
（1）樹的定義和術(shù)語
定義：樹(Tree)是n(n=0)個結(jié)點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：
(1)有且僅有一個特定的稱為根(Root)的結(jié)點；
(2)其余的結(jié)點可分為m(m=0)個互不相交的子集T1,T2,T3…Tm，其中每個子集又是一棵樹，并稱其為子樹(Subtree)。
基本術(shù)語:
l 結(jié)點(node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支；
l 結(jié)點的度(degree)——結(jié)點擁有的子樹數(shù)；
l 葉子(leaf)——度為0的結(jié)點；
l 孩子(child)——結(jié)點子樹的根稱為該結(jié)點的孩子；
l 雙親(parents)——孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親；
l 兄弟(sibling)——同一雙親的孩子；
l 樹的度——一棵樹中最大的結(jié)點度數(shù)；
l 結(jié)點的層次(level)——從根結(jié)點算起，根為第一層，它的孩子為第二層……；
l 深度(depth)——樹中結(jié)點的最大層次數(shù)；
l 森林(forest)——m(m=0)棵互不相交的樹的集合；
（2）樹的存儲結(jié)構(gòu)
樹的存儲結(jié)構(gòu)有多種形式，這里只討論鏈式存儲結(jié)構(gòu)。因為樹是多分支非線性表，因此采用多重鏈表結(jié)構(gòu)，即每個結(jié)點設有多個指針域，其中每個指針指向一棵子樹的根結(jié)點。對于每一個結(jié)點的結(jié)構(gòu)類型有兩種形式：結(jié)點異構(gòu)型、結(jié)點同構(gòu)型。
結(jié)點異構(gòu)型，是根據(jù)每個結(jié)點的子樹數(shù)設置相應的指針域，由于每個結(jié)點的度數(shù)不同，則同一棵樹中，結(jié)點形式也不同。這種結(jié)構(gòu)形式雖然能節(jié)省存儲空間，但運算不方便。
結(jié)點同構(gòu)型，是每個結(jié)點的指針域個數(shù)均為樹的度數(shù)。這種形式運算方便，但會使鏈表中出現(xiàn)很多空鏈域，浪費空間。
當樹的度數(shù)k=2時，空鏈域的比例最低，這就是要介紹的二叉樹。
2）二叉樹及其性質(zhì)
二叉樹在樹結(jié)構(gòu)的應用中起著非常重要的作用，因為對二叉樹的許多操作算法簡單，而任何樹都可以與二叉樹 相互轉(zhuǎn)換，這樣就解決了樹的存儲結(jié)構(gòu)及其運算中存在的復雜性。
（1）二叉樹定義及其存儲結(jié)構(gòu)
定義：二叉樹是由n(n=0)個結(jié)點的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。
這也是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個概念。
二叉樹結(jié)點的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。
圖2-8 二叉樹
存儲結(jié)構(gòu)：通常用具有兩個指針域的鏈表作為二叉樹的存儲結(jié)構(gòu)，其中，每個結(jié)點由數(shù)據(jù)域（data）、左指針域（L child）和右指針域（R child）組成，如圖所示：
圖2-9 二叉鏈表
這就是二叉鏈表，還有三叉鏈表就是在這一基礎上增加一個雙親結(jié)點指針。
（2）二叉樹的基本性質(zhì)
（1） 在二叉樹的第層上，至多有個結(jié)點。
（2） 深度為h的二叉樹中，至多含有個結(jié)點。
（3） 對任意一棵二叉樹，若有個子結(jié)點，個度為2的結(jié)點，則必有。
（3）幾種特殊形式的二叉樹
l 滿二叉樹
一棵深度為h且有2h-1個結(jié)點的二叉樹稱為滿二叉樹。
l 完全二叉樹
如果深度為h、有n個結(jié)點的二叉樹中的結(jié)點能夠與深度為h的順序編號的滿二叉樹從1到n標號的結(jié)點相對應，則該樹稱為完全二叉樹。
完全二叉樹的特點是：
所有的葉結(jié)點都出現(xiàn)在第h層或h－1層。
錯任一結(jié)點，如果其右子樹的最大層次為1，則其左子樹的最大層次為1或l＋1。
滿二叉樹是完全二叉樹的特例。
（1） 平衡二叉樹
所有結(jié)點的平衡因子為-1、0、1。
（4）一般樹轉(zhuǎn)換為二叉樹
為了使一般樹也能象二叉樹一樣用二叉樹鏈表表示，必須找出樹與二叉樹之間的對應關系。將一般樹轉(zhuǎn)換為二叉樹的方法為：
（1） 在兄弟結(jié)點之間加一連線；
（2） 對每個結(jié)點，除了與它的第一個孩子保持聯(lián)系外，去除與其它孩子的聯(lián)系；
（3） 以樹根為軸心將整棵樹順時針旋轉(zhuǎn)45度。
任何一棵樹轉(zhuǎn)換為二叉樹，其根結(jié)點的右子樹必為空。
3）二叉樹的遍歷
遍歷——按一定規(guī)律走遍樹的各個結(jié)點，每一結(jié)點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列。
常用方法
先序遍歷（DLR）：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹
中序遍歷（LDR）：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹
后序遍歷（LRD）：先后序遍歷左、右子樹，然后訪問根結(jié)點
2.2 工程手冊的數(shù)據(jù)處理
基本要求：
（1）熟悉工程手冊的數(shù)據(jù)處理方法；（2）掌握數(shù)表的程序化方法；（3）了解線圖的程序化方法；（4）掌握最小二乘法擬合方法及其應用；（4）能用高級程序設計語言（如C語言）編寫前述相應數(shù)據(jù)處理方法的基本程序并上機通過。
教學內(nèi)容：
（1）數(shù)表的程序化；（2）線圖的程序化；（3）建立經(jīng)驗公式的方法。
重點與難點：
重點：（1）查表程序設計；（2）一元函數(shù)的插值；（3）最小二乘法擬合。
難點：（1）拋物線插值中結(jié)點的選取；（2）插值程序設計及上機調(diào)試；（3）最小二乘法擬合程序設計及上機調(diào)試。
學時安排：
講課4學時，課外上機練習不少于2學時。
在機械設計過程中，往往需要從有關的工程手冊或設計規(guī)范中查找各種設計數(shù)據(jù)（資料）。這些數(shù)據(jù)在手冊或規(guī)范中一般是以數(shù)表和線圖的形式存放（記錄）的。在進行機械CAD時，首先要把這些數(shù)表、線圖形式的數(shù)據(jù)計算機化，即把它們存入計算機外、內(nèi)存儲器中，并設計相應的自動檢索程序。
從總體上說，這些設計資料的計算機處理有以下三種方法：
（1）程序化：在應用程序內(nèi)部對這些數(shù)表和線圖進行處理，包括數(shù)組法和擬合公式法。
（2）數(shù)據(jù)文件法：將數(shù)表或線圖中得數(shù)據(jù)編成一個獨立的數(shù)據(jù)文件，存入外存，供設計解題時調(diào)用。高級程序設計語言本身一般均具備相應的數(shù)據(jù)文件處理功能。
（3）數(shù)據(jù)庫法：將數(shù)表或線圖中的數(shù)據(jù)暗數(shù)據(jù)庫中的規(guī)定進行文件結(jié)構(gòu)化，即建成數(shù)據(jù)庫。
本章重點討論程序化方法，補充介紹有關數(shù)據(jù)文件法的基本內(nèi)容，數(shù)據(jù)庫存儲方法在后面第5章中介紹。
2.2.1 數(shù)表的程序化
l 數(shù)表的形式：
從函數(shù)角度看有：
單變量表：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. 齒輪標準模數(shù)（m）系列值。
l 數(shù)表數(shù)據(jù)的形成（來源）及處理原則：
（1）有些本來就有精確的計算公式，為了便于手工設計使用，才制成表格供設計時查用（如各種數(shù)學用表）——力求找到原來的理論計算公式或經(jīng)驗公式→編入應用程序。（最簡單的方法）。
（2）對大多數(shù)數(shù)表而言，或本來就無法表達成公式，或一時難以找到原來公式——程序化處理。
l 數(shù)表程序化方法：
1） 數(shù)組法：適于只需要用數(shù)表中所列數(shù)據(jù)（離散點、型值點或結(jié)點數(shù)據(jù)），
2） 插值法（擬合公式法）：對于需要用到數(shù)表中各離散點中間的數(shù)據(jù)。
1）數(shù)組法實例
本教材共介紹了六個實例，這里選取二個重點介紹，其余四個自己分析。
例1 平鍵和鍵槽的剖面尺寸，見圖2-10和表2-1（摘引自GB/T 1095-1979）
它是單變量多值表。查表時，設計計算出的軸徑dgiven→D(范圍) →b,h,t,t1?？墒褂靡痪S數(shù)組，D的范圍可用其上限表示。變量及數(shù)組的定義：
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++等均可）語言編程實現(xiàn)該數(shù)表數(shù)據(jù)存儲及查詢。
例2 齒輪傳動工況系數(shù)KA，見表2-2。
表2-2 齒輪傳動工況系數(shù)KA
圖2-12 齒輪傳動工況系數(shù)KA查詢流程
根據(jù)原動機機、工作機的工況→KA，使用二維數(shù)組：KK[i][j]，i=0～2:表示原動機工況，j=0～2:表示工作機工況。
變量及數(shù)組定義：
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++等均可）語言編程實現(xiàn)該數(shù)表數(shù)據(jù)存儲及查詢。
例3 說明：多變量單值表
① P1值需用三維數(shù)組NN（4,4,14），可以將P1值→數(shù)據(jù)文件→NN數(shù)組。
② 降維處理：三維→二個二維。
2） 一元函數(shù)的插值
設有一用數(shù)據(jù)表格給出的列表函數(shù)y=f(x)，如下表2-3：
表2-3 列表函數(shù)y=f(x)
表中只有幾個離散點（或型值點、結(jié)點）的數(shù)據(jù)，當自變量為結(jié)點間的中間值時，就要用到插值法求取其函數(shù)值。
基本思想：在插值點附近選取幾個合適的結(jié)點，過這些點構(gòu)造一個簡單函數(shù)g(x)，在此小段上用g(x)代替原來函數(shù)f(x)，這樣插值點的函數(shù)值就用g(x)的值來代替，如圖2-13。
圖2-13 一元函數(shù)插值
插值的實質(zhì)問題：如何構(gòu)造一個既簡單又具有足夠精度的函數(shù)f(x)。
插值方法類型：線性插值、拋物線插值。
（1）線性插值
方法步驟：（1）選xi,xi+1,滿足xix xi+1；（2）過(xi,yi)及(xi+1,yi+1)兩點構(gòu)造直線g(x)→f(x)。
誤差問題：存在誤差，當自變量間隔較小，而插值精度不要很高時，可以滿足要求。
x(n),y(n)——一維數(shù)值，n——結(jié)點數(shù)。C語言下標從0開始。xgiven,ygiven——已知的x 插入值及求出的函數(shù)值。
圖2-14 線性插值流程
（2）拋物線插值
在f(x)上選取三點（xi-1,yi-1）,（xi,yi）,（xi+1,yi+1），構(gòu)造拋物線g(x)→f(x)。比線性插值精度好。
關鍵問題：根據(jù)插值點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 拋物線插值流程
要求：將線性插值與拋物線插值統(tǒng)一編程。
3）二元函數(shù)的插值
有二元列表函數(shù)f(xi,yi)，i=1,2,…,n，如下表2-4。
表2-4 二元列表函數(shù)
插值幾何意義：在3D空間中選定幾個點，通過這些點構(gòu)造一塊曲面g(x,y)，用它近似地表示在這區(qū)間內(nèi)原有的曲面f (x,y)，從而得到插值后的函數(shù)值Zk=g(xk,yk) ， 如圖2-15所示。
插值方式類型，在一元函數(shù)插值方法的基礎上延伸，有以下幾種：
（1）直線－直線插值
最最基本、最簡單、精度最低。
如圖所示，g(x,y)形成：以AB、CD為導線，作//yoz平面的直母線（EF）直線的運動→柱狀面。
插值步驟：
圖2-15 二元函數(shù)插值
圖2-16 拋物線插值流程
(a)根據(jù)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）據(jù)k點的（xk,yk）→a,b,c,d＋e,f；
（2）據(jù)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）據(jù)k點的（xk,yk）→a,b,c,d+e,f＋r,s,t；
（2）據(jù)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點。
上述三種插值方法統(tǒng)一的程序流程圖見P44圖3-10，三種方法由變量II控制。
要求：讀懂該流程圖，有余力的學生編程上機。
2.2.2 數(shù)表的公式擬合
工程實際中常需要用一定的數(shù)學方法將一系列測試數(shù)據(jù)或統(tǒng)計數(shù)據(jù)擬合成近似的經(jīng)驗公式——曲線擬合。
插值法的實質(zhì)是在幾何上用嚴格通過各結(jié)點的曲線或曲面來近似代替列表函數(shù)曲線或曲面。但通過試（實）驗所得的數(shù)據(jù)離散性很大，誤差比較大，因此，插值法建立的公式必然保留了所有誤差，此外，要構(gòu)造這樣的函數(shù)的復雜度或難度比較大。有鑒于此，采用構(gòu)造近似曲線、曲面，此曲線、曲面并不嚴格通過所有結(jié)點，而是盡可能反映所給數(shù)據(jù)的趨勢，這種利用所給數(shù)據(jù)建立擬合或近似曲線或曲面經(jīng)驗公式的過程稱為曲線、曲面擬合或公式擬合。
本節(jié)介紹最常用最基本的單變量曲線擬合方法——最小二乘法。（其他常用的還有Bezier法、三次參數(shù)樣條法、B樣條法等）。
1）最小二乘法擬合的基本思想
根據(jù)離散點的大致分布規(guī)律，先確定擬合函數(shù)的類型，如多項式函數(shù)、指數(shù)函數(shù)、對數(shù)函數(shù)等，計算出各數(shù)據(jù)點橫坐標處的函數(shù)值與縱坐標之間的偏差的平方，求其和并使之為最小值，從而解出函數(shù)的待定系數(shù)。
已知由線圖或?qū)嶒炈胢個點的值為：(x1,y1)，(x1,y1)，……，(xm,ym)，設擬合函數(shù)公式為：y=f(x)，則每一結(jié)點處的偏差為： (i=1,2,…,m)，偏差的平方和為：
求 min 函數(shù)f(x)的待定系數(shù)→ f(x)
擬合函數(shù)的類型，常選取初等函數(shù)，如對數(shù)函數(shù)、指數(shù)函數(shù)、代數(shù)多項式等。一般是根據(jù)數(shù)據(jù)曲線形態(tài)判斷所采用的函數(shù)類型。最常用的是代數(shù)多項式擬合。本節(jié)只討論在選定函數(shù)類型的情況下如何確定各系數(shù)值的問題。
2）最小二乘法的（代數(shù)）多項式擬合
設擬合公式為： (n次多項式)
已知m個點的值(x1,y1)，(x1,y1)，……，(xm,ym),且mn，結(jié)點偏差的平方和為：
為使 j=0,1,2,…,n
其中：（k=1,2,…,2m+1）
這是一個關于的n+1個線性方程組，求解該方程組→→f(x)
常用二次三項式擬合公式：
例1 介紹
程序流程圖，見P.44圖3-13
要求：看懂該流程圖，該流程圖中采用了高斯消去法解聯(lián)立方法（詳見3.3.4節(jié)），有余力的學生編程上機。
以前做的。
一、 需求分析
1． 本程序是是利用平衡二叉樹實現(xiàn)一個動態(tài)查找表，實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。
2． 初始，平衡二叉樹為空樹，可以按先序輸入平衡二叉樹，以輸入0結(jié)束，中間以回車隔開，創(chuàng)建好二叉樹后，可以對其查找，再對其插入，輸入0結(jié)束插入，再可以對其刪除，輸入0結(jié)束，每次插入或刪除一個結(jié)點后，更新平衡二叉樹的顯示。
3． 本程序以用戶和計算機的對話方式執(zhí)行，根據(jù)計算機終端顯示：“提示信息”下，用戶可由鍵盤輸入要執(zhí)行的操作。
4． 測試數(shù)據(jù)（附后）
二、 概要設計
1． 抽象數(shù)據(jù)類型動態(tài)查找表的定義如下：
ADT DynamicSearchTable{
數(shù)據(jù)結(jié)構(gòu)D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素含有類型相同，可惟一標識數(shù)據(jù)元素的關鍵字。
數(shù)據(jù)關系R：數(shù)據(jù)元素同屬一個集合。
基本操作P：
InitDSTable(DT);
操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。
DestroyDSTable(DT);
初試條件：動態(tài)查找表DT存在。
操作結(jié)果: 銷毀動態(tài)查找表DT。
SearchDSTable(DT,key);
初試條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值。
操作結(jié)果: 若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或表中的位置，否則為“空”。
InsertDSTable(DT,e);
初試條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素。
操作結(jié)果: 若DT中不存在其關鍵字等于e. key的數(shù)據(jù)元素，則插入e到DT。
DeleteDSTable(DT,key);
初試條件：動態(tài)查找表DT存在，key為和關鍵字類型相同的給定值。
操作結(jié)果: 若DT中存在其關鍵字等于key的數(shù)據(jù)元素，則刪除之。
TraverseDSTable(DT,Visit());
初試條件：動態(tài)查找表DT存在，Visit()是結(jié)點操作的應用函數(shù)。
操作結(jié)果: 按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多
一次。一但Visit()失敗，則操作失敗。
}ADT DynamicSearchTable
2． 本程序包含兩個模塊：
Void main(){
Do{
接受命令（根據(jù)提示輸入終點城市和起點城市的序號）；
處理命令；
}while(“命令”=“退出”)；
}
3．本程序只有兩個模塊，調(diào)用關系簡單
主程序模塊
平衡二叉樹的模塊
三、 詳細設計
1． 根據(jù)題目要求和查找的基本特點，其結(jié)點類型
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)；
////////在平衡二叉樹中插入結(jié)點。
int FindAVL(bstree p,int e)；
////////查找平衡二叉樹中是否有結(jié)點e。
bstree DeleteAVL(bstree T,int e)
////////刪除平衡平衡二叉樹的結(jié)點e，并保持平衡二叉樹的性質(zhì)。
int Preordertraverse(bstree T)
////////按先序遍歷平衡二叉樹。
/------------------------************平衡二叉樹的操作的詳細算法
bstree InsertAVL(bstree T, int e)
{
bstree p;
//插入新結(jié)點，樹長高置taller為TRUE
if(!T) {
T=(bstree)malloc(sizeof(BSTnode));
T-data=e;
T-lchild=T-rchild=NULL;
T-bf=EH;
taller=TRUE;
}
else {
//樹中存在和e有相同關鍵字的結(jié)點則不再插入
if(e==T-data){
taller=FALSE;
return NULL;
}
//值小于則繼續(xù)在樹的左子樹中搜索
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: //原本左子樹和右子樹同高，現(xiàn)因左子樹爭高而使樹增高
T-bf=LH;
taller=TRUE;
break;
case RH: //原本右子樹比左子樹高，現(xiàn)在左右子樹等高
T-bf=EH;
taller=FALSE;
break;
}///////switch(T-bf)
}///////if(taller)
}/////if(p)
}///////if(e T-data)
//繼續(xù)在*T的右子樹中搜索
else{
//插入到右子樹且使右子樹長高
p=InsertAVL(T-rchild,e);
if (p){
T-rchild=p;
if(taller) {
switch(T-bf){ //檢查*T的平衡度
case LH: //原本左子樹比右子樹高，現(xiàn)在左右子樹等高
T-bf=EH;
taller=FALSE;
break;
case EH: //原本左子樹和右子樹同高，現(xiàn)因右子樹增高而使樹增高
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)
}////////在右子數(shù)上尋找完
}////////在左右子上完
}///////////刪除完
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("有要查找的節(jié)點\n");
else printf("無要查找的節(jié)點\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的左子樹根結(jié)點
switch(lc-bf) { //檢查*T的左子樹平衡度，并做相應的平衡處理
case LH: //新結(jié)點插入在*T的左孩子的左子樹上，要做單右旋處理
T-bf=lc-bf=EH;
T=R_Rotate(T);
break;
case RH: //新結(jié)點插入在*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的右子樹根結(jié)點
switch(rc-bf) { //檢查*T的右子樹平衡度，并做相應的平衡處理
case RH: //新結(jié)點插入在*T的右孩子的右子樹上，要做單右旋處理
T-bf=rc-bf=EH;
T=L_Rotate(T);
break;
case LH: //新結(jié)點插入在*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){
//刪除結(jié)點
bstree p,q;
e=0;
p=T;
if(!T-rchild) {//右子數(shù)為空需要重接它的左子數(shù)
T=T-lchild;
free(p);
shorter=true;
}
else if(!T-lchild) {//重接它的右子數(shù)
T=T-rchild;
free(p);
shorter=true;
}
else{ //左右子數(shù)均不空
q=T-lchild;
while(q-rchild!=NULL){//轉(zhuǎn)左，然后向右到盡頭
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． 函數(shù)的調(diào)用關系圖
Main
InsertAVL Preordertraverse FindAVL DeleteAVL
四、 調(diào)試分析
1． 在開始對平衡二叉樹的插入后，再做平衡處理時，特別是在做雙向旋轉(zhuǎn)平衡處理后的更新時，費了一些時間；
2． 在做平衡二叉樹的刪除時，當刪除結(jié)點左右孩子均在時，開始直接用左子樹的最大數(shù)代替，然后直接刪除結(jié)點，結(jié)果導致刪除了將要刪除的結(jié)點及其孩子均刪除了，后來將要刪除的結(jié)點用左子樹的最大樹代替后，對左子樹的最大結(jié)點做好標記，然后再做對其做刪除處理。
3． 本程序算法基本簡單，沒有多大困難，就是在分析做雙旋平衡處理的更新時，開始思路有些混亂，后來就好了；
五、 用戶手冊
1. 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為Balanced Tree.exe。
2. 進入演示程序后，按廣度遍歷輸入平衡二叉樹，中間以回車鍵隔開，輸入0為結(jié)束；再輸入要插入的結(jié)點，輸入0結(jié)束，再輸入要查找的結(jié)點，最后可以輸入要刪除的結(jié)點，輸入0結(jié)束
六、 測試結(jié)果
先按廣度遍歷創(chuàng)建平衡二叉樹（亦可一個一個的插入二叉樹的結(jié)點）（50 20 60 10 30 55 70 5 15 25 58 90） ，輸入0結(jié)束，然后可插入結(jié)點（39），其會顯示插入后的二叉樹，輸入0，不再插入；輸入要查找結(jié)點（6），輸入要刪除的結(jié)點（20），其顯示如下：
七、 附錄
Balance Tree.cpp
重慶分公司
重慶分公司
