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