1.本周學習總結

1.思維導圖

2.談談你對樹結構的認識及學習體會

    學完樹之后，最大的感覺就是在處理節點之間的兄弟父親關系的時候真的挺好用的，一目了然。不過，樹令人比較頭疼的就是要用遞歸，大致能懂遞歸怎么用，但是自己具體寫起代碼來就比較懵逼，不知道把遞歸語句放在哪里，對遞歸條件判斷什么的概念也比較模糊。這次的目錄樹大作業，我是自己獨立寫了一些的，但是后面發現遇到了和老師之前說的問題一樣的情況，就是建立起來的樹是散的，并不是一棵完整的樹。在和團隊討論之后，發現需要用指針把彼此之間兄弟的關系建立起來，不過，我們隊這次用的是指針，多次循環找關系，沒有巧妙地運用遞歸，代碼量就增加了不少。
    這次作業，最大的收獲是學會了優先隊列，降序隊列代碼：priority_queue<int>q     升序隊列代碼：priority_queue<int, vector<int>, greater<int> > q。利用已有的庫函數等知識點，可以大大減少編程量，這個也涉及到堆的應用，這個又和容器相關聯，發現容器還真是個好東西，以后要多應用應用！

2.PTA實驗作業

2.1.題目1：表達式樹

輸入要求：輸入一行字符串
輸出要求：輸出結算結果，如遇到除0，提示divide 0 error!
輸入樣例：1+2*3
輸出樣例：7

2.1.1設計思路

建樹初始化函數：
讓葉子節點放數字，其余放運算符。初始化樹的代碼中定義兩個棧，一個存放字符，一個存放數字，str讀入的是算式
- 當str數組不為空字符的時候，進行下面循環
（1）如果str[i]是數字，就讓他為葉子節點，并且進數字棧
（2）如果str[i]是字符
     - 如果棧為空，則直接進棧
     - 否則就和字符棧棧頂元素比較
        - 如果棧頂優先級更大，則出棧兩個節點存于a，b中，將兩個結點以及運算符構建二叉樹，將建好的樹進字符棧
        - 如果棧頂優先級更小，則該字符進棧
        - 如果兩字符優先級相等，則棧頂元素出棧
（3）
- 如果棧中和運算符不為空，則繼續出棧建樹，進行下面循環
     出棧兩個節點存于a，b中，將兩個結點以及運算符構建二叉樹，將建好的樹進字符棧

計算結果的函數：
- 將數字字符轉化為十進制數字，number1,2分別存儲兩葉子節點數字
- 對兩葉子節點的根進行判斷
    - 如果是加號：result+=number1+number2
    - 如果是減號：result+=number1-number2
    - 如果是乘號：result+=number1*number2
    - 如果是除號：
        - 如果number2=0，輸出提示語并且退出程序
        - 如果number2！=0，result+=number1/number2

2.1.2代碼截圖

2.1.3本題PTA提交列表說明

• Q1：第一次出現括號錯誤
• A1：我以為是計算結果個函數出了問題，于是定義了一個result存放結果
• Q2：后面發現錯誤一樣，不是這個問題
• A2：于是我向同學拿代碼過來對比一下，發現在初始化樹那個函數中，我并沒有建立起樹的關系，導致后面計算結果那個函數無法進行樹無法進行遍歷

2.2 題目2：輸出二叉樹每層結點

輸入格式：輸入一行字符串。空節點用#表示。
輸出格式：層次遍歷二叉樹，按照層次輸出所在層及其包含節點，節點間要求,隔開，最后一個節點尾部帶,。若二叉樹為空，則輸出NULL
輸入樣例：ABD#G###CEH###F#I##
輸出樣例：
1:A,
2:B,C,
3:D,E,F,
4:G,H,I,

