【2019暑假刷题笔记-树的遍历】总结
生活随笔
收集整理的這篇文章主要介紹了
【2019暑假刷题笔记-树的遍历】总结
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
關(guān)于樹這一塊，前期沒有做一個(gè)學(xué)習(xí)的緒論，因?yàn)闀r(shí)間來不及了。在總結(jié)上回顧一下這些題目的一些特點(diǎn)
樹的遍歷的是數(shù)據(jù)結(jié)構(gòu)樹這一塊中的一部分。
樹的遍歷和二叉樹的遍歷本質(zhì)上相同。二叉樹用指針也可以做，但是在考試中用靜態(tài)數(shù)組處理樹更有優(yōu)勢(shì)
樹的遍歷一般的模板是：輸入——遞歸（設(shè)置邊界-遞歸兩步）——輸出
輸入形式的代碼：
for(int i=0;i<presents;i++){scanf("%d %d",&present,&num);for(int j=0;j<num;j++){scanf("%d",&id);node[present].child.push_back(id); //把孩子結(jié)點(diǎn)壓進(jìn)數(shù)組 } }DFS的代碼形式：
void DFS(int index,int depth){node[index].layer=depth;ans[node[index].layer]++;if(node[index].child.size()==0){ //設(shè)置邊界return;}for(int i=0;i<node[index].child.size();i++){ //遞歸int child=node[index].child[i];DFS(child,depth+1);} }結(jié)構(gòu)體的設(shè)置：
//根據(jù)需要設(shè)置結(jié)構(gòu)體 struct Node{int data; //數(shù)值或權(quán)重vector<int> child; //孩子結(jié)點(diǎn)int layer; //層次結(jié)構(gòu) }在輸出的過程中 ，如果要記錄某個(gè)最大值，最小值，要在全局里設(shè)置。如本題：記錄最淺深度，卡了20分鐘，可能不是很熟練，做后面一題的時(shí)候就避免了這個(gè)坑（PS還是要多實(shí)踐，多做）
?
可以用數(shù)組來記錄答案更有優(yōu)勢(shì)，如本題：用數(shù)組記錄答案
?
總結(jié)
以上是生活随笔為你收集整理的【2019暑假刷题笔记-树的遍历】总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【PAT】A1079 Total Sal
- 下一篇： 【二叉查找树BST】二叉查找树的基本操作