二叉樹(shù)的建立與遍歷與二叉樹(shù)的線索化與線索化遍歷-資料下載頁(yè)
2025-06-24 14:18本頁(yè)面
【正文】 f(\t線索二叉樹(shù)\n\n)。 printf (\t建二叉樹(shù) 1 )。 printf (\t\t\t先序遍歷線索化二叉樹(shù) 2 \n)。 printf (\t中序遍歷線索化二叉樹(shù) 3 )。 printf (\t后序遍歷線索化二叉樹(shù) 4 \n)。 printf (\t結(jié)束輸入 0\n)。 printf(\n\t\n\n)。 printf (請(qǐng)輸入您的選擇:)。 scanf (%d,amp。k)。 switch(k) { case 1: printf(\t結(jié)束為 39。39。 \n)。 printf(請(qǐng)輸入樹(shù)的根結(jié)點(diǎn):)。 creat(T)。 T1=copy(T)。system(cls)。 break。 case 2: T=copy(T1)。PreOrderThreading(p,T)。 first(p)。 system(pause)。 system(cls)。 break。 case 3: T=copy(T1)。InOrderThreading(p,T)。 mid(p)。system(pause)。system(cls)。 break。 case 4: T=copy(T1)。backorderThreading(p,T)。 last(p)。system(pause)。 system(cls)。 default: break。 } }while(k!=0)。 printf(\n\t謝謝使用！\n)。}二、實(shí)驗(yàn)報(bào)告：(1).運(yùn)行過(guò)程 ： 先序遍歷線索化二叉樹(shù)結(jié)果為：abdefcg 中序遍歷線索化二叉樹(shù)結(jié)果為：edfbacg 后序遍歷線索化二叉樹(shù)結(jié)果為：efdbaabcgdfe ： 1)創(chuàng)建二叉樹(shù)的實(shí)際結(jié)果如下圖： 2)先序遍歷線索化二叉樹(shù)的實(shí)際結(jié)果如下圖所示：3)中序遍歷線索化二叉樹(shù)的實(shí)際結(jié)果如下所示： 4)后序遍歷線索化二叉樹(shù)的實(shí)際結(jié)果如下圖所示：5)結(jié)束界面如下圖所示：(2).算法分析，首先必須建立二叉樹(shù)，沒(méi)有建立二叉樹(shù)、當(dāng)遍歷時(shí)樹(shù)為空，其次遍歷的過(guò)程必須在線索化的后面進(jìn)行，這樣才能夠體現(xiàn)出本次試驗(yàn)的目的—線索化二叉樹(shù)。遍歷的實(shí)現(xiàn)還需要與其對(duì)應(yīng)的線索化進(jìn)行一 一對(duì)應(yīng)，否則遍歷的結(jié)果是錯(cuò)誤的。,因?yàn)樵诰€索的過(guò)程都必須要申請(qǐng)存儲(chǔ)空間，就是需要多少存儲(chǔ)空間，就申請(qǐng)空間，但是在后面需要復(fù)制本二叉樹(shù)的信息，所以也要求與建立的書(shū)的存儲(chǔ)空間相同，即空間復(fù)雜度為（n）。(3).時(shí)間復(fù)雜度（n），因?yàn)樵谄溥^(guò)程中線索一個(gè)走其下一個(gè)節(jié)點(diǎn)，過(guò)程依次將所有節(jié)點(diǎn)線索完成。，所以遍歷的時(shí)間復(fù)雜度同樣為O（n）。(4).總結(jié)在寫(xiě)本次實(shí)驗(yàn)報(bào)告的過(guò)程中，通過(guò)上機(jī)我對(duì)二叉樹(shù)有了深刻的了解：n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域。利用二叉鏈表中的空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針?lè)Q為線索）。這種加上了線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù)(ThreadedBinaryTree)。對(duì)一棵非線索二叉樹(shù)以某種次序遍歷使其變?yōu)橐豢镁€索二叉樹(shù)的過(guò)程稱(chēng)為二叉樹(shù)的線索化。由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索，而一個(gè)結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的信息只有在遍歷時(shí)才能得到，因此線索化的過(guò)程即為在遍歷過(guò)程中修改空指針的過(guò)程。根據(jù)線索性質(zhì)的不同，線索二叉樹(shù)可分為前序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。寧可累死在路上，也不能閑死在家里！寧可去碰壁，也不能面壁。是狼就要練好牙，是羊就要練好腿。什么是奮斗？奮斗就是每天很難，可一年一年卻越來(lái)越容易。不奮斗就是每天都很容易，可一年一年越來(lái)越難。能干的人，不在情緒上計(jì)較，只在做事上認(rèn)真；無(wú)能的人！不在做事上認(rèn)真，只在情緒上計(jì)較。拼一個(gè)春夏秋冬！贏一個(gè)無(wú)悔人生！早安！—————獻(xiàn)給所有努力的人. 學(xué)習(xí)好幫手
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1