求二叉樹根到給定節(jié)點的路徑設(shè)計報告(編輯修改稿)
2025-08-20 11:26 本頁面
【文章內(nèi)容簡介】 n。char d。int p。cout //***請輸入節(jié)點和雙親指針\n。for(int i=0。iPTn。i++){ cindp。 PTnodes[i].data=d。 PTnodes[i].parent=p。}cout 以下就是節(jié)點數(shù)是PTn的二叉樹endl。for(i=0。iPTn。i++) //輸出順序存儲的二叉樹{couti PTnodes[i].data PTnodes[i].parentendl。 }} 求根節(jié)點到給定節(jié)點的路徑void path(PTree *PT , char e) //求根節(jié)點到給定節(jié)點的路徑{ int s[100],top=1。 //建棧 for(int i=0。iPTn。i++) //找到給定節(jié)點并且祖先依次進棧 if(PTnodes[i].data==e)break。 while(i!=PTr){ s[++top]=i。 i=PTnodes[i].parent。 }s[++top]=i。 cout根節(jié)點到e的路徑: 。for(。top0。top) //從根節(jié)點到給定結(jié)點依次輸出coutPTnodes[s[top]].data。coutPTnodes[s[top]].data\n。}//path第六章 結(jié)論、運行結(jié)果： 算法分析：經(jīng)過不斷的上機調(diào)試,源程序運行正確,實現(xiàn)了用雙親表示存儲的方法創(chuàng)建二叉樹并通過path()函數(shù)實現(xiàn)了求根節(jié)點到給定節(jié)點路徑的功能并且實現(xiàn)算法要求的功能,程序中二叉樹有n個節(jié)點，因此創(chuàng)建樹所用時間為O(n)，實現(xiàn)根節(jié)點到指定節(jié)點的路徑問題時所用時間為O（n*n）所以算法的時間復(fù)雜度為O（n*n）.第七章 后記：通過本設(shè)計實驗將數(shù)據(jù)結(jié)構(gòu)中的二叉樹和棧的知
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1