c語言程序設計與項目實踐第18章-資料下載頁

　　

【正文】 10 LastOrderTreversingTree (InBinTreeleftchild)。 //后序遍歷左子樹 11 LastOrderTreversingTree (InBinTreerightchild)。//后序遍歷右子樹 12 printf( %d, InBinTreedata)。//訪問根結點 13 } 14 return。 15 } 二叉樹的簡單操作 ? 4．二叉樹中查找某個結點 對于任何一個非空二叉樹，都可以通過遍歷來查找值為 val的某個結點，若找到，則返回該結點位置，否則，輸出提示信息。使用遞歸算法，代碼如下： 01 struct TreeNode *SearchBinTree(struct TreeNode *InBinTree, int Indata) 02 { 03 struct TreeNode *pTree=NULL。 04 printf(開始處理函數 SearchBinTree()\n)。 05 if(NULL==InBinTree) 06 { 07 printf(輸入參數錯誤，退出 \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。 //返回查找到的結點 21 } 22 if(pTree = SearchBinTree(InBinTreerightchild, Indata)) //遍歷右子樹 23 { 24 return pTree。 //返回查找到的結點 25 } 26 printf(沒有匹配的結點 \n)。 27 return NULL。 28 } 29 } 30 } 二叉樹的簡單操作 ? 5．二叉樹中插入一個結點 向二叉樹中插入結點時應考慮二叉樹的有序性，即在不破壞二叉樹的有序性的前提下插入一個新的結點，若二叉樹為空，則新建一個結點，構成一個僅有一個結點的二叉樹。二叉樹插入結點的基本代碼如下： 01 void InsertBinTree(struct TreeNode *InBinTree, int NewData) 02 { 03 if(NULL= =InBinTree) //樹為空，新建一個根結點 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) //判斷插入結點的位置 13 { 14 InsertBinTree(InBinTreeleftchild,NewData)。 //向左子樹中插入該結點 15 } 16 else 17 { 18 InsertBinTree(InBinTreerightchild,NewData)。 //向右子樹中插入該結點 19 } 20 } 二叉樹的簡單操作 ? 6．二叉樹中刪除一個結點 刪除結點時需要考慮二叉樹的各種可能結構。當二叉樹為空樹時，無法執行刪除操作，輸出提示信息并返回。當二叉樹根結點為要刪除的結點且左子樹為空時，直接刪除根結點，將右子樹作為保留二叉樹。當二叉樹根結點為要刪除的結點且右子樹為空時，直接刪除根結點，將左子樹作為保留二叉樹。當二叉樹僅有一個結點且為要刪除的結點時，刪除該結點，并結束。其他情況，將使用中序遍歷算法進行遞歸查找并刪除找到的結點。 實訓 ——合并兩個有序數組 已知兩個有序數組 array1 = [3 8 10]， array2[3 9 28 101]。將這兩個數組合并成一個有序數組，并將其放在 arrayMerge里。 ? 1．需求分析： 需求 1：分配數組 arrayMerge的大小應不小于兩個數組 array1和array2長度之和。 需求 2：對兩個數組中元素進行比較，依次按大小順序插入數組arrayMerge中。 ? 2．技術應用 將兩個有序數組進行合并，按照有序數組合并的基本思想，第一次比較結果如圖所示，圖中 i為數組 array1的元素指示下標， j為數組array2的元素指示下標， k為數組 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 3k+ ++ +實訓 ——合并兩個有序數組 進行第一次比較之后，將 array2中的值 3插入數組 arrayMerge中，下標 j和 k分別將指向下一個元素，然后重新進行比較，如圖所示。 進行第二次比較之后，將 array1中的值 3插入數組 arrayMerge中，下標 i和 k分別將指向下一個元素。重復上述比較方法，依次比較下去，直到數組 array1遍歷完畢為止，然后將數組 array2的剩余元素依次插入數組 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