試題資料-程序員面試題

精品試題資料-程序員面試題精選程序員面試題精選（01）一把二元查找樹轉(zhuǎn)變成排序的雙向鏈表題目：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。比如將二元查找樹TOC\o"1-5"\h\z10 / \6 14 /\ /\ 4 812 16轉(zhuǎn)換成雙向鏈表4二6二8二10=12:14=16。分析：本題是微軟的面試題。許多與樹相關(guān)的題目都是用遞歸的思路來解決，本題也不例外。下面我們用兩種不同的遞歸思路來分析。思路一：當我們到達某一結(jié)點打算調(diào)整以該結(jié)點為根結(jié)點的子樹時，先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個排好序的左子鏈表，再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點（左子樹的最大結(jié)點）、當前結(jié)點和右子鏈表的最左結(jié)點（右子樹的最小結(jié)點）。從樹的根結(jié)點起先遞歸調(diào)整全部結(jié)點。思路二：我們可以中序遍歷整棵樹。根據(jù)這個方式遍歷樹，比較小的結(jié)點先訪問。假如我們每訪問一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當前結(jié)點的指針將其鏈接到鏈表的末尾。當全部結(jié)點都訪問過之后，整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。參考代碼：首先我們定義二元查找樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：structBSTreeNode//anodeinthebinarysearchtree{ int mnValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};思路一對應(yīng)的代碼：/////////////////////////////////////////////////////////////////////////Covertasubbinary-search-treeintoasorteddouble-linkedlist//Input:pNode-theheadofthesubtree// asRight-whetherpNodeistherightchildofitsparent//Output:ifasRightistrue,returntheleastnodeinthesub-tree//elsereturnthegreatestnodeinthethesub-tree//sub-tree///////////////////////////////////////////////////////////////////////BSTreeNode*ConvertNode(BSTreeNode*pNode,boolasRight){ if(!pNode) returnNULL