周遊二叉樹

二叉樹

定義：每個結點最多有兩個子樹的樹

1

2

3

4

5

6

<code>struct</code>

<code>TreeNode {</code>

<code>     </code><code>int</code>

<code>val;</code>

<code>     </code><code>TreeNode *left;</code>

<code>     </code><code>TreeNode *right;</code>

<code>     </code><code>TreeNode(</code><code>int</code>

<code>x) : val(x), left(NULL), right(NULL) {}</code>

<code> </code><code>};</code>

基本操作：

1. 先序周遊 ：先通路根節點，在通路左子樹，最後通路右子樹

7

8

9

<code>void</code>

<code>PreOrderVisit(TreeNode *root)</code>

<code>{</code>

<code>    </code><code>if</code>

<code>(root == NULL)</code>

<code>        </code><code>return</code><code>;</code>

<code>        </code> 

<code>    </code><code>cout &lt;&lt; root-&gt;val &lt;&lt; endl;</code>

<code>    </code><code>PreOrderVisit(root-&gt;left);</code>

<code>    </code><code>PreOrderVisit(root-&gt;right);</code>

<code>}</code>

2. 中序周遊：先通路左子樹，在通路根節點，最後通路右子樹

3. 後序周遊：先通路左子樹，在通路右子樹，最後通路根節點

可見，所謂的前序，中序，後序周遊僅僅是由通路根節點的順序決定。

4. 層次周遊 ： 一層一層通路

 借助一個隊列，将每一層的結點都存放于隊列中，從隊列中取資料。

 那麼如何記錄一層呢，可以通過記錄每層的個數。

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

<code>LevelVisit(TreeNode *root)</code>

<code>    </code><code>deque&lt;TreeNode*&gt; q;</code>

<code>    </code><code>q.push_back(root);</code>

<code>    </code> 

<code>    </code><code>int</code>

<code>levelNum = 0;</code>

<code>    </code><code>while</code>

<code>(!q.empty())</code>

<code>    </code><code>{</code>

<code>        </code><code>levelNum = q.size();</code>

<code>        </code><code>while</code>

<code>(levelNum &gt; 0)</code>

<code>        </code><code>{</code>

<code>            </code><code>TreeNode *node = q.front();</code>

<code>            </code><code>q.pop_front();</code>

<code>            </code><code>levelNum--;</code>

<code>            </code><code>cout &lt;&lt; node-&gt;val &lt;&lt;</code><code>" "</code><code>;</code>

<code>            </code><code>if</code>

<code>(root-&gt;left != NULL)</code>

<code>                </code><code>q.push_back(root-&gt;left);</code>

<code>(root-&gt;right != NULL)</code>

<code>                </code><code>q.push_back(root-&gt;right);</code>

<code>        </code><code>}</code>

<code>        </code><code>cout &lt;&lt; endl;</code>

<code>    </code><code>}</code>

<code>}　</code>

5. 求樹的高度

<code>int</code> <code>Height(Tree *root)</code>

<code>        </code><code>return</code>

<code>0;</code>

<code>lh = Height(root-&gt;left);</code>

<code>rh = Height(root-&gt;right);</code>

<code>    </code><code>return</code>

<code>max(lh, rh) + 1;</code>

基本操作應該就這些，還是很簡單的。