對於中序遍歷它的後繼如下
()如有右孩子後繼是右孩子的最左下節點
()若無右孩子且是父母的左孩子則後繼就是父母
()若無右孩子且是父母的右孩子則一直上溯到第一個左祖先(定義如前)則後繼就是這個祖先若無這樣的祖先說明已經遍歷完畢
對於後序遍歷它的後繼如下
()若是父母的右孩子則後繼是父母
()若是父母的左孩子且父母無右子樹則後繼是父母
()若是父母的左孩子父母有右子樹則後繼是父母右子樹的最先訪問到的節點(指向父母的右子樹後一直往左若不行的話往右一步一直到葉子)
總結完了想一想我們還能得到哪些提示?經常有一類型題目要求求某個結點的直接前驅其實求前序遍歷的前驅和求後序遍歷的後繼是一樣的只不過把左換成右而已前序遍歷的求後繼和後序遍歷的求前驅中序遍歷的求前驅和中序遍歷求後繼都有這樣的對稱關系因此總結出共性的東西許多題目就可以迎刃而解了問一問讀到這裡的讀者你現在能夠自己在腦子裡面非常輕松地像上面那樣把這個例子裡面的情況都條理清楚地分析總結出來嗎?如果現在還不行到考試之前你必須掌握到這種程度才能得到一個自己很滿意的分數
經過以上的三個過程復習相信讀者對數據結構的掌握就可以到達比較高的水平了如果參加考試獲得一個比較滿意的成績也很有希望了當然達到這一步並不容易大量的練習是真正掌握的必由之路因此我們建議大家能夠下功夫把本書中的題目完整地做一遍然後在學賽網遠程測試平台中做模擬試題能夠真正把這些題都掌握就意味著對數據結構這門課程的理解以及對問題的分析能力都有很大的提高這樣在考場上即使遇到未曾見過的題目也就可以從容應對了
[] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/11241.html