課程設計說明書課程名稱：數據結構與算法設計題目：AVL樹院系：計算機科學與信息工程學院課程設計任務書設計題目AVL樹學生姓名所在院系計算機科學與信息工程專業、年級、班13軟工1設計要求：設計、實現一個AVL樹程序，為用戶提供三種便利：(1)查找最快；(2)刪除方便；(3)完善樹的平衡。學生應完成的工作：(1)根據課程設計要求，分析思路并完善其功能；(2)根據功能設計并編寫程序段、連接各程序段使之形成一個整體；(3)調試、運行程序進而得到正確的結果；(4)根據實驗設計運行過程，寫出實驗論文并總結實驗教訓。參考文獻閱讀：(1)C語言程序設計（潭浩強第二版，清華大學出版社）；(2)數據結構（吳偉民等C語言版，清華大學出版社）；(3)數據結構實驗教程（高曉兵等，清華大學出版社）；(4）C++數據結構與算法（AdamDrozdek，清華大學出版社）；(5)算法分析與設計（鄭宗漢、鄭曉明，清華大學出版社）。工作計劃：(1)第一周：小組布置設計題目；說明進度安排；小組審題，查閱資料，進行設計前的必要資料準備。(2)第二周：程序編寫、上機調試并上機調試程序、結果分析、撰寫設計報告。任務下達日期：2015年6月日任務完成日期：2015年6月日指導教師（簽名）：學生（簽名）：AVL樹摘要：樹形結構是一類重要的非線性結構。樹由節點與弧組成。與自然界的樹不同，這些樹是倒過來的：根在頂部，葉子在底部。根是一個沒有父節點只有子節點的節點。而葉節點沒有子節點或者子節點是空結構。本程序研究了樹形結構的基礎知識，包括相關定義、操作以及樹在數據結構中的簡單應用問題。主要運用圖示以及相關的算法來研究樹以技術在數據結構中的如干應用問題。在計算機應用的各個領域中都會遇到各種各樣的數據結構，而樹在數據結構中又是一個相當重要的非線性結構，廣泛應用于計算機領域中。在現實生活中存在很多可以用樹形結構描述的實際問題，比如家譜等。關鍵詞：樹、二叉樹、數據結構、樹的應用目錄1、設計背景51.1樹結構的廣泛應用51.2樹結構的需求52、設計方案 52.1總體設計流程52.2部分模塊設計流程63.方案實施73.1二叉樹的實現73.2二叉樹的遍歷84．結果與結論84.1關鍵程序代碼段詳細描述84.2運行結果115.收獲與致謝126.參考文獻137.附件131.設計背景1.1樹結構的廣泛應用鏈表通常可以提供比數據更大的靈活性，但由于鏈表是線性結構，所以很難使用它們來組織對象的分層表示。雖然棧和隊列反映了某些層次，但他們是一維的。為了避免這種限制，我們創建了一個新的數據類型，稱為樹，樹由節點與弧組成。1.2樹結構的需求AVL樹是平衡的二元查找樹。一株平衡的二元查找樹就是指對其每一個節點，其左子樹和右子樹的高度只差不超過1。編寫程序實現AVL樹的判別；并實現AVL樹的ADT，包括其上的基本操作；節點的加入和刪除。BSt和AVL的差別就在平衡性上，所以AVL的操作關鍵要考慮如何在保持二元查找樹定義條件下對二元樹進行平衡化。編寫AVL樹的判別程序，并判別一個人元查找數是否為AVL樹。二元查找樹用其先序遍歷結果表示，如：5,2,1,3,7,8。實現AVL樹的ADT，包括其上的基本操作：節點的加入和刪除，另外包括將一般二元查找樹轉變為AVL樹的操作。2.設計方案2.1總體設計流程主函數流程圖：開始開始選擇功能選擇功能刪 除節 點構建AVL樹刪 除節 點構建AVL樹1 2查 找節 點查 找節 點插 入節 點插 入節 點0結束結束2.2部分模塊設計流程構建AVL樹和插入結點流程圖：開始開始判斷根結點是否存在判斷根結點是否存在否是是否相同是否相同創建結點是 否創建結點插入失敗插入失敗插入插入平衡旋轉處理平衡旋轉處理結束結束查找函數流程圖：開始開始判斷判斷輸出查詢數據輸出查詢數據查找失敗查找失敗結束結束刪除函數流程圖：開始開始查找查找刪除數據刪除失敗刪除數據刪除失敗結束結束3.方案實施3.1二叉樹的實現二叉樹至少可以以如下兩種方式實現：數組和鏈接結構。為了用數組實現樹，節點應聲明為某種結構，其中包含一個信息字段和兩個“指針”字段。指針字段包含了數組單元的下標，數組單元則存儲了該節點的左右子節點（如果有的話）但是，即使數組很靈活（也就是使用向量），這種實現方法也很不方便。要插入新節點，必須知道子節點的位置，而這些位置必須按順序查找。在從樹中刪除一個節點后，必須去除數組中留下的空隙。為此，可以對未用單元使用特殊的標記，但這可能會導致數組中包含大量的未用單元，還可以將元素移動一個位置，但這也要求更新對移動元素的引用。有時數組實現方式比較方便，在討論堆時就使用了這種方式，但通常應使用另一種方法。在新的實現方法，節點是一個類的實例，該類由一個信息成員和兩個指針成員組成。該節點由另一個類（該類將樹作為整體對待）的成員函數使用并操作。因此，BSTNode類的成員聲明為public，因為它們只能由BST類型對象的非公有成員訪問，這樣，信息隱藏的原則依然得到了遵守。將BSTNode的成員設置為public很重要，否則，BST派生的類將無法訪問這些對象。3.2二叉樹的遍歷樹的遍歷是當且僅當訪問樹中每個節點一次的過程。遍歷可以解釋為把所有的節點放在一條線上，或者將樹線性化。遍歷的定義只指定了一個條件：每個節點僅訪問一次，沒有指定這些節點的訪問順序。因此，節點有多少種排列方式，就有多少種遍歷方法。本程序中使用的是深度優先遍歷，則深度優先遍歷包括前、中、后序樹遍歷。4.結果與結論4.1關鍵程序代碼段詳細描述左旋二叉樹代碼思想:只要AVL樹中任一節點的平衡因子小于-1或大于1,樹就需要平衡。而左旋二叉樹的思想是，經歷一輪左旋，需要把n的左孩子接到subl的右孩子上，然后再把調整后的subl接到n的左孩子上，這樣就形成了一個以n為根節點的AVL樹。（右旋二叉樹的思想與左旋雷同，方法對稱）voidavl::LeftSpinTree(LinkNode*n){ inttag=0,flag1=0; right=n; n=right->RightChild; if(right!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) { right->RightChild->perint=right; flag1=1; } n->leftChild=right; if(right->perint!=0) { if(right->perint->data>right->data) { right->perint->leftChild=n; } else { right->perint->RightChild=n; } n->perint=right->perint; } else { n->perint=0; } right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } if(flag1==1) { right->blanceFactor=1; n->blanceFactor=-1; flag1=0; } else { right->blanceFactor=0; n->blanceFactor=0; }}先右后左旋代碼思想：有的時候為了使樹重新平衡，要執行雙重旋轉。這就有了先右后左旋和先左后右旋。這里的先右后左旋的思想為，先經歷一輪右旋，使n的右孩子接到subr的左孩子上，再把subr作為n的右孩子；然后再經歷一輪左旋，讓n的左孩子作為subl的右孩子，再把subl作為n的左孩子。這樣經過一輪先右后左旋，一棵新的平衡樹就建成了。（先左后右旋思想與其雷同，順序顛倒一下）voidavl::RightSpinLeft(LinkNode*n){ inttag=0; right=n; left=right->RightChild; n=left->leftChild; if(right!=first) tag=1; left->leftChild=n->RightChild; if(left->leftChild!=0) left->leftChild->perint=left; n->RightChild=left; left->perint=n; if(n->blanceFactor>=0) left->blanceFactor=0; else left->blanceFactor=1; right->RightChild=n->leftChild; if(right->RightChild!=0) right->RightChild->perint=right; n->leftChild=right; if(right->perint!=0) { if(right->perint->data<right->data) { right->perint->RightChild=n; } else { right->perint->leftChild=n; } n->perint=right->perint; } if(n->blanceFactor==1) right->blanceFactor=-1; else right->blanceFactor=0; right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } n->blanceFactor=0;}4.2運行結果1.建立平衡二叉樹2.插入結點3.刪除結點4.查找結點5.顯示當前樹5.收獲與致謝總的來說,在整個設計的過程中,對二叉樹的知識有了相當程度的了解掌握,基本上學會了對二叉樹的設計和對二叉樹的操作等。在對二叉樹的自學過程中也認識，在學習的過程中要靈活的把所學的知識運用到實踐當中，并且還要鞏固練習和運用，這樣才可以牢牢的記住。試驗也對數據結構的知識進行了復習，尤其是圖及最短路徑等知識點，在對程序不斷的修改和逐步改進提升的過程中，積累了不少經驗，為在以后的學習和實踐應用奠定了一定的基礎。這次課程設計受益非淺，學到了不少知識，同時也認識到自身的不足，需要加強自身訓練，學以致用，學會自我總結，吸取教訓，積累經驗，在學習和實踐中來不斷的提升自己。同時也非常感謝老師對我們的指導，我們也受益匪淺，在其中也學到了很多以前從未領會到的知識，讓我感覺到的程序與算法設計的博大精深。在這次課程設計中也增強了我們對數據結構與算法的喜愛與興趣。6.參考文獻[1]C語言程序設計（潭浩強第二版，清華大學出版社）；[2]數據結構（吳偉民等C語言版，清華大學出版社）；[3]數據結構實驗教程（高曉兵等，清華大學出版社）；[4]C++數據結構與算法（AdamDrozdek，清華大學出版社）；[5]算法分析與設計（鄭宗漢、鄭曉明，清華大學出版社）。7.附件附源程序：//MainAVL.cpp#include"AVL.h"#include<iostream>usingnamespacestd;intmain(){ charselect[100],slt;avlmm; intnum[1000],m=0,n=0,n1=0,total=0,t=0,tag=0,ll=0,ll2=0,f=0; cout<<"AVL樹操作菜單"<<endl; cout<<"***********************************"<<endl; cout<<"1.建立平衡二叉樹"<<endl; cout<<"2.插入結點"<<endl; cout<<"3.刪除結點"<<endl; cout<<"4.查找結點"<<endl; cout<<"5.顯示當前樹"<<endl; cout<<"6.退出"<<endl; cout<<"***********************************"<<endl; cout<<"提示：本系統只能對數字進行相應操作！！！"<<endl<<endl; cout<<"請輸入要執行的功能代號："; while(cin>>select) { if(!strcmp(select,"1")) { if(f==1) { cout<<"已存在一棵非空樹！！若重新建樹會造成已有的數據丟失！確定要重新建立嗎？(y/n)"<<endl; cin>>slt; if(slt=='y'||slt=='Y') f=0; } if(slt=='y'||slt=='Y'||f==0) { f=1; mm.Root=0; cout<<"請輸入要建立平衡二叉樹的結點個數："; cin>>n; n=ll+n; cout<<"請輸入要建立平衡二叉樹的結點"<<endl; for(inti=0;i<n;i++) cin>>num[i]; for(inti=0;i<n;i++) { if(mm.InsertNode(num[i])==-1) { cout<<"結點"<<num[i]<<"已存在！！！"<<endl;n--; continue; } } cout<<"前序遍歷"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍歷"<<endl; mm.Displaym(mm.Root); cout<<endl; tag=0; } } elseif(!strcmp(select,"2")) { cout<<"請輸入要插入的結點個數："<<endl; cin>>n1; n1=ll2+n1; cout<<"請輸入要插入的結點"<<endl; for(inti=0;i<n1;i++) { cin>>num[i]; } for(inti=0;i<n1;i++) { if(mm.InsertNode(num[i])==-1) { cout<<"結點"<<num[i]<<"已存在！！！"; n1--; continue; } } cout<<"前序遍歷"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍歷"<<endl; mm.Displaym(mm.Root); cout<<endl; tag=0; } elseif(!strcmp(select,"3")) { if(tag==0) { total=n+n1; tag=1; } if(total==0) { cout<<"此樹為空樹，請新建一棵樹！！！"<<endl; } else { cout<<"請輸入要刪除的結點值:"; cin>>m; t=mm.DeleteNode(m); if(t==1) total--; else { cout<<"沒有要刪除的結點！！！"<<endl; } if(total!=0) { cout<<"前序遍歷"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍歷"<<endl; mm.Displaym(mm.Root); cout<<endl; } else { cout<<"此樹已刪空!!!!"<<endl; total=0; n=0; n1=0; f=0; } } } elseif(!strcmp(select,"4")) { cout<<"請輸入要查找的結點："<<endl; cin>>m; if(mm.FindNode(m,mm.Root)==1) { cout<<"存在要查的結點"; } else { cout<<"結點"<<m<<"不存在!!"<<endl; } } elseif(!strcmp(select,"5")) { if(mm.Root!=0) { cout<<"前序遍歷"<<endl; mm.Display(mm.Root); cout<<endl<<"中序遍歷"<<endl; mm.Displaym(mm.Root); cout<<endl; } else { cout<<"此樹為空樹！！！"<<endl; f=0; } } elseif(!strcmp(select,"6")) { exit(1); } else { cout<<"輸入的選項非法！請正確輸入！"<<endl; } } system("PAUSE");return0;}//AVL.h#ifndefAVL_H#defineAVL_H#include<iostream>#include<iomanip>usingnamespacestd;classLinkNode;classavl{ friendclassLinkNode;public: avl(); intInsertNode(int);//插入結點函數 intDeleteNode(int);//刪除結點函數 intFindNode(int,LinkNode*);//查找結點函數 voidPushStack(LinkNode*);//結點路徑入棧 LinkNode*PopStack();//結點路徑出棧 voidLeftSpinTree(LinkNode*);//spin旋轉，左旋二叉樹 voidRightSpin(LinkNode*);//先左后右旋轉 voidRightSpinTree(LinkNode*);//右旋二叉數 voidRightSpinLeft(LinkNode*);//先右后左旋 voidDisplay(LinkNode*); voidDisplaym(LinkNode*); LinkNode*Root;//根結點指針 LinkNode*first;private: LinkNode*right;//右旋指針 LinkNode*left;//左旋指針 LinkNode*stack[100];//路徑查找結點存儲棧 inttop;//棧頂指針 intbottom;//棧低指針};classLinkNode{ friendclassavl;public: LinkNode();private: intblanceFactor;//平衡因子 intdata; LinkNode*leftChild; LinkNode*RightChild; LinkNode*perint;//AVL.cpp#include"AVL.h"avl::avl(){ right=0; left=0; Root=0; top=-1; bottom=-1; for(inti=0;i<100;i++) stack[i]=0;}LinkNode::LinkNode(){ perint=0; leftChild=0; RightChild=0; data=0; blanceFactor=0;}voidavl::Display(LinkNode*n){ if(n!=0) { cout<<n->data<<""; Display(n->leftChild); Display(n->RightChild); }}voidavl::Displaym(LinkNode*n){ if(n!=0) { Displaym(n->leftChild); cout<<n->data<<""; Displaym(n->RightChild); }}voidavl::PushStack(LinkNode*n){ bottom=-1; top++; stack[top]=n;}LinkNode*avl::PopStack(){ LinkNode*n; bottom=-1; n=stack[top]; top--; returnn;}intavl::DeleteNode(intn){ LinkNode*pr=0,*p=Root,*q,*ppr; intd,dd=0,tag=0,tag1=0; top=-1;//初始化棧頂指針 while(p!=0)//查找要刪除的結點并記錄查找路徑 { if(n==p->data) break; pr=p; PushStack(pr); if(n<p->data) p=p->leftChild; else p=p->RightChild;}if(p==0)return-1;if(p->leftChild!=0&&p->RightChild!=0) { pr=p; PushStack(pr); q=p->leftChild; while(q->RightChild!=0) { pr=q; PushStack(pr); q=q->RightChild; } p->data=q->data; p=q;}if(p->leftChild!=0)q=p->leftChild;else{ q=p->RightChild;}if(pr==0)Root=q;else{ if(pr->leftChild==p) { pr->leftChild=q; if(pr->leftChild!=0) pr->leftChild->perint=pr; tag=1; } else { pr->RightChild=q; if(pr->RightChild!=0) pr->RightChild->perint=pr; tag1=1; } while(top!=bottom) { pr=PopStack(); if(pr->leftChild!=0||pr->RightChild!=0) { if(pr->RightChild==q) { pr->blanceFactor--; } if(pr->leftChild==q) { pr->blanceFactor++; } } else { if(tag==1) { pr->blanceFactor++; tag=0; } if(tag1==1) { pr->blanceFactor--; tag1=0; } } if(pr->blanceFactor==1||pr->blanceFactor==-1) break; if(pr->blanceFactor!=0) { if(pr->blanceFactor<0) { d=-1; q=pr->leftChild; } else { d=1; q=pr->RightChild; } if(q->blanceFactor==0) { if(d==-1) { RightSpinTree(pr); } else { LeftSpinTree(pr); } break; } if(q->blanceFactor==d) { if(d==-1) RightSpinTree(pr); else LeftSpinTree(pr); } else { if(d==-1) RightSpin(pr); else RightSpinLeft(pr); } } q=pr; } } deletep; return1;}intavl::FindNode(intn,LinkNode*t){ inttag=0; while(t!=0) { if(n<t->data) t=t->leftChild; else { if(n>t->data)t=t->RightChild; else if(n==t->data) { tag=1; break; } } } if(tag!=1) return0; else return1;}intavl::InsertNode(intn){ LinkNode*p=0; LinkNode*pr=0; LinkNode*r=0; intd; p=Root; while(p!=0) { if(n==p->data) { return-1; } pr=p; PushStack(pr);//存儲查找路徑 if(n<p->data)//根據插入至的大小判斷插入位置 p=p->leftChild; else p=p->RightChild; } p=newLinkNode; p->data=n; p->blanceFactor=0; if(Root==0) { Root=p; first=p; p->perint=0; return1; } p->perint=pr; if(n<pr->data) pr->leftChild=p; else pr->RightChild=p; while(top!=bottom) { LinkNode*temp; temp=PopStack(); if(p==temp->leftChild) temp->blanceFactor--; else temp->blanceFactor++; if(temp->blanceFactor==0) { top=-1; break; } if(temp->blanceFactor==1||temp->blanceFactor==-1) { p=temp; } if(temp->blanceFactor==2||temp->blanceFactor==-2) { top=-1;//初始化棧頂指針 d=(temp->blanceFactor<0)?-1:1; if(p->blanceFactor==d) { if(d==-1) { RightSpinTree(temp); } else { LeftSpinTree(temp); } } else { if(d==-1) { RightSpin(temp); } else RightSpinLeft(temp); } break; } }}voidavl::LeftSpinTree(LinkNode*n){ inttag=0,flag1=0; right=n; n=right->RightChild; if(right!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) { right->RightChild->perint=right; flag1=1; } n->leftChild=right; if(right->perint!=0) { if(right->perint->data>right->data) { right->perint->leftChild=n; } else { right->perint->RightChild=n; } n->perint=right->perint; } else { n->perint=0; } right->perint=n; Root=n; if(tag==1) { Root=first; tag=0; } else { first=Root; Root->perint=0; } if(flag1==1) { right->blanceFactor=1; n->blanceFactor=-1; flag1=0; } else { right->blanceFactor=0; n->blanceFactor=0; }}voidavl::RightSpinTree(LinkNode*n){inttag=0,flag1=0;left=n;n=left->leftChild;if(left!=first)tag=1;left->leftChild=n->RightChild;if(left->leftChild!=0){ left->leftChild->perint=left; flag1=1;}n->RightChild=left;if(left->perint!=0){ if(left->perint->data>left->data) { left->perint->leftChild=n; } else { left->perint->RightChild=n; } n->perint=left->perint;}else{ n->perint=0;}left->perint=n;Root=n;if(tag==1){ Root=first; tag=0;}else{ first=Root; Root->perint=0;}if(flag1==1){ left->blanceFactor=-1; n->blanceFactor=1; flag1=0;}else{ n->blanceFactor=0; left->blanceFactor=0;}}voidavl::RightSpin(LinkNode*n){ inttag=0; left=n; right=left->leftChild; n=right->RightChild; if(left!=first) tag=1; right->RightChild=n->leftChild; if(right->RightChild!=0) right->RightChild->perint=right; n->leftChild=right; right->perint=n; if(n->blanceFactor<=0) right->blanceFactor=0; else right->blanceFactor=-1; left->leftChild=n->RightChild; if(left->leftChild!=0) left->leftChild->perint=left; n->RightChild=left; if(left->perint!=0) { if(left->perint->data<left->data) { left->perint->RightChild=n; } else {