博客作業04--樹

1.學習總結(2分)

1.1樹結構思維導圖

1.2 樹結構學習體會

• 樹這一章節比較復雜，知識點繁多，結合了遞歸的知識所以代碼閱讀起來會有障礙，難以理解，所以學起來比較吃力，而且很多經典的算法理解的不是很透徹解決pta上的問題時還要多次翻閱課本回顧代碼，是需要多花時間學習的一個章節。

2.PTA實驗作業（4分）

2.1 題目1：6-2 求二叉樹高度

2.2 設計思路（偽代碼或流程圖）

遞歸遍歷左右子樹
if（左子樹高度大于右子樹高度）返回左子樹高度+1
否則返回右子樹高度+1
當BT=NULL，返回0，遞歸調用結束

2.3 代碼截圖（注意，截圖、截圖、截圖。代碼不要粘貼博客上。不用用···語法去渲染）

2.4 PTA提交列表說明。

2.1 題目2：7-3 jmu-ds-二叉樹層次遍歷

2.2 設計思路（偽代碼或流程圖）

利用函數建樹
樹的左孩子為該節點i的：2i      樹的右孩子為該節點i的：2i+1
左子樹遞歸：bt->lchild =CreateBTree(str,2*i); 
右子樹遞歸：bt->rchild =CreateBTree(str,2*i+1);   
遞歸出口：字符下表i超過字符長度   或  str[i]為#；建立隊列將根節點入棧
while（隊不空）
{取隊頭節點并輸出內存元素隊頭元素出隊if(左孩子不空){左孩子進隊；}if(右孩子不空){右孩子進隊；}}

2.3 代碼截圖（注意，截圖、截圖、截圖。代碼不要粘貼博客上。不用用···語法去渲染）

2.4 PTA提交列表說明。

• 未判斷樹空情況

2.1 題目3：6-4 jmu-ds-表達式樹

2.2 設計思路（偽代碼或流程圖）

定義op為字符串棧，s樹結點棧
while（遍歷字符串）
{if （str[i]不為運算符）則將str【i】賦給樹節點后入棧否則{判斷運算符優先級棧頂優先等級低：將str[i]進棧，i下指優先等級相等：處在棧頂字符，i下指棧頂有限等級高：op棧頂元素出棧賦給節點T，s出棧兩次分別做T節點左右孩子，T后入s棧
}
while（op棧頂元素不為#）{op棧頂元素賦給T的數據域s棧不為空時出棧兩次分別做T節點左右孩子將節點T入s棧}
計算表達式樹{if（左右孩子不為空）則把T->data轉換成數字 利用遞歸將左右孩子轉化為數字存入a，b中判斷節點T的數據域+：返回a+b-：返回a-b*：返回a*b'/'：if（b<1&&b-1）提示錯誤退出

2.3 代碼截圖（注意，截圖、截圖、截圖。代碼不要粘貼博客上。不用用···語法去渲染）

2.4 PTA提交列表說明。

3.截圖本周題目集的PTA最后排名（3分）

3.1 PTA排名

3.2 我的得分：1.5

4. 閱讀代碼（必做，1分）

#include <bits/stdc++.h>
using namespace std;
int main()
{priority_queue<int,vector<int>,greater<int> >l;  int n;cin>>n;for(int i=0;i<n;i++)/// {int t;cin>>t;l.push(t);}int sum=0;   while( q.size() > 1 ) {int first = q.top();q.pop();int second = q.top();q.pop();sum += first + second;q.push( first + second );}printf("%d\n",sum);
}

• （pta修理牧場）這段代碼用了優先隊列，每次遍歷隊列時可以將隊列中的最小和次小值出隊后相加，結果再入隊，不同于普通隊列的操作，能夠高效的解決修理牧場的問題

5. 代碼Git提交記錄截圖