算法大全-面試題-數據結構(收錄)

一單鏈表

單鏈表反轉

找出單鏈表的倒數第個元素

找出單鏈表的中間元素

刪除無頭單鏈表的一個節點

兩個不交叉的有序鏈表的合並

有個二級單鏈表其中每個元素都含有一個指向一個單鏈表的指針寫程序把這個二級鏈表稱一級單鏈表

單鏈表交換任意兩個元素（不包括表頭）

判斷單鏈表是否有環？如何找到環的&#;起始&#;點？如何知道環的長度？

判斷兩個單鏈表是否相交

兩個單鏈表相交計算相交點

用鏈表模擬大整數加法運算

單鏈表排序

刪除單鏈表中重復的元素

首先寫一個單鏈表的C#實現這是我們的基石

public class Link

{

public Link Next;

public string Data;

public Link(Link next string data)

{

thisNext = next;

thisData = data;

}

其中我們需要人為地在單鏈表前面加一個空節點稱其為head例如一個單鏈表是>>如圖所示

對一個單鏈表的遍歷如下所示

static void Main(string[] args)

{

Link head = GenerateLink();

Link curr = head;

while (curr != null)

{

ConsoleWriteLine(currData);

curr = currNext;

}

單鏈表反轉

這道題目有兩種算法既然是要反轉那麼肯定是要破壞原有的數據結構的

算法我們需要額外的兩個變量來存儲當前節點curr的下一個節點next再下一個節點nextnext

public static Link ReverseLink(Link head)

{

Link curr = headNext;

Link next = null;

Link nextnext = null;

//if no elements or only one element exists

if (curr == null || currNext == null)

{

return head;

}

//if more than one element

while (currNext != null)

{

next = currNext; //

nextnext = nextNext; //

nextNext = headNext; //

headNext = next; //

currNext = nextnext; //

}

return head;

}

算法的核心是while循環中的句話

我們發現curr始終指向第個元素

此外出於編程的嚴謹性還要考慮種極特殊的情況沒有元素的單鏈表以及只有一個元素的單鏈表都是不需要反轉的

算法自然是遞歸

如果題目簡化為逆序輸出這個單鏈表那麼遞歸是很簡單的在遞歸函數之後輸出當前元素這樣能確保輸出第N個元素語句永遠在第N+個遞歸函數之後執行也就是說第N個元素永遠在第N+個元素之後輸出最終我們先輸出最後一個元素然後是倒數第個倒數第個直到輸出第個

public static void ReverseLink(Link head)

{

if (headNext != null)

{

ReverseLink(headNext);

ConsoleWriteLine(headNextData);

}

但是現實應用中往往不是要求我們逆序輸出（不損壞原有的單鏈表）而是把這個單鏈表逆序（破壞型）這就要求我們在遞歸的時候還要處理遞歸後的邏輯

首先要把判斷單鏈表有或個元素這部分邏輯獨立出來而不需要在遞歸中每次都比較一次

public static Link ReverseLink(Link head)

{

//if no elements or only one element exists

if (headNext == null || headNextNext == null)

return head;

headNext = ReverseLink(headNext);

return head;

}

我們觀測到

headNext = ReverseLink(headNext);

這句話的意思是為ReverseLink方法生成的逆序鏈表添加一個空表頭

接下來就是遞歸的核心算法ReverseLink了

static Link ReverseLink(Link head)

{

if (headNext == null)

return head;

Link rHead = ReverseLink(headNext);

headNextNext = head;

headNext = null;

return rHead;

}

算法的關鍵就在於遞歸後的兩條語句

headNextNext = head; //

headNext = null; //

啥意思呢？畫個圖表示就是

這樣就得到了一個逆序的單鏈表我們只用到了個額外的變量rHead

找出單鏈表的倒數第個元素

這道題目有兩種算法但無論哪種算法都要考慮單鏈表少於個元素的情況

第種算法建立兩個指針第一個先走步然後第個指針也開始走兩個指針步伐（前進速度）一致

static Link GetLastthOne(Link head)

{

Link first = head;

Link second = head;

for (int i = ; i < ; i++)

{

if (firstNext == null)

throw new Exception(&#;Less than elements&#;);

first = firstNext;

}

while (first != null)

{

first = firstNext;

second = secondNext;

}

return second;

}

第種算法做一個數組arr[]讓我們遍歷單鏈表把第個第個第個……第N個扔到arr[]把第個第個第個……第N+個扔到arr[]把第個第個第個……第N+個扔到arr[]把第個第個第個……第N+個扔到arr[]這樣隨著單鏈表的遍歷結束arr中存儲的就是單鏈表的最後個元素找到最後一個元素對應的arr[i]讓k=(i+)%則arr[k]就是倒數第個元素

static Link GetLastthOneByArray(Link head)

{

Link curr = head;

int i = ;

Link[] arr = new Link[];

while (currNext != null)

{

arr[i] = currNext;

curr = currNext;

i = (i + ) % ;

}

if (arr[i] == null)

throw new Exception(&#;Less than elements&#;);

return arr[i];

}

本題目源代碼下載

推而廣之對倒數第K個元素都能用以上種算法找出來

找出單鏈表的中間元素

算法思想類似於上題還是使用兩個指針first和second只是first每次走一步second每次走兩步

static Link GetMiddleOne(Link head)

{

Link first = head;

Link second = head;

while (first != null && firstNext != null)

{

first = firstNextNext;

second = secondNext;

}

return second;

}

但是這道題目有個地方需要注意就是對於鏈表元素個數為奇數以上算法成立如果鏈表元素個數為偶數那麼在返回second的同時還要返回secondNext也就是下一個元素它倆都算是單鏈表的中間元素

下面是加強版的算法無論奇數偶數一概通殺

static void Main(string[] args)

{

Link head = GenerateLink();

bool isOdd = true;

Link middle = GetMiddleOne(head ref isOdd);

if (isOdd)

{

ConsoleWriteLine(middleData);

}

else

{

ConsoleWriteLine(middleData);

ConsoleWriteLine(middleNextData);

}

ConsoleRead();

}

static Link GetMiddleOne(Link head ref bool isOdd)

{

Link first = head;

Link second = head;

while (first != null && firstNext != null)

{

first = firstNextNext;

second = secondNext;

}

if (first != null)

isOdd = false;

return second;

}

一個單鏈表很長遍歷一遍很慢我們僅知道一個指向某節點的指針curr而我們又想刪除這個節點

這道題目是典型的&#;狸貓換太子&#;如下圖所示

如果不考慮任何特殊情況代碼就行

currData = currNextData;

currNext = currNextNext;

上述代碼由一個地方需要注意就是如果要刪除的是最後一個元素呢？那就只能從頭遍歷一次找到倒數第二個節點了

此外這道題目的一個變身就是將一個環狀單鏈表拆開（即刪除其中一個元素）此時只要使用上面那兩行代碼就可以了不需要考慮表尾

相關問題只給定單鏈表中某個結點p(非空結點)在p前面插入一個結點q

話說交換單鏈表任意兩個節點也可以用交換值的方法但這樣就沒意思了所以才會有第題霸王硬上工的做法

兩個不交叉的有序鏈表的合並

有兩個有序鏈表各自內部是有序的但是兩個鏈表之間是無序的

算法思路當然是循環逐項比較兩個鏈表了如果一個到了頭就不比較了直接加上去

注意對於個元素的Data相等（僅僅是Data相等哦而不是相同的引用）我們可以把它視作前面的Data大於後面的Data從而節省了算法邏輯

static Link MergeTwoLink(Link head Link head)

{

Link head = new Link(null IntMinValue);

Link pre = head;

Link curr = headNext;

Link curr = head;

//compare until one link run to the end

while (currNext != null && currNext != null)

{

if (currNextData < currNextData)

{

curr = new Link(null currNextData);

curr = currNext;

}

else

{

curr = new Link(null currNextData);

curr = currNext;

}

preNext = curr;

pre = preNext;

}

//if head run to the end

while (currNext != null)

{

curr = new Link(null currNextData);

curr = currNext;

preNext = curr;

pre = preNext;

}

//if head run to the end

while (currNext != null)

{

curr = new Link(null currNextData);

curr = currNext;

preNext = curr;

pre = preNext;

}

return head;

}

如果這兩個有序鏈表交叉組成了Y型呢比如說

這時我們需要先找出這個交叉點（圖中是）這個算法參見第題我們這裡直接使用第道題目中的方法GetIntersect

然後局部修改上面的算法只要其中一個鏈表到達了交叉點就直接把另一個鏈表的剩余元素都加上去如下所示

static Link MergeTwoLink(Link head Link head)

{

Link head = new Link(null IntMinValue);

Link pre = head;

Link curr = headNext;

Link intersect = GetIntersect(head head);

Link curr = head;

//compare until one link run to the intersect

while (currNext != intersect && currNext != intersect)

{

if (currNextData < currNextData)

{

curr = new Link(null currNextData);

curr = currNext;

}

else

{

curr = new Link(null currNextData);

curr = currNext;

}

preNext = curr;

pre = preNext;

}

//if head run to the intersect

if (currNext == intersect)

{

while (currNext != null)

{

curr = new Link(null currNextData);

curr = currNext;

preNext = curr;

pre = preNext;

}

//if head run to the intersect

else if (currNext == intersect)

{

while (currNext != null)

{

curr = new Link(null currNextData);

curr = currNext;

preNext = curr;

pre = preNext;

}

return head;

}

有個二級單鏈表其中每個元素都含有一個指向一個單鏈表的指針寫程序把這個二級鏈表展開稱一級單鏈表

這個簡單就是說這個二級單鏈表只包括一些head

public class Link

{

public Link Next;

public int Data;

public Link(Link next int data)

{

thisNext = next;

thisData = data;

}

public class CascadeLink

{

public Link Next;

public CascadeLink NextHead;

public CascadeLink(CascadeLink nextHead Link next)

{

thisNext = next;

thisNextHead = nextHead;

}

下面做一個二級單鏈表GenerateLink和GenerateLink方法在前面都已經介紹過了

public static CascadeLink GenerateCascadeLink()

{

Link head = GenerateLink();

CascadeLink element = new CascadeLink(null head);

CascadeLink element = new CascadeLink(element head);

CascadeLink head = new CascadeLink(element null);

return head;

}

就是說這些單鏈表的表頭headheadheadhead……它們組成了一個二級單鏈表headnull –> head –> head –> head –> head

–>

我們的算法思想是進行兩次遍歷在外層用curr遍歷二級單鏈表head在內層用curr遍歷每個單鏈表

public static Link GenerateNewLink(CascadeLink head)

{

CascadeLink curr = headNextHead;

Link newHead = currNext;

Link curr = newHead;

while (curr != null)

{

currNext = currNextNext;

while (currNext != null)

{

curr = currNext;

}

curr = currNextHead;

}

return newHead;

}

其中currNext = currNextNext; 這句話是關鍵它負責把上一個單鏈表的表尾和下一個單鏈表的非空表頭連接起來

單鏈表交換任意兩個元素（不包括表頭）

先一次遍歷找到這兩個元素curr和curr同時存儲這兩個元素的前驅元素pre和pre

然後大換血

public static Link SwitchPoints(Link head Link p Link q)

{

if (p == head || q == head)

throw new Exception(&#;No exchange with head&#;);

if (p == q)

return head;

//find p and q in the link

Link curr = head;

Link curr = p;

Link curr = q;

Link pre = null;

int count = ;

while (curr != null)

{

if (currNext == p)

{

pre = curr;

count++;

if (count == )

break;

}

else if (currNext == q)

{

pre = curr;

count++;

if (count == )

break;

}

curr = currNext;

}

curr = currNext;

preNext = curr;

currNext = currNext;

preNext = curr;

currNext = curr;

return head;

}

注意特例如果相同元素就沒有必要交換如果有一個是表頭就不交換

判斷單鏈表是否有環？如何找到環的&#;起始&#;點？如何知道環的長度？

算法思想

先分析是否有環為此我們建立兩個指針從header一起向前跑一個步長為一個步長為用while（直到步長的跑到結尾）檢查兩個指針是否相等直到找到為止

static bool JudgeCircleExists(Link head)

{

Link first = head; // step each time

Link second = head; // steps each time

while (secondNext != null && secondNextNext != null)

{

second = secondNextNext;

first = firstNext;

if (second == first)

return true;

}

return false;

}

那又如何知道環的長度呢？

根據上面的算法在返回true的地方也就是個指針相遇處這個位置的節點P肯定位於環上我們從這個節點開始先前走轉了一圈肯定能回來

static int GetCircleLength(Link point)

{

int length = ;

Link curr = point;

while (currNext != point)

{

length++;

curr = currNext;

}

return length;

}

繼續我們的討論如何找到環的&#;起始&#;點呢？

延續上面的思路我們仍然在返回true的地方P計算一下從有環單鏈表的表頭head到P點的距離

static int GetLengthFromHeadToPoint(Link head Link point)

{

int length = ;

Link curr = head;

while (curr != point)

{

length++;

curr = currNext;

}

return length;

}

如果我們把環從P點&#;切開&#;（當然並不是真的切那就破壞原來的數據結構了）那麼問題就轉化為計算兩個相交&#;單鏈表&#;的交點（第題）

一個單鏈表是從P點出發到達P（一個回圈）距離M另一個單鏈表從有環單鏈表的表頭head出發到達P距離N

我們可以參考第題的GetIntersect方法並稍作修改

private static Link FindIntersect(Link head)

{

Link p = null;

//get the point in the circle

bool result = JudgeCircleExists(head ref p);

if (!result) return null;

Link curr = headNext;

Link curr = pNext;

//length from head to p

int M = ;

while (curr != p)

{

M++;

curr = currNext;

}

//circle length

int N = ;

while (curr != p)

{

N++;

curr = currNext;

}

//recover curr & curr

curr = headNext;

curr = pNext;

//make links have the same distance to the intersect

if (M > N)

{

for (int i = ; i < M &#; N; i++)

curr = currNext;

}

else if (M < N)

{

for (int i = ; i < N &#; M; i++)

curr = currNext;

}

//goto the intersect

while (curr != p)

{

if (curr == curr)

{

return curr;

}

curr = currNext;

}

return null;

}

判斷兩個單鏈表是否相交

這道題有多種算法

算法把第一個鏈表逐項存在hashtable中遍歷第個鏈表的每一項如果能在第一個鏈表中找到則必然相交

static bool JudgeIntersectLink(Link head Link head)

{

Hashtable ht = new Hashtable();

Link curr = head;

//store all the elements of link

while (currNext != null)

{

ht[currNext] = stringEmpty;

curr = currNext;

}

//check all the elements in link if exists in Hashtable or not

while (currNext != null)

{

//if exists

if (ht[currNext] != null)

{

return true;

}

curr = currNext;

}

return false;

}

算法把一個鏈表A接在另一個鏈表B的末尾如果有環則必然相交如何判斷有環呢？從A開始遍歷如果能回到A的表頭則肯定有環

注意在返回結果之前要把剛才連接上的兩個鏈表斷開恢復原狀

static bool JudgeIntersectLink(Link head Link head)

{

bool exists = false;

Link curr = head;

//goto the end of the link

while (currNext != null)

{

curr = currNext;

}

//join these two links

currNext = head;

//iterate link

while (currNext != null)

{

if (currNext == head)

{

exists = true;

break;

}

curr = currNext;

}

//recover original status whether exists or not

currNext = null;

return exists;

}

算法如果兩個鏈表的末尾元素相同則必相交

static bool JudgeIntersectLink(Link head Link head)

{

Link curr = head;

//goto the end of the link

while (currNext != null)

{

curr = currNext;

}

//goto the end of the link

while (currNext != null)

{

curr = currNext;

}

if (curr != curr)

return false;

else

return true;

}

兩個單鏈表相交計算相交點

分別遍歷兩個單鏈表計算出它們的長度M和N假設M比N大則長度M的鏈表先前進MN然後兩個鏈表同時以步長前進前進的同時比較當前的元素如果相同則必是交點

public static Link GetIntersect(Link head Link head)

{

Link curr = head;

int M = N = ;

//goto the end of the link

while (currNext != null)

{

curr = currNext;

M++;

}

//goto the end of the link

while (currNext != null)

{

curr = currNext;

N++;

}

//return to the begining of the link

curr = head;

if (M > N)

{

for (int i = ; i < M &#; N; i++)

curr = currNext;

}

else if (M < N)

{

for (int i = ; i < N &#; M; i++)

curr = currNext;

}

while (currNext != null)

{

if (curr == curr)

{

return curr;

}

curr = currNext;

}

return null;

}

用鏈表模擬大整數加法運算

例如>>>NULL + >NULL =>

>>>>NULL

肯定是使用遞歸啦不然沒辦法解決進位+問題因為這時候要讓前面的節點加而我們的單鏈表是永遠指向前的

此外對於+=新得到的值的位數（位）比原來的兩個值（個位個位）都多所以我們將表頭的值設置為如果多出一位來就暫時存放到表頭遞歸結束後如果表頭為就在新的鏈表外再加一個新的表頭

//head length > head so M > N

public static int Add(Link head Link head ref Link newHead int M int N)

{

// goto the end

if (head == null)

return ;

int temp = ;

int result = ;

newHead = new Link(null );

if (M > N)

{

result = Add(headNext head ref newHeadNext M &#; N);

temp = headData + result;

newHeadData = temp % ;

return temp >=

: ;

}

else // M == N

{

result = Add(headNext headNext ref newHeadNext M &#; N &#; );

temp = headData + headData + +result;

newHeadData = temp % ;

return temp >=

: ;

}

這裡假設head比head長而且MN分別是head和head的長度

單鏈表排序

無外乎是冒泡選擇插入等排序方法關鍵是交換算法需要額外考慮第題我編寫了一個交換算法在本題的排序過程中我們可以在外層和內層循環裡面捕捉到pre和pre然後進行交換而無需每次交換又要遍歷一次單鏈表

在實踐中我發現冒泡排序和選擇排序都要求內層循環從鏈表的末尾向前走這明顯是不合時宜的

所以我最終選擇了插入排序算法如下所示

先給出基於數組的算法

代碼

static int[]

InsertSort(int[] arr)

{

for(int i=; i<arrLength;i++)

{

for(int j =i; (j>)&&arr[j]<arr[j];j&#;)

{

arr[j]=arr[j]^arr[j];

}

return arr;

}

仿照上面的思想我們來編寫基於Link的算法

public static Link SortLink(Link head)

{

Link pre = head;

Link pre = headNext;

Link min = null;

for (Link curr = headNext; curr != null; curr = minNext)

{

if (currNext == null)

break;

min = curr;

for (Link curr = currNext; curr != null; curr = currNext)

{

//swap curr and curr

if (currData < currData)

{

min = curr;

curr = curr;

curr = min;

preNext = curr;

currNext = currNext;

currNext = pre;

//if exchange element n and n no need to add reference from pre to curr because they are the same one

if (pre != curr)

preNext = curr;

}

pre = curr;

}

pre = min;

pre = minNext;

}

return head;

}

值得注意的是很多人的算法不能交換相鄰兩個元素這是因為pre和curr是相等的如果此時還執行preNext = curr; 會造成一個自己引用自己的環

交換指針很是麻煩而且效率也不高需要經常排序的東西最好不要用鏈表來實現還是數組好一些

刪除單鏈表中重復的元素

用Hashtable輔助遍歷一遍單鏈表就能搞定

實踐中發現curr從表頭開始每次判斷下一個元素currNetx是否重復如果重復直接使用currNext = currNextNext; 就可以刪除重復元素——這是最好的算法唯一的例外就是表尾所以到達表尾就break跳出while循環

public static Link DeleteDuplexElements(Link head)

{

Hashtable ht = new Hashtable();

Link curr = head;

while (curr != null)

{

if (currNext == null)

{

break;

}

if (ht[currNextData] != null)

{

currNext = currNextNext;

}

else

{

ht[currNextData] = &#;&#;;

}

curr = currNext;

}

return head;

}

結語

單鏈表只有一個向前指針Next所以要使用個額外變量來存儲當前元素的前一個或後一個指針

盡量用while循環而不要用for循環來進行遍歷

哇塞我就是不用指針照樣能&#;修改地址&#;達到和C++同樣的效果雖然很煩~

遍歷的時候不要在while循環中head=headNext;這樣會改變原先的數據結構我們要這麼寫Link curr=head;然後curr=currNext;

有時我們需要臨時把環切開有時我們需要臨時把單鏈表首尾相連成一個環

究竟是玩curr還是currNext根據不同題目而各有用武之地沒有定論不必強求

二棧和隊列

設計含min函數的棧要求minpush和pop的時間復雜度都是o()

設計含min函數的棧的另解

用兩個棧實現隊列

用兩個隊列實現棧

棧的pushpop序列是否一致

遞歸反轉一個棧要求不得重新申請一個同樣的棧空間復雜度o()

給棧排個序

如何用一個數組實現兩個棧

如何用一個數組實現三個棧

設計含min函數的棧要求minpush和pop的時間復雜度都是o()

算法思想需要設計一個輔助棧用來存儲當前棧中元素的最小值網上有人說存儲當前棧中元素的最小值的所在位置雖然能節省空間這其實是不對的因為我在調用Min函數的時候只能得到位置還要對存儲元素的棧不斷的pop才能得到最小值——時間復雜度o()

所以還是在輔助棧中存儲元素吧

此外還要額外注意Push操作第一個元素不用比較自動成為最小值入棧其它元素每次都要和棧頂元素比較小的那個放到棧頂

public class NewStack

{

private Stack dataStack;

private Stack mindataStack;

public NewStack()

{

dataStack = new Stack();

mindataStack = new Stack();

}

public void Push(int element)

{

dataStackPush(element);

if (mindataStackCount == )

mindataStackPush(element);

else if (element <= (int)mindataStackPeek())

mindataStackPush(element);

else //(element > mindataStackPeek)

mindataStackPush(mindataStackPeek());

}

public int Pop()

{

if (dataStackCount == )

throw new Exception(&#;The stack is empty&#;);

mindataStackPop();

return (int)dataStackPop();

}

public int Min()

{

if (dataStackCount == )

throw new Exception(&#;The stack is empty&#;);

return (int)mindataStackPeek();

}

設計含min函數的棧的另解

話說和青菜臉呆久了就沾染了上海小市民意識再加上原本我就很摳門兒於是對於上一題目我把一個棧當成兩個用就是說每次push先入站當前元素然後入棧當前棧中最小元素pop則每次彈出個元素

算法代碼如下所示（這裡最小元素位於當前元素之上為了下次比較方便）

public class NewStack

{

private Stack stack;

public NewStack()

{

stack = new Stack();

}

public void Push(int element)

{

if (stackCount == )

{

stackPush(element);

}

else if (element <= (int)stackPeek())

{

stackPush(element);

}

else //(element > stackPeek)

{

object min = stackPeek();

stackPush(element);

stackPush(min);

}

public int Pop()

{

if (stackCount == )

throw new Exception(&#;The stack is empty&#;);

stackPop();

return (int)stackPop();

}

public int Min()

{

if (stackCount == )

throw new Exception(&#;The stack is empty&#;);

return (int)stackPeek();

}

之所以說我這個算法比較叩門是因為我只使用了一個棧空間復雜度o(N)節省了一半的空間（算法的空間復雜度o(N)）

用兩個棧實現隊列

實現隊列就要實現它的個方法Enqueue（入隊）Dequeue（出隊）和Peek（隊頭）

）stack存的是每次進來的元素所以Enqueue就是把進來的元素push到stack中

）而對於Dequeue一開始stack是空的所以我們把stack中的元素全都pop到stack中這樣stack的棧頂就是隊頭只要stack不為空那麼每次出隊就相當於stack的pop

）接下來每入隊一個元素仍然push到stack中每出隊一個元素如果stack不為空就從stack中pop一個元素如果stack為空就重復上面的操作——把stack中的元素全都pop到stack中

）Peek操作類似於Dequeue只是不需要出隊所以我們調用stack的Peek操作當然如果stack為空就把stack中的元素全都pop到stack中

）注意邊界的處理如果stack和stack都為空才等於隊列為空此時不能進行Peek和Dequeue操作

按照上述分析算法實現如下

public class NewQueue

{

private Stack stack;

public NewQueue()

{

stack = new Stack();

}

public void Enqueue(int element)

{

stackPush(element);

}

public int Dequeue()

{

if (stackCount == )

{

if (stackCount == )

throw new Exception(&#;The queue is empty&#;);

else

while (stackCount > )

stackPush(stackPop());

}

return (int)stackPop();

}

public int Peek()

{

if (stackCount == )

{

if (stackCount == )

throw new Exception(&#;The queue is empty&#;);

else

while (stackCount > )

stackPush(stackPop());

}

return (int)stackPeek();

}

用兩個隊列實現棧

這個嘛就要queue和queue輪流存儲數據了這個&#;輪流&#;發生在Pop和Peek的時候假設此時我們把所有數據存在queue中（此時queue為空）我們把queue的n個元素放到queue中queue中最後一個元素就是我們想要pop的元素此時queue存有n個元素（queue為空）

至於Peek則是每次轉移n個數據再轉移最後一個元素的時候將其計下並返回

那麼Push的操作則需要判斷當前queue和queue哪個為空將新元素放到不為空的隊列中

public class NewStack

{

private Queue queue;

public NewStack()

{

queue = new Queue();

}

public void Push(int element)

{

if (queueCount == )

queueEnqueue(element);

else

queueEnqueue(element);

}

public int Pop()

{

if (queueCount == && queueCount == )

throw new Exception(&#;The stack is empty&#;);

if (queueCount > )

{

while (queueCount > )

{

queueEnqueue(queueDequeue());

}

//還剩一個

return (int)queueDequeue();

}

else //queueCount >

{

while (queueCount > )

{

queueEnqueue(queueDequeue());

}

//還剩一個

return (int)queueDequeue();

}

public int Peek()

{

if (queueCount == && queueCount == )

throw new Exception(&#;The stack is empty&#;);

int result = ;

if (queueCount > )

{

while (queueCount > )

{

queueEnqueue(queueDequeue());

}

//還剩一個

result = (int)queueDequeue();

queueEnqueue(result);

}

else //queueCount >

{

while (queueCount > )

{

queueEnqueue(queueDequeue());

}

//還剩一個

result = (int)queueDequeue();

queueEnqueue(result);

}

return result;

}

棧的pushpop序列是否一致

輸入兩個整數序列其中一個序列表示棧的push順序判斷另一個序列有沒有可能是對應的pop順序為了簡單起見我們假設push序列的任意兩個整數都是不相等的

比如輸入的push序列是那麼就有可能是一個pop系列因為可以有如下的push和pop序列push push push push poppush poppoppoppop這樣得到的pop序列就是但序列就不可能是push序列的pop序列

網上的若干算法都太復雜了現提出包氏算法如下

先for循環把arr中的元素入棧並在每次遍歷時檢索arr中可以pop的元素如果循環結束而stack中還有元素就說明arr序列不是pop序列

static bool

JudgeSequenceIsPossible(int[] arrint[] arr)

{

Stack stack = new Stack();

for (int i = j = ; i < arrLength; i++)

{

stackPush(arr[i]);

while(stackCount > && (int)stackPeek() == arr[j])

{

stackPop();

j++;

}

return stackCount == ;

}

遞歸反轉一個棧要求不得重新申請一個同樣的棧空間復雜度o()

算法思想漢諾塔的思想非常復雜玩過九連環的人都想得通的

static void ReverseStack(ref Stack stack)

{

if (stackCount == )

return;

object top = stackPop();

ReverseStack(ref stack);

if (stackCount == )

{

stackPush(top);

return;

}

object top = stackPop();

ReverseStack(ref stack);

stackPush(top);

ReverseStack(ref stack);

stackPush(top);

}

給棧排個序

本題目是上一題目的延伸

static void Sort(ref Stack stack)

{

if (stackCount == )

return;

object top = stackPop();

Sort(ref stack);

if (stackCount == )

{

stackPush(top);

return;

}

object top = stackPop();

if ((int)top > (int)top)

{

stackPush(top);

Sort(ref stack);

stackPush(top);

}

else

{

stackPush(top);

Sort(ref stack);

stackPush(top);

}

如何用一個數組實現兩個棧

繼續我所提倡的摳門兒思想也不枉我和青菜臉相交一場

網上流傳著兩種方法

方法

采用交叉索引的方法

一號棧所占數組索引為 &#;&#;(K*)

二號棧所占數組索引為 &#;&#;(K* + )

算法實現如下

public class NewStack

{

object[] arr;

int top;

public NewStack(int capticy)

{

arr = new object[capticy];

top = ;

}

public void Push(int type object element)

{

if (type == )

{

if (top + >= arrLength)

throw new Exception(&#;The stack is full&#;);

else

{

top += ;

arr[top] = element;

}

else //type==

{

if (top + >= arrLength)

throw new Exception(&#;The stack is full&#;);

else

{

top += ;

arr[top] = element;

}

public object Pop(int type)

{

object obj = null;

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

else

{

obj = arr[top];

arr[top] = null;

top = ;

}

else //type ==

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

else

{

obj = arr[top];

arr[top] = null;

top = ;

}

return obj;

}

public object Peek(int type)

{

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

return arr[top];

}

else //type ==

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

return arr[top];

}

方法

第一個棧A從最左向右增長

第二個棧B從最右向左增長

代碼實現如下

public class NewStack

{

object[] arr;

int top;

public NewStack(int capticy)

{

arr = new object[capticy];

top = ;

top = capticy;

}

public void Push(int type object element)

{

if (top == top)

throw new Exception(&#;The stack is full&#;);

if (type == )

{

arr[top] = element;

top++;

}

else //type==

{

top&#;;

arr[top] = element;

}

public object Pop(int type)

{

object obj = null;

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

else

{

top&#;;

obj = arr[top];

arr[top] = null;

}

else //type ==

{

if (top == arrLength)

throw new Exception(&#;The stack is empty&#;);

else

{

obj = arr[top];

arr[top] = null;

top++;

}

return obj;

}

public object Peek(int type)

{

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

return arr[top ];

}

else //type ==

{

if (top == arrLength)

throw new Exception(&#;The stack is empty&#;);

return arr[top];

}

綜合比較上述兩種算法我們發現算法實現的兩個棧每個都只有n/個空間大小而算法實現的兩個棧如果其中一個很小另一個則可以很大它們的和為常數n

如何用一個數組實現三個棧

最後讓我們把摳門兒進行到底相信看完本文你已經從物質和精神上都升級為一個摳門兒主義者

如果還使用交叉索引的辦法每個棧都只有N/個空間

讓我們只好使用上個題目的第個方法不過這只能容納個棧我們還需要一個位置存放第個棧不如考慮數組中間的位置——第個棧的增長規律可以如下

第個入棧C的元素進mid處

第個入棧C的元素進mid+處

第個入棧C的元素進mid處

第個入棧C的元素進mid+處

這個方法的好處是每個棧都有接近N/個空間

public class NewStack

{

object[] arr;

int top;

int top_left;

int top_right;

bool isLeft;

public NewStack(int capticy)

{

arr = new object[capticy];

top = ;

top = capticy;

isLeft = true;

top_left = capticy / ;

top_right = top_left + ;

}

public void Push(int type object element)

{

if (type == )

{

if (top == top_left + )

throw new Exception(&#;The stack is full&#;);

arr[top] = element;

top++;

}

else if (type == )

{

if (top == top_right)

throw new Exception(&#;The stack is full&#;);

top&#;;

arr[top] = element;

}

else //type==

{

if (isLeft)

{

if (top == top_left + )

throw new Exception(&#;The stack is full&#;);

arr[top_left] = element;

top_left&#;;

}

else

{

if (top == top_right)

throw new Exception(&#;The stack is full&#;);

arr[top_right] = element;

top_right++;

}

isLeft = !isLeft;

}

public object Pop(int type)

{

object obj = null;

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

else

{

top&#;;

obj = arr[top];

arr[top] = null;

}

else if (type == )

{

if (top == arrLength)

throw new Exception(&#;The stack is empty&#;);

else

{

obj = arr[top];

arr[top] = null;

top++;

}

else //type==

{

if (top_right == top_left + )

throw new Exception(&#;The stack is empty&#;);

if (isLeft)

{

top_left++;

obj = arr[top_left];

arr[top_left] = null;

}

else

{

top_right&#;;

obj = arr[top_right];

arr[top_right] = null;

}

isLeft = !isLeft;

}

return obj;

}

public object Peek(int type)

{

if (type == )

{

if (top == )

throw new Exception(&#;The stack is empty&#;);

return arr[top ];

}

else if (type == )

{

if (top == arrLength)

throw new Exception(&#;The stack is empty&#;);

return arr[top];

}

else //type==

{

if (top_right == top_left + )

throw new Exception(&#;The stack is empty&#;);

if (isLeft)

return arr[top_left + ];

else

return arr[top_right ];

}

三二叉樹

二叉樹三種周游（traversal）方式

怎樣從頂部開始逐層打印二叉樹結點數據

如何判斷一棵二叉樹是否是平衡二叉樹

設計一個算法找出二叉樹上任意兩個節點的最近共同父結點復雜度如果是O(n)則不得分

如何不用遞歸實現二叉樹的前序/後序/中序遍歷？

在二叉樹中找出和為某一值的所有路徑

怎樣編寫一個程序把一個有序整數數組放到二叉樹中？

判斷整數序列是不是二叉搜索樹的後序遍歷結果

求二叉樹的鏡像

一棵排序二叉樹（即二叉搜索樹BST）令 f=(最大值+最小值)/設計一個算法找出距離f值最近大於f值的結點復雜度如果是O(n)則不得分

把二叉搜索樹轉變成排序的雙向鏈表

首先寫一個二叉樹的C#實現這是我們的基石

public class BinNode

{

public int Element;

public BinNode Left;

public BinNode Right;

public BinNode(int element BinNode left BinNode right)

{

thisElement = element;

thisLeft = left;

thisRight = right;

}

public bool IsLeaf()

{

return thisLeft == null && thisRight == null;

}

二叉樹三種周游（traversal）方式

）前序周游（preorder）節點 –> 子節點Left（包括其子樹） –> 子節點Right（包括其子樹）

static void PreOrder(BinNode root)

{

if (root == null)

return;

//visit current node

ConsoleWriteLine(rootElement);

PreOrder(rootLeft);

PreOrder(rootRight);

}

）後序周游（postorder）子節點Left（包括其子樹） –> 子節點Right（包括其子樹） –> 節點

static void PostOrder(BinNode root)

{

if (root == null)

return;

PostOrder(rootLeft);

PostOrder(rootRight);

//visit current node

ConsoleWriteLine(rootElement);

}

）中序周游（inorder）子節點Left（包括其子樹） –> 節點 –> 子節點Right（包括其子樹）

static void InOrder(BinNode root)

{

if (root == null)

return;

InOrder(rootLeft);

//visit current node

ConsoleWriteLine(rootElement);

InOrder(rootRight);

}

我們發現三種周游的code實現僅僅是訪問當前節點的這條語句所在位置不同而已

怎樣從頂部開始逐層打印二叉樹結點數據

有種算法

算法基於Queue來實現也就是廣度優先搜索（BFS）的思想

static void PrintTree(BinNode root)

{

if (root == null) return;

BinNode tmp = null;

Queue queue = new Queue();

queueEnqueue(root);

while (queueCount > )

{

tmp = (BinNode)queueDequeue();

ConsoleWriteLine(tmpElement);

if (tmpLeft != null)

queueEnqueue(tmpLeft);

if (tmpRight != null)

queueEnqueue(tmpRight);

}

話說BFS和DFS思想本來是用於圖的但我們不能被傳統的思維方式所束縛

算法基於單鏈表實現

如果沒有Queue給我們用我們只好使用單鏈表把每個節點存在單鏈表的Data中實現如下

public class Link

{

public Link Next;

public BinNode Data;

public Link(Link next BinNode data)

{

thisNext = next;

thisData = data;

}

看過了Queue的實現我們發現永遠是先出隊個（隊頭）然後入隊個（把出隊的Left和Right放到隊尾）

對於單鏈表而言我們可以先模擬入隊——把first的Data所對應的Left和Right先後插到second的後面即secondNext和secondNextNext位置同時second向前走或次再次到達鏈表末尾這取決於Left和Right是否為空然後我們模擬出隊——first前進步

當first指針走不下去了那麼任務也就結束了

static void PrintTree(BinNode root)

{

if (root == null) return;

Link head = new Link(null root);

Link first = head;

Link second = head;

while (first != null)

{

if (firstDataLeft != null)

{

secondNext = new Link(null firstDataLeft);

second = secondNext;

}

if (firstDataRight != null)

{

secondNext = new Link(null firstDataRight);

second = secondNext;

}

ConsoleWriteLine(firstDataElement);

first = firstNext;

}

如何判斷一棵二叉樹是否是平衡二叉樹

平衡二叉樹的定義如果任意節點的左右子樹的深度相差不超過那這棵樹就是平衡二叉樹

算法思路先編寫一個計算二叉樹深度的函數GetDepth利用遞歸實現然後再遞歸判斷每個節點的左右子樹的深度是否相差

static int GetDepth(BinNode root)

{

if (root == null)

return ;

int leftLength = GetDepth(rootLeft);

int rightLength = GetDepth(rootRight);

return (leftLength > rightLength

leftLength : rightLength) + ;

}

注意這裡的+對應於root不為空（算作當前個深度）

static bool IsBalanceTree(BinNode root)

{

if (root == null)

return true;

int leftLength = GetDepth(rootLeft);

int rightLength = GetDepth(rootRight);

int distance = leftLength > rightLength

leftLength &#; rightLength : rightLength &#; leftLength;

if (distance > )

return false;

else

return IsBalanceTree(rootLeft) && IsBalanceTree(rootRight);

}

上述程序的邏輯是只要當前節點root的Left和Right深度差不超過就遞歸判斷Left和Right是否也符合條件直到為Left或Right為null這意味著它們的深度為能走到這一步前面必然都符合條件所以整個二叉樹都符合條件

設計一個算法找出二叉樹上任意兩個節點的最近共同父結點復雜度如果是O(n)則不得分

本題網上有很多算法都不怎麼樣這裡提出包氏的兩個算法

算法做一個容器我們在遍歷二叉樹尋找節點的同時把從根到節點的路徑扔進去（兩個節點就是兩個容器）由於根節點最後一個被扔進去但我們接下來又需要第一個就能訪問到它——後進先出所以這個容器是一個棧時間復雜度O(N)空間復雜度O(N)

static bool GetPositionByNode(BinNode root BinNode node ref Stack stack)

{

if (root == null)

return false;

if (root == node)

{

stackPush(root);

return true;

}

if (GetPositionByNode(rootLeft node ref stack) || GetPositionByNode(rootRight node ref stack))

{

stackPush(root);

return true;

}

return false;

}

然後我們要同時彈出這兩個容器的元素直到它們不相等那麼之前那個相等的元素就是我們要求的父親節點

static BinNode FindParentNode(BinNode root BinNode node BinNode node)

{

Stack stack = new Stack();

GetPositionByNode(root node ref stack);

Stack stack = new Stack();

GetPositionByNode(root node ref stack);

BinNode tempNode = null;

while (stackPeek() == stackPeek())

{

tempNode = (BinNode)stackPop();

stackPop();

}

return tempNode;

}

算法如果要求o()的空間復雜度就是說只能用一個變量來輔助我們

我們選擇一個位的整數然後從開始從左到右逐層為二叉樹的每個元素賦值root對應rootLeft對應rootRight對應依次類推而不管實際這個位置上是否有節點我們發現兩個規律

////

如果要找的是和位置上的節點

我們發現它們的二進制分別是和右移使之與位數相同於是變成了（也就是的父親）

這時和（也就是和位於同樣的深度）我們從左往右找和具有位相同即這就是我們要找的和的父親也就是和的最近父親

由上面觀察得到算法

)將找到的兩個節點對應的數字

static bool GetPositionByNode(BinNode root BinNode node ref int pos)

{

if (root == null)

return false;

if (root == node)

return true;

int temp = pos;

//這麼寫很別扭但是能保證只要找到就不再進行下去

pos = temp * ;

if (GetPositionByNode(rootLeft node ref pos))

{

return true;

}

else

{

//找不到左邊找右邊

pos = temp * + ;

return GetPositionByNode(rootRight node ref pos);

}

)它們的二進制表示從左向右逐一比較直到一個結束或不再相同則最大的相同子串就是我們需要得到的最近父親所對應的位置K

static int FindParentPosition(int larger int smaller)

{

if (larger == smaller) return larger;

int left = GetLen(larger) &#; GetLen(smaller);

while (left > )

{

larger = larger >> ;

left&#;;

}

while (larger != smaller)

{

larger = larger >> ;

smaller = smaller >> ;

}

return smaller;

}

static int GetLen(int num)

{

int length = ;

while (num != )

{

num = num >> ;

length++;

}

return length;

}

)第次遞歸遍歷尋找K所對應的節點

函數GetNodeByPosition的思想是先算出k在第幾層power觀察k的二進制表示比如說即從左向右數第一個位不算還剩下表示向右走表示向左走於是從root出發>>>

static BinNode GetNodeByPosition(BinNode root int num)

{

if (num == ) return root;

int pow = (int)MathFloor(MathLog(num )); // return return return

//第一個位不算

num = << pow;

while (pow > )

{

if ((num & << (pow &#; )) == )

root = rootLeft;

else

root = rootRight;

pow&#;;

}

return root;

}

總結上面的個步驟

static BinNode FindParentNode(BinNode root BinNode node BinNode node)

{

int pos = ;

GetPositionByNode(root node ref pos);

int pos = ;

GetPositionByNode(root node ref pos);

int parentposition = ;

if (pos >= pos)

{

parentposition = FindParentPosition(pos pos);

}

else //pos<pos

{

parentposition = FindParentPosition(pos pos);

}

return GetNodeByPosition(root parentposition);

}

如何不用遞歸實現二叉樹的前序/後序/中序遍歷？

算法思想三種算法的思想都是讓root的Left的Left的Left全都入棧所以第一個while循環的邏輯都是相同的

下面詳細分析第個while循環這是一個出棧動作只要棧不為空就始終要彈出棧頂元素由於我們之前入棧的都是Left節點所以每次在出棧的時候我們都要考慮Right節點是否存在因為前序/後序/中序遍歷順序的不同所以在具體的實現上有略為區別

)前序遍歷

這個是最簡單的

前序遍歷是root>rootLeft>rootRight的順序

因為在第一個while循環中每次進棧的都可以認為是一個root所以我們直接打印然後rootRight和rootLeft先後進棧那麼出棧的時候就能確保先左後右的順序

static void PreOrder(BinNode root)

{

Stack stack = new Stack();

BinNode temp = root;

//入棧

while (temp != null)

{

ConsoleWriteLine(tempElement);

if (tempRight != null)

stackPush(tempRight);

temp = tempLeft;

}

//出棧當然也有入棧

while (stackCount > )

{

temp = (BinNode)stackPop();

ConsoleWriteLine(tempElement);

while (temp != null)

{

if (tempRight != null)

stackPush(tempRight);

temp = tempLeft;

}

//後序遍歷比較麻煩需要記錄上一個訪問的節點然後在本次循環中判斷當前節點的Right或Left是否為上個節點當前節點的Right為null表示沒有右節點

static void PostOrder(BinNode root)

{

Stack stack = new Stack();

BinNode temp = root;

//入棧

while (temp != null)

{

if (temp != null)

stackPush(temp);

temp = tempLeft;

}

//出棧當然也有入棧

while (stackCount > )

{

BinNode lastvisit = temp;

temp = (BinNode)stackPop();

if (tempRight == null || tempRight == lastvisit)

{

ConsoleWriteLine(tempElement);

}

else if (tempLeft == lastvisit)

{

stackPush(temp);

temp = tempRight;

stackPush(temp);

while (temp != null)

{

if (tempLeft != null)

stackPush(tempLeft);

temp = tempLeft;

}

//中序遍歷類似於前序遍歷

static void InOrder(BinNode root)

{

Stack stack = new Stack();

BinNode temp = root;

//入棧

while (temp != null)

{

if (temp != null)

stackPush(temp);

temp = tempLeft;

}

//出棧當然也有入棧

while (stackCount > )

{

temp = (BinNode)stackPop();

ConsoleWriteLine(tempElement);

if (tempRight != null)

{

temp = tempRight;

stackPush(temp);

while (temp != null)

{

if (tempLeft != null)

stackPush(tempLeft);

temp = tempLeft;

}

在二叉樹中找出和為某一值的所有路徑

算法思想這道題目的苦惱在於如果用遞歸只能打出一條路徑來其它符合條件的路徑打不出來

為此我們需要一個Stack來保存訪問過的節點即在對該節點的遞歸前讓其進棧對該節點的遞歸結束後再讓其出棧——深度優先原則（DFS）

此外在遞歸中如果發現某節點（及其路徑）符合條件如何從頭到尾打印是比較頭疼的因為DFS使用的是stack而不是queue為此我們需要一個臨時棧來輔助打印

static void FindBinNode(BinNode root int sum Stack stack)

{

if (root == null)

return;

stackPush(rootElement);

//Leaf

if (rootIsLeaf())

{

if (rootElement == sum)

{

Stack tempStack = new Stack();

while (stackCount > )

{

tempStackPush(stackPop());

}

while (tempStackCount > )

{

ConsoleWriteLine(tempStackPeek());

stackPush(tempStackPop());

}

ConsoleWriteLine();

}

if (rootLeft != null)

FindBinNode(rootLeft sum &#; rootElement stack);

if (rootRight != null)

FindBinNode(rootRight sum &#; rootElement stack);

stackPop();

}

怎樣編寫一個程序把一個有序整數數組放到二叉樹中？

算法思想我們該如何構造這棵二叉樹呢？當然是越平衡越好如下所示

//// arr[]

//// arr[] arr[]

//// arr[] arr[] arr[]

相應編碼如下

public static void InsertArrayIntoTree(int[] arr int pos ref BinNode root)

{

root = new BinNode(arr[pos] null null);

rootElement = arr[pos];

//if Left value less than arr length

if (pos * + > arrLength &#; )

{

return;

}

else

{

InsertArrayIntoTree(arr pos * + ref rootLeft);

}

//if Right value less than arr length

if (pos * + > arrLength &#; )

{

return;

}

else

{

rootRight = new BinNode(arr[pos * + ] null null);

InsertArrayIntoTree(arr pos * + ref rootRight);

}

判斷整數序列是不是二叉搜索樹的後序遍歷結果

比如給你一個數組 int a[] = [ ] 則F(a) => false

算法思想在後續遍歷得到的序列中最後一個元素為樹的根結點從頭開始掃描這個序列比根結點小的元素都應該位於序列的左半部分從第一個大於跟結點開始到跟結點前面的一個元素為止所有元素都應該大於跟結點因為這部分元素對應的是樹的右子樹根據這樣的劃分把序列劃分為左右兩部分我們遞歸地確認序列的左右兩部分是不是都是二元查找樹

由於不能使用動態數組所以我們每次遞歸都使用同一個數組arr通過start和length來模擬&#;部分&#;數組

public static bool VerifyArrayOfBST(int[] arr int start int length)

{

if (arr == null || arrLength == || arrLength == )

{

return false;

}

int root = arr[length + start ];

int i = start;

for (; i < length &#; ; i++)

{

if (arr[i] >= root)

break;

}

int j = i;

for (; j < length &#; ; j++)

{

if (arr[j] < root)

return false;

}

bool left = true;

if (i > start)

{

left = VerifyArrayOfBST(arr start i &#; start);

}

bool right = true;

if (j > i)

{

right = VerifyArrayOfBST(arr i j &#; i + );

}

return left && right;

}

求二叉樹的鏡像

算法利用上述遍歷二叉樹的方法（比如說前序遍歷）把訪問操作修改為交換左右節點的邏輯

static void PreOrder(ref BinNode root)

{

if (root == null)

return;

//visit current node

BinNode temp = rootLeft;

rootLeft = rootRight;

rootRight = temp;

PreOrder(ref rootLeft);

PreOrder(ref rootRight);

}

算法使用循環也可以完成相同的功能

static void PreOrder(ref BinNode root)

{

if (root == null)

return;

Stack stack = new Stack();

stackPush(root);

while (stackCount > )

{

//visit current node

BinNode temp = rootLeft;

rootLeft = rootRight;

rootRight = temp;

if (rootLeft != null)

stackPush(rootLeft);

if (rootRight != null)

stackPush(rootRight);

}

一棵排序二叉樹（即二叉搜索樹BST）令 f=(最大值+最小值)/設計一個算法找出距離f值最近大於f值的結點復雜度如果是O(n)則不得分

算法思想最小最大節點分別在最左下與最右下節點O(N)

static BinNode Find(BinNode root)

{

BinNode min = FindMinNode(root);

BinNode max = FindMaxNode(root);

double find = (double)(minElement + maxElement) / ;

return FindNode(root find);

}

static BinNode FindMinNode(BinNode root)

{

BinNode min = root;

while (minLeft != null)

{

min = minLeft;

}

return min;

}

static BinNode FindMaxNode(BinNode root)

{

BinNode max = root;

while (maxRight != null)

{

max = maxRight;

}

return max;

}

遞歸尋找BST的節點O(logN)

static BinNode FindNode(BinNode root double mid)

{

//如果小於相等則從右邊找一個最小值

if (rootElement <= mid)

{

if (rootRight == null)

return root;

BinNode find = FindNode(rootRight mid);

//不一定找得到

return findElement < mid

root : find;

}

//如果大於則找到Left

else //tempElement > find

{

if (rootLeft == null)

return root;

BinNode find = FindNode(rootLeft mid);

//不一定找得到

return findElement < mid

root : find;

}

把二叉搜索樹轉變成排序的雙向鏈表如

////

轉變為Link=======

算法思想這個就是中序遍歷啦因為BST的中序遍歷就是一個從小到大的訪問順序局部修改中序遍歷算法於是有如下代碼

static void ConvertNodeToLink(BinNode root ref DoubleLink link)

{

if (root == null)

return;

BinNode temp = root;

if (tempLeft != null)

ConvertNodeToLink(tempLeft ref link);

//visit current node

linkNext = new DoubleLink(link null root);

link = linkNext;

if (tempRight != null)

ConvertNodeToLink(tempRight ref link);

}

但是我們發現這樣得到的Link是指向雙鏈表最後一個元素而我們想要得到的是表頭為此我們不得不額外進行while循環將指針向前移動到表頭

static DoubleLink ReverseDoubleLink(BinNode root ref DoubleLink link)

{

ConvertNodeToLink(root ref link);

DoubleLink temp = link;

while (tempPrev != null)

{

temp = tempPrev;

}

return temp;

}

這麼寫有點蠢為什麼不直接在遞歸中就把順序反轉呢？於是有算法

算法觀察算法的遞歸方法訪問順序是Left > Root –> Right所以我們要把訪問順序修改為Right > Root –> Left

此外算法的節點訪問邏輯是連接當前節點和新節點同時指針link向前走即========link

代碼如下所示

linkNext = new DoubleLink(link null root);

link = linkNext;

那麼即使我們顛倒了訪問順序新的Link也只是變為========link

為此我們修改上面的節點訪問邏輯——將Next和Prev屬性交換

linkPrev = new DoubleLink(null link root);

link = linkPrev;

這樣新的Link就變成這樣的順序了link========

算法代碼如下所示

static void ConvertNodeToLink(BinNode root ref DoubleLink link)

{

if (root == null)

return;

BinNode temp = root;

if (tempRight != null)

ConvertNodeToLink(tempRight ref link);

//visit current node

linkPrev = new DoubleLink(null link root);

link = linkPrev;

if (tempLeft != null)

ConvertNodeToLink(tempLeft ref link);

}

以下算法屬於二叉樹的基本概念未列出

Huffman Tree的生成編碼和反編碼

BST的實現

Heap的實現優先隊列

非平衡二叉樹如何變成平衡二叉樹？

玩二叉樹基本都要用到遞歸算法

唉對於遞歸函數我一直糾結到底要不要返回值？到底先干正事還是先遞歸？到底要不要破壞原來的數據結構？到底要不要額外做個stack/queue/link/array來轉存還是說完全在遞歸裡面實現？到底終結條件要寫成什麼樣子？ ref在遞歸裡面貌似用的很多哦

From:http://tw.wingwit.com/Article/program/sjjg/201404/30577.html