計(jì)算機(jī)軟件技術(shù)基礎(chǔ)-03 算法和數(shù)據(jù)結(jié)構(gòu)3

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)3、算法和數(shù)據(jù)結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)樹(shù)型結(jié)構(gòu)是一類(lèi)重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。在此類(lèi)結(jié)構(gòu)中，元素之間存在著明顯的分層或嵌套關(guān)系，它們通常以各種形式的鏈表作存儲(chǔ)結(jié)構(gòu)，樹(shù)和二叉樹(shù)是最常用的樹(shù)型結(jié)構(gòu)。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的定義和術(shù)語(yǔ)樹(shù)結(jié)構(gòu)類(lèi)似一棵倒長(zhǎng)的樹(shù)，結(jié)構(gòu)中含有一個(gè)類(lèi)似“樹(shù)根”的結(jié)點(diǎn)和若干類(lèi)似“樹(shù)葉”的結(jié)點(diǎn)以及若干分支節(jié)點(diǎn)樹(shù)的形式化定義：樹(shù)(Tree)是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合T其中有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,T3 ,Tm每一個(gè)集合本身又是一棵樹(shù)，且稱(chēng)為根的子樹(shù)算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的表示，每進(jìn)一層次加一個(gè)括號(hào)，同層之間用逗號(hào)分

2、開(kāi)。例如：(A(B(E,F),C(G),D(H,I,J)，表示下面的樹(shù)算法和數(shù)據(jù)結(jié)構(gòu)度雙親（父）結(jié)點(diǎn)、子結(jié)點(diǎn)葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)（非葉）兄弟、堂兄弟祖先、子孫層數(shù)路徑、路徑長(zhǎng)度結(jié)點(diǎn)的基本術(shù)語(yǔ)算法和數(shù)據(jù)結(jié)構(gòu)度：所有結(jié)點(diǎn)的最大度數(shù)。層數(shù)（深度、高度）：所有結(jié)點(diǎn)的最大層次。路徑長(zhǎng)度：從樹(shù)根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。樹(shù)的基本術(shù)語(yǔ)算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的定義和術(shù)語(yǔ)二叉樹(shù)是另一種重要的樹(shù)形結(jié)構(gòu)，其結(jié)構(gòu)定義為：二叉樹(shù)(Binary Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為根的左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)的區(qū)別樹(shù)和二叉樹(shù)之間最主要

3、的差別是：二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)，即使在結(jié)點(diǎn)只有一棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的性質(zhì)包含n個(gè)(n0)元素的二叉樹(shù)邊數(shù)為n-1；若二叉樹(shù)的高度為h(h=0), 則該二叉樹(shù)最少有h個(gè)結(jié)點(diǎn)，最多有2h-1個(gè)結(jié)點(diǎn)；包含n個(gè)元素的二叉樹(shù)的最大高度為n，最小為log2(n+1)；對(duì)于任意非空的二叉樹(shù)，若葉子結(jié)點(diǎn)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。算法和數(shù)據(jù)結(jié)構(gòu)兩種特殊的二叉樹(shù)滿(mǎn)二叉樹(shù)：高度為h(h=0), 有2h-1個(gè)結(jié)點(diǎn)ABDHCEFGIOJLNKM算法和數(shù)據(jù)結(jié)構(gòu)兩種特殊的二叉樹(shù)完全二叉樹(shù)：除最后一層外，其余層皆滿(mǎn)，且最后一層的結(jié)點(diǎn)集

