c語言程序設(shè)計(jì)與項(xiàng)目實(shí)踐第18章-資料下載頁
2025-01-09 01:07本頁面
【正文】 10 LastOrderTreversingTree (InBinTreeleftchild)。 //后序遍歷左子樹 11 LastOrderTreversingTree (InBinTreerightchild)。//后序遍歷右子樹 12 printf( %d, InBinTreedata)。//訪問根結(jié)點(diǎn) 13 } 14 return。 15 } 二叉樹的簡(jiǎn)單操作 ? 4．二叉樹中查找某個(gè)結(jié)點(diǎn) 對(duì)于任何一個(gè)非空二叉樹，都可以通過遍歷來查找值為 val的某個(gè)結(jié)點(diǎn)，若找到，則返回該結(jié)點(diǎn)位置，否則，輸出提示信息。使用遞歸算法，代碼如下： 01 struct TreeNode *SearchBinTree(struct TreeNode *InBinTree, int Indata) 02 { 03 struct TreeNode *pTree=NULL。 04 printf(開始處理函數(shù) SearchBinTree()\n)。 05 if(NULL==InBinTree) 06 { 07 printf(輸入?yún)?shù)錯(cuò)誤，退出 \n)。 08 return NULL。 09 } 10 else 11 { 12 if(InBinTreedata == Indata) 13 { 14 return InBinTree。 15 } 16 else 17 {/* 分別向左右子樹遞歸查找 */ 18 if(pTree = SearchBinTree(InBinTreeleftchild, Indata)) //遍歷左子樹 19 { 20 return pTree。 //返回查找到的結(jié)點(diǎn) 21 } 22 if(pTree = SearchBinTree(InBinTreerightchild, Indata)) //遍歷右子樹 23 { 24 return pTree。 //返回查找到的結(jié)點(diǎn) 25 } 26 printf(沒有匹配的結(jié)點(diǎn) \n)。 27 return NULL。 28 } 29 } 30 } 二叉樹的簡(jiǎn)單操作 ? 5．二叉樹中插入一個(gè)結(jié)點(diǎn) 向二叉樹中插入結(jié)點(diǎn)時(shí)應(yīng)考慮二叉樹的有序性，即在不破壞二叉樹的有序性的前提下插入一個(gè)新的結(jié)點(diǎn)，若二叉樹為空，則新建一個(gè)結(jié)點(diǎn)，構(gòu)成一個(gè)僅有一個(gè)結(jié)點(diǎn)的二叉樹。二叉樹插入結(jié)點(diǎn)的基本代碼如下： 01 void InsertBinTree(struct TreeNode *InBinTree, int NewData) 02 { 03 if(NULL= =InBinTree) //樹為空，新建一個(gè)根結(jié)點(diǎn) 04 { 05 struct TreeNode *pNode=(struct TreeNode *)malloc(sizeof(struct TreeNode))。 06 pNodedata=NewData。 07 pNodeleftchild=NULL。 08 pNoderightchild=NULL。 09 InBinTree=pNode。 10 return。 11 } 12 else if(NewDataInBinTreedata) //判斷插入結(jié)點(diǎn)的位置 13 { 14 InsertBinTree(InBinTreeleftchild,NewData)。 //向左子樹中插入該結(jié)點(diǎn) 15 } 16 else 17 { 18 InsertBinTree(InBinTreerightchild,NewData)。 //向右子樹中插入該結(jié)點(diǎn) 19 } 20 } 二叉樹的簡(jiǎn)單操作 ? 6．二叉樹中刪除一個(gè)結(jié)點(diǎn) 刪除結(jié)點(diǎn)時(shí)需要考慮二叉樹的各種可能結(jié)構(gòu)。當(dāng)二叉樹為空樹時(shí)，無法執(zhí)行刪除操作，輸出提示信息并返回。當(dāng)二叉樹根結(jié)點(diǎn)為要?jiǎng)h除的結(jié)點(diǎn)且左子樹為空時(shí)，直接刪除根結(jié)點(diǎn)，將右子樹作為保留二叉樹。當(dāng)二叉樹根結(jié)點(diǎn)為要?jiǎng)h除的結(jié)點(diǎn)且右子樹為空時(shí)，直接刪除根結(jié)點(diǎn)，將左子樹作為保留二叉樹。當(dāng)二叉樹僅有一個(gè)結(jié)點(diǎn)且為要?jiǎng)h除的結(jié)點(diǎn)時(shí)，刪除該結(jié)點(diǎn)，并結(jié)束。其他情況，將使用中序遍歷算法進(jìn)行遞歸查找并刪除找到的結(jié)點(diǎn)。 實(shí)訓(xùn) ——合并兩個(gè)有序數(shù)組 已知兩個(gè)有序數(shù)組 array1 = [3 8 10]， array2[3 9 28 101]。將這兩個(gè)數(shù)組合并成一個(gè)有序數(shù)組，并將其放在 arrayMerge里。 ? 1．需求分析： 需求 1：分配數(shù)組 arrayMerge的大小應(yīng)不小于兩個(gè)數(shù)組 array1和array2長(zhǎng)度之和。 需求 2：對(duì)兩個(gè)數(shù)組中元素進(jìn)行比較，依次按大小順序插入數(shù)組arrayMerge中。 ? 2．技術(shù)應(yīng)用 將兩個(gè)有序數(shù)組進(jìn)行合并，按照有序數(shù)組合并的基本思想，第一次比較結(jié)果如圖所示，圖中 i為數(shù)組 array1的元素指示下標(biāo)， j為數(shù)組array2的元素指示下標(biāo)， k為數(shù)組 arrayMerge的元素指示下標(biāo)。 i3 8 1 0 9 3 2 8 1 0 1a r r a y 1a r r a y M e r g eja r r a y 2 3k+ ++ +實(shí)訓(xùn) ——合并兩個(gè)有序數(shù)組 進(jìn)行第一次比較之后，將 array2中的值 3插入數(shù)組 arrayMerge中，下標(biāo) j和 k分別將指向下一個(gè)元素，然后重新進(jìn)行比較，如圖所示。 進(jìn)行第二次比較之后，將 array1中的值 3插入數(shù)組 arrayMerge中，下標(biāo) i和 k分別將指向下一個(gè)元素。重復(fù)上述比較方法，依次比較下去，直到數(shù)組 array1遍歷完畢為止，然后將數(shù)組 array2的剩余元素依次插入數(shù)組 arrayMerge中，如圖所示。 i3 8 1 0 9 3 2 8 1 0 1a r r a y 1a r r a y M e r g eja r r a y 2 3k3+ ++ +i3 8 1 0 9 3 2 8 1 0 1a r r a y 1a r r a y M e r g eja r r a y 2 3k3 8 9 1 0 2 8 1 0 1
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1