2.2.1設計思路

    這題我一開始想的是按老師方法，lastNode指針是指向隊列最后一個一個元素的右孩子，可是注意到他可能沒有右孩子或者沒有孩子的情況比較麻煩，于是就放棄這個方法。后來我發現可以用隊列，想的是curNode指針一直往后找，同時他的孩子入隊，找到lastNode就全部出隊，那樣就需要兩個隊列，一個放當前行數，一個放下一層元素，而且雙重循環，代碼閱讀性不好。
    后來看到同學的，可以用一個隊列，curNode孩子節點依次入隊，lastNode為一開始隊列最后的元素，curNode為隊首元素，只要兩指針不相等，元素就依次出隊，相等則將lastNode改為隊列最后的一個元素。只要隊不空，就重復前面過程。

2.2.2代碼截圖

2.2.3本題PTA提交列表說明

比較奇怪的是，vs上分明出現了問題，但是交上去是答案正確，這個問題目前尚未解決，解決之后博主將更新博客說明原因

2.3 題目3：修理牧場

    要將長度為20的木頭鋸成長度為8、7和5的三段，第一次鋸木頭花費20，將木頭鋸成12和8；第二次鋸木頭花費12，將長度為12的木頭鋸成7和5，總花費為32。
如果第一次將木頭鋸成15和5，則第二次鋸木頭花費15，總花費為35（大于32）。
輸入格式：輸入首先給出正整數N≤10000，表示要將木頭鋸成N塊。第二行給出N個正整數（≤50），表示每段木塊的長度。
輸出格式：輸出一個整數，即將木頭鋸成N塊的最少花費。
輸入樣例:
8
4 5 1 2 1 3 1 1
輸出樣例:
49

2.3.1設計思路

    這題其實就是一個哈夫曼樹，要使最后的花費最小，即是要生成一棵哈夫曼樹。可以利用隊列，每次選取最小的兩個節點合成一棵樹，由于這樣要排序與合并，用數組就會比較麻煩。老師提示說可以用優先隊列，其實就是一個堆的問題，放進一些無序的數進去，會自動排好序。
    降序隊列代碼：priority_queue<int>q     升序隊列代碼：priority_queue<int, vector<int>, greater<int> > q
    - 先讓全部元素入隊，優先隊列會自動排好序
    (1)隊大小不為1的情況前兩個元素出隊，相加和存于cost中
    (2)將cost放入隊列中
    (3)定義一個total記錄最后總的費用，total每次自增cost
    (4)隊列大小不為1的情況下，cost重新置為1，再重復步驟(1)
    (5)最后輸出的total即所求的最小花費

2.3.2代碼截圖

2.3.3本題PTA提交列表說明

這題還比較順利，由于老師有說過思路，就未犯什么錯誤

3、閱讀代碼

3.1 題目

本題為天梯賽試題，給定一個龐大家族的家譜，要請你給出最小一輩的名單。
輸入格式：
輸入在第一行給出家族人口總數 N（不超過 100 000 的正整數） —— 簡單起見，我們把家族成員從 1 到 N 編號。隨后第二行給出 N 個編號，其中第 i 個編號對應第 i 位成員的父/母。家譜中輩分最高的老祖宗對應的父/母編號為 -1。一行中的數字間以空格分隔。
輸出格式：
首先輸出最小的輩分（老祖宗的輩分為 1，以下逐級遞增）。然后在第二行按遞增順序輸出輩分最小的成員的編號。編號間以一個空格分隔，行首尾不得有多余空格。
輸入樣例：
9
2 6 5 5 -1 5 6 4 7
輸出樣例：
4
1 9

3.2 解題思路

    家族人數其實就是一棵樹對應的層層父親兄弟孩子之間的關系，輸入的N個節點對應的編號是其父母，由此可建成一棵樹。而題目需要輸出最小輩分即是層次遍歷樹，輸出最后一層節點，也就需要用隊列進行廣度搜索。

3.3 代碼截圖

3.4 學習體會

• 看完這個代碼發現根據父親結點來建樹會比給出先序序列那些邏輯性更強一些，這就需要建樹的時候控制好他們之間的關系
• 利用廣度遍歷找到最小字輩，用到了vector，可很方便實現排序等功能