4、中在左邊ABDHCEFGIJLK算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)可以采用具有多個(gè)指針域的多重鏈表，結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹(shù)的度來(lái)決定但在實(shí)際應(yīng)用中，這種存儲(chǔ)結(jié)構(gòu)并不方便，一般將樹(shù)轉(zhuǎn)化為二叉樹(shù)表示，進(jìn)行處理算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常使用具有2個(gè)指針域的鏈表，LC為左指針域，指向結(jié)點(diǎn)的左子樹(shù)，RC為右指針域，指向結(jié)點(diǎn)的右子樹(shù)。亦可用數(shù)組的下標(biāo)來(lái)模擬指針，即開(kāi)辟三個(gè)一維數(shù)組DATA，LC和RC分別存放結(jié)點(diǎn)的元素及其左、右指針。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示樹(shù)轉(zhuǎn)二叉樹(shù)的方法在樹(shù)(樹(shù)林)與二叉樹(shù)之間有一個(gè)自然的一一對(duì)應(yīng)的關(guān)系，每一棵都能唯一地轉(zhuǎn)換到它所對(duì)應(yīng)的二叉樹(shù)。有一個(gè)自然的方式把樹(shù)轉(zhuǎn)換成

5、對(duì)應(yīng)的二叉樹(shù)：凡是兄弟就用線(xiàn)連接起來(lái)；對(duì)每個(gè)非終端結(jié)點(diǎn)，除其最左孩子外，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)45度。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示樹(shù)轉(zhuǎn)二叉樹(shù)的方法有一個(gè)自然的方式把樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)：凡是兄弟就用線(xiàn)連接起來(lái)；對(duì)每個(gè)非終端結(jié)點(diǎn)，除其最左孩子外，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)45度。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示樹(shù)轉(zhuǎn)二叉樹(shù)的方法有一個(gè)自然的方式把樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)：凡是兄弟就用線(xiàn)連接起來(lái)；對(duì)每個(gè)非終端結(jié)點(diǎn)，除其最左孩子外，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)45度。算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示二叉樹(shù)轉(zhuǎn)樹(shù)的

6、方法二叉樹(shù)轉(zhuǎn)為樹(shù)的方式，基本上是樹(shù)轉(zhuǎn)二叉樹(shù)的逆過(guò)程：如果二叉樹(shù)某結(jié)點(diǎn)是其雙親的左孩子，則把他的右子孫都與其雙親結(jié)點(diǎn)鏈接；刪除二叉樹(shù)中所有結(jié)點(diǎn)與其右孩子的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)整理。ABEHCIFJGDABEHCIFJGD算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示二叉樹(shù)轉(zhuǎn)樹(shù)的方法二叉樹(shù)轉(zhuǎn)為樹(shù)的方式，基本上是樹(shù)轉(zhuǎn)二叉樹(shù)的逆過(guò)程：如果二叉樹(shù)某結(jié)點(diǎn)是其雙親的左孩子，則把他的右子孫都與其雙親結(jié)點(diǎn)鏈接；刪除原二叉樹(shù)中所有結(jié)點(diǎn)與其右孩子的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)整理。ABEHCIFJGDABEHCIFJGD算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)的二叉樹(shù)表示二叉樹(shù)轉(zhuǎn)樹(shù)的方法二叉樹(shù)轉(zhuǎn)為樹(shù)的方式，基本上是樹(shù)轉(zhuǎn)二叉樹(shù)的逆過(guò)程

7、：如果二叉樹(shù)某結(jié)點(diǎn)是其雙親的左孩子，則把他的右子孫都與其雙親結(jié)點(diǎn)鏈接；刪除原二叉樹(shù)中所有結(jié)點(diǎn)與其右孩子的連線(xiàn)；再以根結(jié)點(diǎn)為軸心，對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)整理。ABEHCIFJGDABEHCIFJGD算法和數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)的遍歷對(duì)于樹(shù)形結(jié)構(gòu)的運(yùn)算很多，但最重要、使用最為廣泛的是遍歷。遍歷一個(gè)樹(shù)形結(jié)構(gòu)就是按一定的次序，系統(tǒng)地訪(fǎng)問(wèn)該結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰被訪(fǎng)問(wèn)一次。我們將重點(diǎn)討論二叉樹(shù)的遍歷樹(shù)的遍歷根據(jù)樹(shù)的遞歸定義，有兩種遍歷樹(shù)的方法：先根(次序)遍歷：若樹(shù)中只有一個(gè)根結(jié)點(diǎn)，則訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)；否則，首先訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷每棵子樹(shù)。后根(次序)遍歷：若樹(shù)中只有一個(gè)根結(jié)點(diǎn)，則訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)；

