數據結構復習大綱第一章基本概念：1.數據結構的概念：邏輯結構：數據之間的結構關系，是現實中具體關系的抽象。存儲結構：數據結構在計算機內存中的表示。算法：算法是求解問題的操作序列。2?抽象數據類型：抽象數據類型是指一個數學模型以及定義在該模型上的一組操作。算法的5個特征：輸入：0個或多個輸入；輸出：1個或多個輸出；有窮性：算法必須在有限步內結束；確定性：組成算法的操作必須清晰無二義性；可行性：組成算法的操作必須能夠在計算機上實現。4?時間復雜度：一般來說,設算法中基本操作的執行次數是問題規模n的某個函數f(n),算法的時間復雜度記作：T(n)=O(f(n))它表示隨問題規模n的增大，算法執行時間的增長率與f(n)的增長率相同。5?空間復雜度：在本課程中，用執行算法所需的輔助空間的大小作為算法所需空間的度量。設執行算法所需的輔助空間是問題規模n的某個函數g(n),則算法空間復雜度記作：S(n)=O(g(n))注：要求會計算時間復雜度和空間復雜度!

第六章樹與二叉樹二叉樹的基本性質：性質1在二叉樹的第i層上最多有2i-1個結點性質2深度為k的二叉樹最多有2k-1個結點性質3設二叉樹葉子結點數為n0,度為2的結點n2，則n0=n2+1二叉樹的存儲：順序：(滿二叉樹或完全二叉樹的順序存儲)二-二叉樹存貯結構2<>5?G61二叉樹的葩序結構藕二叉樹或蠱全二更脯的順序結構用一組連續的內療單元'按編號順序依撫存儲蠱全二買則的元塞.例如，用…雉4數W[]存放一棵蠱全二叉時，將標號為i的結虛的數據元素存放在分量bt[i]中-存衙位黑隱含r樹中的關系「樹中的關黍足通過完全二戈樹的性廣實現的*例如，bt[6](1=6)的雙親結點標號是k=trtinc(i/2)=3,雙親給點所對應的數組分晝骯[k]2<>5?G60123 4 5 67 m-1(非完全二叉樹的順序結構)非完全二叉樹的順序結構28D10按完全二叉樹的形式補齊二叉樹所缺少的那些結點，對二叉樹結點編號，將二叉樹原有的結點按編號存儲到內存單元龍相應^的位置上*但這種方式對于畸形二叉樹*

28D10二叉鏈表:2二文鏈表*二叉鏈表中每入結點包含三個域：數據域r左抬針域*右指針域typedefstructBiTNode{TElemTypedata;StructBiTNode*lchildh*rchild;}BiTNode,*BiTree;三叉鏈表:3三叉鏈表三叉鏈表中每牛結點包含四個域：數據域、雙親指針域*左指針域"右指針域structBT3Node^lchild,旳xh訂山

*parent;:BT3Nodet*B3Tree;

二叉樹的遍歷①先序：先序遍歷右子樹訪問抿結點A先序遍歷左子樹先序遍歷序列：af先序遍歷右子樹訪問抿結點A先序遍歷左子樹先序遍歷序列：afb即按TLR的順序遍歷先序遍歷(TLR)若二叉樹非空訪問棍結點； ’先序遍歷左子樹： .先序遍歷右子樹；\(例：先序遍歷右圖所示的二丈樹⑴⑵左了樹⑶右子樹即按TLR的順序遍歷中序遍歷左子樹;例*中序(1)中序遍歷左子樹;例*中序(1)②中序:中序遍歷(LT若二叉樹非空C1)中序遍歷左子樹⑵訪問根結點(3)中序遍歷右子樹歷左子樹C2)訪問根結點A(3)中序遍歷右子樹：即按LTR的順序遍歷右子樹中序遍歷序列：D點G.EAC.F

③后序:例：后序遍歷右圖所示的二叉（1）后序遍歷左子樹；即按（③后序:例：后序遍歷右圖所示的二叉（1）后序遍歷左子樹；即按（2）后仔遍歷右子樹：即按LRT的順序遍歷右子樹后序遍歷（LR若二叉樹非空<1）后序遍歷左子樹（2）后序遍歷右子樹<3）訪問根結點（3）訪問根結點A后序遍歷睜列：DPGrE,BrFrC?A④層次:LnitQueue(Q);if(T)EnQueue(Q,T);while(!EmptyQucuc(Q))jDeQueue(Q.p);訪問LnitQueue(Q);if(T)EnQueue(Q,T);while(!EmptyQucuc(Q))jif(p->ktiild)￡nQueue(Qnp->lchi[d);if(p->rchild)EnQueuefQsp->rchild);J}先序、中序遍歷二叉樹的非遞歸算法:先序：中序:中序遍歷的非遞歸算法(算法1)StatusInOrderTraverse(BiTreeT){InitStack(S);Push(S；T);while(!StackEmpty(S)){while(GetTop(S?p)&&p)Push(S,p->khild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);visitfp);Push(S,p->rchild)F}returnOK;中序遍歷的非遞歸算法(算法2)StatusInOrderTraverse(BiTrccT){initStack(S);p=T;while(p||!