如果覺得code本身就是最好的解釋那可以直接移駕到
前序建立树,中序建立树,后序建立树
去看原版我撿到的版本wwwww 好讀好改~
把多餘的部份刪掉跟改io只花不到我5分鐘就可以拿去交差了(◕ ◡◡ ◕)
(心情不好懶的自己打一份作業交~就套用組語教學法勒)
以下內容是學術不精之人亂打的註解~錯了可不負責
ps.一般的利用堆疊的中序轉後(前)序~可以直接洽良葛葛
簡單來講樹就是由許多節點 (Node) 和節點之間的分支 (Branch) 所構成
指定其中一個特定的節點叫做根 (Root)。
整棵樹就由根開始往下生長,長到末尾不再生長時,我們把這些節點稱為葉子 (Leaf)
~因為樹非常常出現所以詳細就不講了看懂上面那張圖,定義應該就懂了吧
而樹之中如果每個節點的最大分支不超過2就被稱為二元樹
看上圖也知道~如果把節點的左子節點當作根可以看作另一棵二元樹(左子樹),右邊同理
而把根移除就會產生兩顆樹~也就是兩顆樹可以用一個新根來合併
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
再來實作部份~
可以用陣列模擬二元樹不過這問題會想哭~所以請用串列定義節點結構
class TNode
{
public:
char optr; //本身儲存的資料
TNode* left; //左節點的位置
TNode* right;
TNode(char op, TNode* lef, TNode* rgt): optr(op), left(lef), right(rgt) {} //普通的預設建構子囉
TNode(char num): optr(num), left(NULL), right(NULL) {} //左右節點都沒有那就是沒有子節點也就是葉
};
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
接下來開始轉換~首先只凭一种遍历序列建立二叉树树是不唯一
所以看來轉出來的式子也不見得唯一就是了~
先看看平常用堆疊的方法
取出中序式的字元
運算元
直接輸出
左括號
直接進堆疊
運算子
堆疊中運算子優先順序若大於等於讀入的運算子優先順序的話,直接輸出堆疊中的運算子,再將讀入的運算子置入堆疊;
右括號
輸出堆疊中的運算子至左括號。
=======================以上=====================
而此處建樹的方法為
*建新節點的方法為從節點堆疊裡pop出兩個節點當作新建節點的左右節點再把新建節點丟回堆疊
運算元
直接建新葉;
左括號
直接進堆疊
堆疊運算子;
堆疊中運算子優先順序若大於等於讀入的運算子優先順序的話,直接拿堆疊中的運算子建新節點
再將讀入的運算子置入堆疊;
右括號
直接拿堆疊中的運算子建新節點至左括號。
最後節點堆疊剩下的唯一節點就是此二元樹的根
==============================================
稍微比較就發現~原理根本一模一樣wwwwwww(也就是說如果不用前後序兩種都求直接用普通方法還比較快= =)
只是建樹時會用到兩個堆疊
stack<TNode*> dataStack; 跟 stack<char> operStack;
值得注意的是先pop出來的是右子節點~之後才是左子節點
~建好樹只要依照走訪順序不同就是不同的式子了
簡單講
先序遍歷『自己-左邊-右邊』
中序遍歷『左邊-自己-右邊』
後序遍歷『左邊-右邊-自己』
就這樣~看本身節點的順序決定是先中後
由根開始遞迴去輸出所有節點資料~就可以勒
像之前那張圖
前 序 : +-+A*BCD/EF
中 序 : A+B*C-D+E/F
後 序 : ABC*+D_EF/+
自己從根走過一遍就知道了~
~~~~~~~~~~~~~~~~~~~~~不是我打的程式碼~~~~~~~~~~~~~~~~~~~~
刪掉一些用不到的功能就是~基本題就不太計較了
跟我的習慣"差很多"就是~在學校無事可作時自己默打一遍吧
反正概念很簡單~
是說我突然很喜歡組語耶
鼓勵我們複製貼上改一改的教授大好!(造謠)
===========================
是說我被騙去參加請客團了0.0~雖然請定了
不過還是最晚再9號之前開始刷TIOJ吧!免得太難看就糗了
.......我想玩上古啦QQQQQQQQQQ
大概是週期到了~心情極差
之前還幫某個做到一半的傢伙收爛攤子又剛好踩到我的大雷~
就是這樣我才很注重要找誰入夥嘛!!!
無能的傢伙最好完全不認識!凎
那能弄多久~才不到一個晚上
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
既然不是說ACM那當然就是不同的東西啊= =|||
這也好意思遲疑啊~世界很大的
當然不是說程式解題論就是一切
但是自己的程式哪可能出錯都找不出來
只想著別人告訴你測資~DEBUG能力只會越來越爛罷了
至於只會解別人教過的問題~自身毫無思考能力跟自學能力的根本廢物
至少要能再時限內把會動的程式生出來就是一切
一群沒看過系統工程師的傢伙(大誤)
﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍﹍
上面說的好聽~我最近都在沈迷上古卷軸5根本沒打過任何程式wwww
B.A.D事件簿(1):繭墨今天也要吃巧克力 超級好看!獵奇黑暗控推薦!
上述兩者~就是我最近的精神糧食啊!!!!!
<--旁邊的繭墨是真的小說插畫喔!!!超棒的
ps.下篇是組語(好像快教完了)或者java(終於講我欠缺的東西了)