1.本周學習總結
1.思維導圖
2.談談你對樹結構的認識及學習體會。
2.PTA實驗作業
這兩周學習了樹與二叉樹，它與前幾章學習的内容有很大的不同，前幾章學習的線性表，棧與隊列等都是線性的存儲結構，而這一章學習的“樹”是非線性存儲結構的。但是，樹的存儲結構還是可以通過找到元素之間邏輯關系，采用類似線性表的方式，按照結點之間的邏輯關系放到線性存儲中。
2.1題目一：6-4 jmu-ds-表達式樹
輸入一行中綴表達式，轉換一顆二叉表達式樹，并求解.
表達式隻包含+，-，*，/，（，）運算符，操作數隻有一位，且為整數(有興趣同學可以考慮負數小數，兩位數做法)。按照先括号，再乘除，後加減的規則構造二叉樹。
2.1.1設計思路
void InitExpTree(BTree& T, string str) //建二叉表達式樹
{
建立char類型容器
建立BTree類型容器
建立BTree類型變量t1，t2
建立int類型變量i=0
while str[i]不為空
if(str[i])為運算符
判斷兩個運算符的優先關系，分别進行操作
else
建立二叉樹
end while
while st不為空
進行操作
end while
}
double EvaluateExTree(BTree T)//計算表達式樹
{
if T->data不為零
進行相應操作
else
return T->data - '0'
}
2.1.2代碼截圖
2.1.3本題PTA送出清單說明。
2.2 題目2： 還原二叉樹
給定一棵二叉樹的先序周遊序列和中序周遊序列，要求計算該二叉樹的高度。
2.2.1設計思路
建立結構體bt
bt *findTree(char *a, char *b, int length)
{
if(length==0)
return NULL
end if
用遞歸建樹
T->lchild = findTree(a, b + 1, i);
T->rchild = findTree(a + i + 1, b + i + 1, length
}
int GetHeight(bt *T)
{
if(NULL==0)
return 0
end if
else
求左孩子與右孩子的高度
}
2.2.2代碼截圖
2.2.3本題PTA送出清單說明。
編譯錯誤？
在對遞歸的使用不熟，導緻頻繁出錯。
部分正确？
對于一些可能的情況沒有考慮完全，有些也不知道如何解決。
2.3 題目3：二叉樹葉子結點帶權路徑長度和
二叉樹葉子結點的帶權路徑長度指：葉子結點的權重路徑長度。本題要求算出二叉樹所有葉子結點的帶權路徑長度和。
2.3.1設計思路
CreateBT(string str,int i)
if 下标越界||字元為‘#’||樹為空
return NULL；
end if
bt->lchild=遞歸調用建樹函數，下标為2*i；
bt->rchild=遞歸調用建樹函數，下标為2*i+1;
}
void GetWpl(BinTree bt,int h,int &wpl ){ //求長度和
if 樹為空
return ;
end if
if 該結點是葉子節點 then
路徑長wpl=葉子節點的權重*層數；
end if
運用遞歸
查找左孩子的葉子節點，層數+1；
查找右孩子的葉子節點，層數+1；
}
2.3.2代碼截圖
2.3.3本題PTA送出清單說明。
在建立求總長度的函數中，最後判斷條件應該是左指針和右指針都為空，但我寫成左指針或右指針為空，導緻部分正确，還有在一個地方判斷條件寫錯，導緻出現段錯誤。
3.閱讀代碼
3.1 題目：擴充二叉樹
由于先序、中序和後序序列中的任一個都不能唯一确定一棵二叉樹，是以對二叉樹做如下處理，将二叉樹的空結點用·補齊，如圖所示。我們把這樣處理後的二叉樹稱為原二叉樹的擴充二叉樹，擴充二叉樹的先序和後序序列能唯一确定其二叉樹。
現給出擴充二叉樹的先序序列，要求輸出其中序和後序序列。
3.2 解題思路
3.3 代碼截圖
3.4 學習體會
轉載于:https://www.cnblogs.com/2084624983yue/p/10878509.html