數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁(yè)
2025-04-30 18:23本頁(yè)面
【正文】 (!visit(pdata)) return ERROR。187。 Push(S,p)。187。 p=plChild。187。 }187。 else187。 { Pop(S,p)。187。 p=prChild。187。 }187。 }187。 return OK。187。 }二叉樹(shù)u 遍歷– 層次遍歷的非遞歸算法187。 通過(guò)隊(duì)列 Q實(shí)現(xiàn)187。 Status levelOrder(Bintree T, visit())187。 {187。 Quere Q。187。 EnQueue(Q,T)。187。 while (!QueueEmpth(Q))187。 { DeQueue(Q,p)。187。 if (!visit(pdata)) return ERROR。187。 if (plChild!=NULL)187。 { EnQueue(Q,plChild)。 }187。 if (prChild!=NULL)187。 { EnQueue(Q,prChild)。 }187。 }187。 }二叉樹(shù)u 遍歷– 先序遍歷187。 訪(fǎng)問(wèn)根結(jié)點(diǎn)，先序遍歷左子樹(shù)，先序遍歷右子樹(shù)– 中序遍歷187。 中序遍歷左子樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)，中序遍歷右子樹(shù)– 后序遍歷187。 后序遍歷左子樹(shù)，后序遍歷右子樹(shù)，訪(fǎng)問(wèn)根結(jié)點(diǎn)– 先序遍歷遞歸算法187。 Status preOrder(binTree T, visit())187。 {187。 if (T)187。 { visit(Tdata)。187。 preOrder(tlchild)。187。 preOrder(trchild)。187。 }187。 }線(xiàn)索二叉樹(shù)u 定義– 二叉樹(shù)鏈表結(jié)構(gòu)中指向左右孩子的指針有時(shí)存在空指針，將左空指針指向該結(jié)點(diǎn)的前驅(qū)，右空指針指向該結(jié)點(diǎn)的后繼，并添加相應(yīng)的標(biāo)志域 ltag， rtag；以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，稱(chēng)為線(xiàn)索鏈表；期中指向前驅(qū)和后繼的指針?lè)Q為線(xiàn)索。– 加上線(xiàn)索的二叉樹(shù)稱(chēng)為線(xiàn)索二叉樹(shù)。– //二叉樹(shù)的二叉線(xiàn)索存儲(chǔ)結(jié)構(gòu)– Typedef enum flag {Child, Thread}。– Typedef struct BinThrNode {– TElemType data。– struct BinThrNode *lchild, *rchild。– flag LTag, RTag。– }BinThrNode, *BinThrTree。算法u 算法的描述– 編寫(xiě)一個(gè)算法時(shí)，可以采用自然語(yǔ)言、流程圖、計(jì)算機(jī)語(yǔ)言或?qū)ｉT(mén)為描述算法而設(shè)計(jì)的語(yǔ)言。u 算法分析及評(píng)價(jià)– 正確性：是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要條件。187。 所設(shè)計(jì)的程序沒(méi)有語(yǔ)法錯(cuò)誤。187。 所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿(mǎn)足要求的結(jié)果。187。 所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿(mǎn)足要求的結(jié)果187。 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿(mǎn)足要求的結(jié)果。達(dá)到第四層含義的正確極為困難，且代價(jià)巨大。– 可讀性：是指一個(gè)算法供人們閱讀和理解的容易程度。相應(yīng)的說(shuō)明文檔是必須的。– 健壯性：是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)和處理能力。– 算法的時(shí)間效率：就是考慮一個(gè)算法運(yùn)行時(shí)所需時(shí)間的多少。– 算法的空間效率：算法的空間復(fù)雜度是指在算法的執(zhí)行過(guò)程中，需要的輔助空間數(shù)量。算法u 算法的描述– 編寫(xiě)一個(gè)算法時(shí)，可以采用自然語(yǔ)言、流程圖、計(jì)算機(jī)語(yǔ)言或?qū)ｉT(mén)為描述算法而設(shè)計(jì)的語(yǔ)言。u 算法分析及評(píng)價(jià)– 正確性：是設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的首要條件。187。 所設(shè)計(jì)的程序沒(méi)有語(yǔ)法錯(cuò)誤。187。 所設(shè)計(jì)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿(mǎn)足要求的結(jié)果。187。 所設(shè)計(jì)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿(mǎn)足要求的結(jié)果187。 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿(mǎn)足要求的結(jié)果。達(dá)到第四層含義的正確極為困難，且代價(jià)巨大。– 可讀性：是指一個(gè)算法供人們閱讀和理解的容易程度。相應(yīng)的說(shuō)明文檔是必須的。– 健壯性：是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)和處理能力。– 算法的時(shí)間效率：就是考慮一個(gè)算法運(yùn)行時(shí)所需時(shí)間的多少。– 算法的空間效率：算法的空間復(fù)雜度是指在算法的執(zhí)行過(guò)程中，需要的輔助空間數(shù)量。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1