圖論基礎
1.什么是“圖”
這里我們說的圖特指圖論中的圖，圖是描述于一組物件的結構，由節點和邊組成
比如，這就是一張（無向）圖：
當然這其中還有很多分類
比如，有向圖（同時它也是一個環）：
2.“樹”
樹是一種特殊的圖，這是樹的嚴謹定義：
任意兩個頂點間有且只有一條路徑的圖
常用名詞的定義：
1. 在樹中有一個特定的節點被稱為根節點，通常在最頂端
2. 一個節點含有的子樹的根節點稱為該節點的子節點
3. 從根開始定義起，根為第1層，根的子節點為第2層，以此類推
4. 樹的高度或深度為樹中節點的最大層
這就是一棵（高度為3的）樹：
特殊的，樹中節點的度不大于2的有序樹我們稱其為二叉樹
如：
3.“樹”的遍歷
在實際程式中，若我們要遍歷一棵樹我們有一下幾種選擇
（為方便表示，我們為每一個節點標上序號）
1. 前序遍歷：首先訪問根結點然后遍歷左子樹，最后遍歷右子樹
在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則回傳
以上我們習慣簡稱：根-左-右
這棵樹的前序遍歷為：A B D E C
2. 中序遍歷：左-根-右（僅存在于二叉樹）
這棵樹的中序遍歷為：D B E A C
3. 后序遍歷：左-右-根
這棵樹的后序遍歷為：D E B C A
4.前/中/后綴運算式
在我們表示一個算式時常使用其中綴運算式，如：
a * ( b + c ) - d
但這樣，在計算機處理時則需要麻煩地用到遞回得到結果
于是，前綴運算式、后綴運算式出現了
我們首先可以把上面的運算式按其運算順序放入一棵樹中：
所謂的前/后綴運算式其實就是簡單地將這棵樹進行前/后序遍歷
我們可以得到前綴運算式：- * a + b c d
后綴運算式：a b c + * d -
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502407.html
標籤：其他