8、否則，首先依次后根遍歷每一棵子樹(shù)，然后訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)。算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遍歷分析二叉樹(shù)的結(jié)構(gòu)特性可知，一棵非空的二叉樹(shù)是由根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)三個(gè)基本部分組成，則遍歷二叉樹(shù)只要依次遍歷這三部分即可。于是，可以有三種遍歷方式：前序遍歷； 中序遍歷； 后序遍歷。算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遍歷ABEHCIFJGD使用前序遍歷，則處理順序?yàn)椋篈BEFCGDHIJ前序遍歷二叉樹(shù)的算法（DLR）為：若二叉樹(shù)不空，則依次進(jìn)行下列操作： a) 訪(fǎng)問(wèn)根結(jié)點(diǎn)； b) 前序遍歷左子樹(shù)； c) 前序遍歷右子樹(shù)。算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遍歷中序遍歷二叉樹(shù)的算法（LDR）為：若二叉樹(shù)不空，則依次進(jìn)行下列操作： a) 中序

9、遍歷左子樹(shù)； b) 訪(fǎng)問(wèn)根結(jié)點(diǎn)； c) 中序遍歷右子樹(shù)。使用中序遍歷，則處理順序?yàn)椋篍FBGCHIJDAABEHCIFJGD算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遍歷后序遍歷二叉樹(shù)的算法（LRD）為：若二叉樹(shù)不空，則依次進(jìn)行下列操作： a) 后序遍歷左子樹(shù)； b) 后序遍歷右子樹(shù)； c) 訪(fǎng)問(wèn)根結(jié)點(diǎn)。使用后序遍歷，則處理順序?yàn)椋篎EGJIHDCBAABEHCIFJGD算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)遍歷的運(yùn)算已知某二叉樹(shù)的前序遍歷序列為: ABDEGCFHIJ，中序遍歷序列為：DBGEAHFIJC，寫(xiě)出該二叉樹(shù)后序遍歷的序列。ABDHCIGJEF算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的實(shí)現(xiàn)二叉樹(shù)的結(jié)構(gòu)定義struct BiTreeNode

10、 int data; / 信息域 TreeNode *lchild; / 左孩子 TreeNode *rchild; / 右孩子;struct BiTree BiTreeNode *root;算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的操作插入左孩子首先根據(jù)制定的結(jié)點(diǎn)值創(chuàng)建新結(jié)點(diǎn)，接著把原來(lái)的左孩子作為新節(jié)點(diǎn)的左孩子，然后把新結(jié)點(diǎn)鏈接到指定的位置。插入右孩子void InsertLeftChild(BiTreeNode *p, int d) BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode); node-data = d; node-rchild =

11、NULL; node-lchild = p-lchild; p-lchild = node; 算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的操作刪除二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始，遞歸刪除左子樹(shù)，再遞歸刪除右子樹(shù)，最后刪除根結(jié)點(diǎn)。void DeleteBiTree(BiTreeNode *root) if (root = NULL) return; DeleteBiTree(root-lchild); DeleteBiTree(root-rchild); free(root); 算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的操作刪除左孩子刪除左孩子也就是把左子樹(shù)全部刪除。刪除右孩子void DeleteLeftChild(BiTreeNode *p) DeleteBiTree(p-lchild); p-lchild = NULL; 算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的應(yīng)用計(jì)算表達(dá)式 5+6*(9-4)+8/2 (5+(6*(9-4)+(8/2)(6*(9-4)+(8/2)(8/2)(6*(9-4)(9-4)算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的應(yīng)用計(jì)算表達(dá)式+54+6*/9-82算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的應(yīng)用計(jì)算表達(dá)式算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的應(yīng)用計(jì)算表達(dá)式算法和數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的應(yīng)用增刪和快速查找 10，6，12，7，-1，37，24，-9，3 用數(shù)組