DS部落格作業05-樹
1.本周學習總結
1.思維導圖
2.學習體會
對于這章，我感覺在課前預習時，看書做課堂派覺得自己挺懂，老師上課講的也大概能了解，但一到做題就不知所措，很迷茫，然後很多題也不會做。難道看書還是太疏忽了？沒記住哪些算法嗎？也許是新知識太多了，還有感覺這兩周老師上課上得挺快得，還沒從樹中走出來，圖就快完了，然後新得一章又來了(-_-)！唉！找時間看書消化消化吧！
2.PTA實驗作業
2.1題目一：6-4 jmu-ds-表達式樹
輸入一行中綴表達式，轉換一顆二叉表達式樹，并求解.
表達式隻包含+，-，*，/，（，）運算符，操作數隻有一位，且為整數(有興趣同學可以考慮負數小數，兩位數做法)。按照先括号，再乘除，後加減的規則構造二叉樹。
如圖所示是"1+(2+3)*2-4/5"代數表達式對應二叉樹，用對應的二叉樹計算表達式的值。 轉換二叉樹如下：
2.1.1設計思路（僞代碼）
void InitExpTree(BTree &T, string str) //建表達式的二叉樹
{
stack<BTree> s; //存放結點的棧
stack<char> op; //存放操作符
op.push('#'); //以#結束
while(str[i]!='\0') //周遊數組str
{
if(!In(str[i]) ) //操作數；
{
建立樹結點，并讓樹進棧；
}
else
{
先判斷操作棧是否空
再比較數組和棧頂的大小關系
根據大小關系做相應的操作
}
}
while(op.top() !='#')
{
周遊棧
根據關系，找左孩子和右孩子，建樹
}
}
double EvaluateExTree(BTree T)//計算表達式樹
{
if (!T->lchild && !T->rchild)
return T->data - '0';
value1 = EvaluateExTree(T->lchild); //遞歸口，讓式子從葉子結點開始計算；
value2 = EvaluateExTree(T->rchild);
switch (T->data) 周遊樹
{
case '+':
case '-':
case '*': 做相應的計算，并傳回式子的結果
case '/':
}
}
2.1.2代碼截圖
2.1.3送出清單及說明
- Q1：段錯誤
- A1：在比較數組和棧頂時忘記判斷棧是否空了。
- Q2：編譯錯誤
- A2：在編譯器上打代碼，不小心把全部代碼複制過去了。
- Q3：答案錯誤
- A3：在對棧做處理時，粗心大意，順序弄反了。
2.2題目二：7-4 jmu-ds-二叉樹葉子結點帶權路徑長度和 (25 分)
二叉樹葉子結點的帶權路徑長度指：葉子結點的權重路徑長度。本題要求算出二叉樹所有葉子結點的帶權路徑長度和。 如下面的二叉樹：
2.2.1設計思路（僞代碼）
BTree CreatTree(string str,int i)
{
定義樹的結構變量bt
當i>len-1或str[i]='#'
傳回NULL
申請結點BTNode
将str[i]的值賦給bt->data
遞歸調用函數CreatTree建構左右孩子
傳回bt
}
void GetWPL(BTree bt,int h,int &wpl)
{
判斷樹是否空，如果樹為空，傳回NULL
如果左右孩子均不為空
wpl+=bt->data-'0'乘以所在層數
遞歸調用函數GetWpl，其中的h+1，得到所在層數
}
2.2.2代碼截圖
2.2.3送出清單及說明
- Q1：編譯錯誤
- A1：沒注意到編譯器的文法改變。
- Q2：段錯誤
- A2：在比較i 和Len 時，以為直接return也可以，後面發現少了NULL不可以。
2.3題目三：7-5 jmu-ds-輸出二叉樹每層節點 (22 分)
~~
層次周遊樹中所有節點。輸出每層樹節點。
樹結構按照樹的先序周遊遞歸建樹，比如先序周遊字元串“ABD#G###CEH###F#I##”#代表空節點。對應樹結構如下圖,
~~~
2.3.1設計思路（僞代碼）
BinTree CreatBT(string str,int &i)
{
當i>len-1或str[i]='#'
傳回NULL
定義樹的結構變量BT
申請結點BTNode
将str[i]的值賦給BT->data
遞歸調用函數CreatTree建構左右孩子
傳回bt
}
void Print(BinTree BT)
{
定義樹的結構變量curNode,lastNode
flag==1,表示該層輸出完成，level表示該結點第幾層
把樹賦給curNode,lastNode，然後讓樹中的結點進棧
周遊棧，對頭賦給curNode，判斷為左孩子還是右孩子或者與lastNode相等，進行相應的指派
用flag控制樹層
最後輸出棧頂
}
2.3.2代碼截圖
2.3.3送出清單及說明
- Q1：部分正确
- A1：對結點層數及該層所有結點的輸出格式混亂
- A2：用flag控制輸出格式
3.閱讀代碼
3.1題目
給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，傳回從右側所能看到的節點值。
示例:
輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:
1 <---
/ \
2 3 <---
\ \
5 4 <---
3.2解題思路
用bfs算法對二叉樹進行層序周遊，儲存每層的最後一個節點
3.3代碼截圖
3.4學習體會
bfs算法為廣度優先搜尋（橫向）。class是将資料與方法封裝，讓行為與資料一緻的程式設計方法。與struct相同而又不同，class的成員預設是private,權限，struct預設是public權限。經百度得知integer是整型的意思，但C++裡隻有int,沒有這個資料類型，但在java裡有，且它是一個類, 是對象類型int的1原始類型。
轉載于:https://www.cnblogs.com/Gejkdj/p/10891682.html