目錄：
1.二叉樹(shù)三種周游（traversal）方式：
2.怎樣從頂部開(kāi)始逐層打印二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)
3.如何判斷一棵二叉樹(shù)是否是平衡二叉樹(shù)
4.設(shè)計(jì)一個(gè)算法，找出二叉樹(shù)上任意兩個(gè)節(jié)點(diǎn)的最近共同父結(jié)點(diǎn)，復(fù)雜度如果是O(n2)則不得分。
5.如何不用遞歸實(shí)現(xiàn)二叉樹(shù)的前序/后序/中序遍歷？
6.在二叉樹(shù)中找出和為某一值的所有路徑
7.怎樣編寫(xiě)一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹(shù)中？
8.判斷整數(shù)序列是不是二叉搜索樹(shù)的后序遍歷結(jié)果
9.求二叉樹(shù)的鏡像
10.一棵排序二叉樹(shù)（即二叉搜索樹(shù)BST），令 f=(最大值+最小值)/2，設(shè)計(jì)一個(gè)算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。復(fù)雜度如果是O(n2)則不得分。
11.把二叉搜索樹(shù)轉(zhuǎn)變成排序的雙向鏈表
首先寫(xiě)一個(gè)二叉樹(shù)的C#實(shí)現(xiàn)，這是我們的基石：
public class BinNode
{
public int Element;
public BinNode Left;
public BinNode Right;
public BinNode(int element, BinNode left, BinNode right)
{
this.Element = element;
this.Left = left;
this.Right = right;
}
public bool IsLeaf()
{
return this.Left == null && this.Right == null;
}
}
1.二叉樹(shù)三種周游（traversal）方式：
1）前序周游（preorder）：節(jié)點(diǎn) –> 子節(jié)點(diǎn)Left（包括其子樹(shù)） –> 子節(jié)點(diǎn)Right（包括其子樹(shù)）
static void PreOrder(BinNode root)
{
if (root == null)
return;
//visit current node
Console.WriteLine(root.Element);
PreOrder(root.Left);
PreOrder(root.Right);
}
2）后序周游（postorder）：子節(jié)點(diǎn)Left（包括其子樹(shù)） –> 子節(jié)點(diǎn)Right（包括其子樹(shù)） –> 節(jié)點(diǎn)
static void PostOrder(BinNode root)
{
if (root == null)
return;
PostOrder(root.Left);
PostOrder(root.Right);
//visit current node
Console.WriteLine(root.Element);
}
3）中序周游（inorder）：子節(jié)點(diǎn)Left（包括其子樹(shù)） –> 節(jié)點(diǎn) –> 子節(jié)點(diǎn)Right（包括其子樹(shù)）
static void InOrder(BinNode root)
{
if (root == null)
return;
InOrder(root.Left);
//visit current node
Console.WriteLine(root.Element);
InOrder(root.Right);
}
我們發(fā)現(xiàn)，三種周游的code實(shí)現(xiàn)，僅僅是訪問(wèn)當(dāng)前節(jié)點(diǎn)的這條語(yǔ)句所在位置不同而已。
2.怎樣從頂部開(kāi)始逐層打印二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)
有2種算法：
算法1：基于Queue來(lái)實(shí)現(xiàn)，也就是廣度優(yōu)先搜索（BFS）的思想
static void PrintTree1(BinNode root)
{
if (root == null) return;
BinNode tmp = null;
Queue queue = new Queue();
queue.Enqueue(root);
while (queue.Count > 0)
{
tmp = (BinNode)queue.Dequeue();
Console.WriteLine(tmp.Element);
if (tmp.Left != null)
queue.Enqueue(tmp.Left);
if (tmp.Right != null)
queue.Enqueue(tmp.Right);
}
}
話說(shuō)，BFS和DFS思想本來(lái)是用于圖的，但我們不能被傳統(tǒng)的思維方式所束縛。
算法2：基于單鏈表實(shí)現(xiàn)
如果沒(méi)有Queue給我們用，我們只好使用單鏈表，把每個(gè)節(jié)點(diǎn)存在單鏈表的Data中，實(shí)現(xiàn)如下：
public class Link
{
public Link Next;
public BinNode Data;
public Link(Link next, BinNode data)
{
this.Next = next;
this.Data = data;
}
}
看過(guò)了Queue的實(shí)現(xiàn)，我們發(fā)現(xiàn)永遠(yuǎn)是先出隊(duì)1個(gè)（隊(duì)頭），然后入隊(duì)2個(gè)（把出隊(duì)的Left和Right放到隊(duì)尾）。
對(duì)于單鏈表而言，我們可以先模擬入隊(duì)——把first的Data所對(duì)應(yīng)的Left和Right，先后插到second的后面，即second.Next和second.Next.Next位置，同時(shí)second向前走0、1或2次，再次到達(dá)鏈表末尾，這取決于Left和Right是否為空；然后我們模擬出隊(duì)——first前進(jìn)1步。
當(dāng)first指針走不下去了，那么任務(wù)也就結(jié)束了。
static void PrintTree2(BinNode root)
{
if (root == null) return;
Link head = new Link(null, root);
Link first = head;
Link second = head;
while (first != null)
{
if (first.Data.Left != null)
{
second.Next = new Link(null, first.Data.Left);
second = second.Next;
}
if (first.Data.Right != null)
{
second.Next = new Link(null, first.Data.Right);
second = second.Next;
}
Console.WriteLine(first.Data.Element);
first = first.Next;
}
}
3.如何判斷一棵二叉樹(shù)是否是平衡二叉樹(shù)
平衡二叉樹(shù)的定義，如果任意節(jié)點(diǎn)的左右子樹(shù)的深度相差不超過(guò)1，那這棵樹(shù)就是平衡二叉樹(shù)。
算法思路：先編寫(xiě)一個(gè)計(jì)算二叉樹(shù)深度的函數(shù)GetDepth，利用遞歸實(shí)現(xiàn)；然后再遞歸判斷每個(gè)節(jié)點(diǎn)的左右子樹(shù)的深度是否相差1
static int GetDepth(BinNode root)
{
if (root == null)
return 0;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
return (leftLength > rightLength
leftLength : rightLength) + 1;
}
注意這里的+1，對(duì)應(yīng)于root不為空（算作當(dāng)前1個(gè)深度）
static bool IsBalanceTree(BinNode root)
{
if (root == null)
return true;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
int distance = leftLength > rightLength
leftLength – rightLength : rightLength – leftLength;
if (distance > 1)
return false;
else
return IsBalanceTree(root.Left) && IsBalanceTree(root.Right);
}
上述程序的邏輯是，只要當(dāng)前節(jié)點(diǎn)root的Left和Right深度差不超過(guò)1，就遞歸判斷Left和Right是否也符合條件，直到為L(zhǎng)eft或Right為null，這意味著它們的深度為0，能走到這一步，前面必然都符合條件，所以整個(gè)二叉樹(shù)都符合條件。
4.設(shè)計(jì)一個(gè)算法，找出二叉樹(shù)上任意兩個(gè)節(jié)點(diǎn)的最近共同父結(jié)點(diǎn)，復(fù)雜度如果是O(n2)則不得分。
本題網(wǎng)上有很多算法，都不怎么樣。這里提出包氏的兩個(gè)算法：
算法1：做一個(gè)容器，我們?cè)诒闅v二叉樹(shù)尋找節(jié)點(diǎn)的同時(shí)，把從根到節(jié)點(diǎn)的路徑扔進(jìn)去（兩個(gè)節(jié)點(diǎn)就是兩個(gè)容器）。由于根節(jié)點(diǎn)最后一個(gè)被扔進(jìn)去，但我們接下來(lái)又需要第一個(gè)就能訪問(wèn)到它——后進(jìn)先出，所以這個(gè)容器是一個(gè)棧。時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(N)。
static bool GetPositionByNode(BinNode root, BinNode node, ref Stack stack)
{
if (root == null)
return false;
if (root == node)
{
stack.Push(root);
return true;
}
if (GetPositionByNode(root.Left, node, ref stack) || GetPositionByNode(root.Right, node, ref stack))
{
stack.Push(root);
return true;
}
return false;
}
然后我們要同時(shí)彈出這兩個(gè)容器的元素，直到它們不相等，那么之前那個(gè)相等的元素就是我們要求的父親節(jié)點(diǎn)。
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2)
{
Stack stack1 = new Stack();
GetPositionByNode(root, node1, ref stack1);
Stack stack2 = new Stack();
GetPositionByNode(root, node2, ref stack2);
BinNode tempNode = null;
while (stack1.Peek() == stack2.Peek())
{
tempNode = (BinNode)stack1.Pop();
stack2.Pop();
}
return tempNode;
}
算法2：如果要求o(1)的空間復(fù)雜度，就是說(shuō)，只能用一個(gè)變量來(lái)輔助我們。
我們選擇一個(gè)64位的整數(shù)，然后從1開(kāi)始，從左到右逐層為二叉樹(shù)的每個(gè)元素賦值，root對(duì)應(yīng)1，root.Left對(duì)應(yīng)2，root.Right對(duì)應(yīng)3，依次類(lèi)推，而不管實(shí)際這個(gè)位置上是否有節(jié)點(diǎn)，我們發(fā)現(xiàn)兩個(gè)規(guī)律：
//// 1
//// 2 3
//// 4 5 6 7
//// 8 9 10
如果要找的是5和9位置上的節(jié)點(diǎn)。
我們發(fā)現(xiàn)，它們的二進(jìn)制分別是101和1001，右移1001使之與101位數(shù)相同，于是1001變成了100（也就是9的父親4）。
這時(shí)101和100（也就是4和5位于同樣的深度），我們從左往右找，101和100具有2位相同，即10，這就是我們要找的4和5的父親，也就是9和5的最近父親。
由上面觀察，得到算法：
1)將找到的兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的數(shù)字
static bool GetPositionByNode(BinNode root, BinNode node, ref int pos)
{
if (root == null)
return false;
if (root == node)
return true;
int temp = pos;
//這么寫(xiě)很別扭，但是能保證只要找到就不再進(jìn)行下去
pos = temp * 2;
if (GetPositionByNode(root.Left, node, ref pos))
{
return true;
}
else
{
//找不到左邊找右邊
pos = temp * 2 + 1;
return GetPositionByNode(root.Right, node, ref pos);
}
}
2)它們的二進(jìn)制表示，從左向右逐一比較，直到一個(gè)結(jié)束或不再相同，則最大的相同子串，就是我們需要得到的最近父親所對(duì)應(yīng)的位置K。
static int FindParentPosition(int larger, int smaller)
{
if (larger == smaller) return larger;
int left = GetLen(larger) – GetLen(smaller);
while (left > 0)
{
larger = larger >> 1;
left–;
}
while (larger != smaller)
{
larger = larger >> 1;
smaller = smaller >> 1;
}
return smaller;
}
static int GetLen(int num)
{
int length = 0;
while (num != 0)
{
num = num >> 1;
length++;
}
return length;
}
3)第3次遞歸遍歷，尋找K所對(duì)應(yīng)的節(jié)點(diǎn)。
函數(shù)GetNodeByPosition的思想是，先算出k在第幾層power，觀察k的二進(jìn)制表示，比如說(shuō)12，即1100，從左向右數(shù)第一個(gè)位1不算，還剩下100，1表示向右走，0表示向左走，于是從root出發(fā)，1->3->6->12。
static BinNode GetNodeByPosition(BinNode root, int num)
{
if (num == 1) return root;
int pow = (int)Math.Floor(Math.Log(num, 2)); //1 return 0, 2-3 return 1, 4-7 return 2
//第一個(gè)位不算
num -= 1 << pow;
while (pow > 0)
{
if ((num & 1 << (pow - 1)) == 0)
root = root.Left;
else
root = root.Right;
pow--;
}
return root;
}
總結(jié)上面的3個(gè)步驟：
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2)
{
int pos1 = 1;
GetPositionByNode(root, node1, ref pos1);
int pos2 = 1;
GetPositionByNode(root, node2, ref pos2);
int parentposition = 0;
if (pos1 >= pos2)
{
parentposition = FindParentPosition(pos1, pos2);
}
else //pos1 {
parentposition = FindParentPosition(pos2, pos1);
}
return GetNodeByPosition(root, parentposition);
}
5.如何不用遞歸實(shí)現(xiàn)二叉樹(shù)的前序/后序/中序遍歷？
算法思想：三種算法的思想都是讓root的Left的Left的Left全都入棧。所以第一個(gè)while循環(huán)的邏輯，都是相同的。
下面詳細(xì)分析第2個(gè)while循環(huán)，這是一個(gè)出棧動(dòng)作，只要棧不為空，就始終要彈出棧頂元素，由于我們之前入棧的都是Left節(jié)點(diǎn)，所以每次在出棧的時(shí)候，我們都要考慮Right節(jié)點(diǎn)是否存在。因?yàn)榍靶?后序/中序遍歷順序的不同，所以在具體的實(shí)現(xiàn)上有略為區(qū)別。
1)前序遍歷
這個(gè)是最簡(jiǎn)單的。
前序遍歷是root->root.Left->root.Right的順序。
因?yàn)樵诘谝粋€(gè)while循環(huán)中，每次進(jìn)棧的都可以認(rèn)為是一個(gè)root，所以我們直接打印，然后root.Right和root.Left先后進(jìn)棧，那么出棧的時(shí)候，就能確保先左后右的順序。
static void PreOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入棧
while (temp != null)
{
Console.WriteLine(temp.Element);
if (temp.Right != null)
stack.Push(temp.Right);
temp = temp.Left;
}
//出棧，當(dāng)然也有入棧
while (stack.Count > 0)
{
temp = (BinNode)stack.Pop();
Console.WriteLine(temp.Element);
while (temp != null)
{
if (temp.Right != null)
stack.Push(temp.Right);
temp = temp.Left;
}
}
}
//后序遍歷比較麻煩，需要記錄上一個(gè)訪問(wèn)的節(jié)點(diǎn)，然后在本次循環(huán)中判斷當(dāng)前節(jié)點(diǎn)的Right或Left是否為上個(gè)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的Right為null表示沒(méi)有右節(jié)點(diǎn)。
static void PostOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入棧
while (temp != null)
{
if (temp != null)
stack.Push(temp);
temp = temp.Left;
}
//出棧，當(dāng)然也有入棧
while (stack.Count > 0)
{
BinNode lastvisit = temp;
temp = (BinNode)stack.Pop();
if (temp.Right == null || temp.Right == lastvisit)
{
Console.WriteLine(temp.Element);
}
else if (temp.Left == lastvisit)
{
stack.Push(temp);
temp = temp.Right;
stack.Push(temp);
while (temp != null)
{
if (temp.Left != null)
stack.Push(temp.Left);
temp = temp.Left;
}
}
}
}
//中序遍歷，類(lèi)似于前序遍歷
static void InOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入棧
while (temp != null)
{
if (temp != null)
stack.Push(temp);
temp = temp.Left;
}
//出棧，當(dāng)然也有入棧
while (stack.Count > 0)
{
temp = (BinNode)stack.Pop();
Console.WriteLine(temp.Element);
if (temp.Right != null)
{
temp = temp.Right;
stack.Push(temp);
while (temp != null)
{
if (temp.Left != null)
stack.Push(temp.Left);
temp = temp.Left;
}
}
}
}
6.在二叉樹(shù)中找出和為某一值的所有路徑
算法思想：這道題目的苦惱在于，如果用遞歸，只能打出一條路徑來(lái)，其它符合條件的路徑打不出來(lái)。
為此，我們需要一個(gè)Stack，來(lái)保存訪問(wèn)過(guò)的節(jié)點(diǎn)，即在對(duì)該節(jié)點(diǎn)的遞歸前讓其進(jìn)棧，對(duì)該節(jié)點(diǎn)的遞歸結(jié)束后，再讓其出棧——深度優(yōu)先原則（DFS）。
此外，在遞歸中，如果發(fā)現(xiàn)某節(jié)點(diǎn)（及其路徑）符合條件，如何從頭到尾打印是比較頭疼的，因?yàn)镈FS使用的是stack而不是queue，為此我們需要一個(gè)臨時(shí)棧，來(lái)輔助打印。
static void FindBinNode(BinNode root, int sum, Stack stack)
{
if (root == null)
return;
stack.Push(root.Element);
//Leaf
if (root.IsLeaf())
{
if (root.Element == sum)
{
Stack tempStack = new Stack();
while (stack.Count > 0)
{
tempStack.Push(stack.Pop());
}
while (tempStack.Count > 0)
{
Console.WriteLine(tempStack.Peek());
stack.Push(tempStack.Pop());
}
Console.WriteLine();
}
}
if (root.Left != null)
FindBinNode(root.Left, sum – root.Element, stack);
if (root.Right != null)
FindBinNode(root.Right, sum – root.Element, stack);
stack.Pop();
}
7.怎樣編寫(xiě)一個(gè)程序，把一個(gè)有序整數(shù)數(shù)組放到二叉樹(shù)中？
算法思想：我們?cè)撊绾螛?gòu)造這棵二叉樹(shù)呢？當(dāng)然是越平衡越好，如下所示：
//// arr[0]
//// arr[1] arr[2]
//// arr[3] arr[4] arr[5]
相應(yīng)編碼如下：
public static void InsertArrayIntoTree(int[] arr, int pos, ref BinNode root)
{
root = new BinNode(arr[pos], null, null);
root.Element = arr[pos];
//if Left value less than arr length
if (pos * 2 + 1 > arr.Length – 1)
{
return;
}
else
{
InsertArrayIntoTree(arr, pos * 2 + 1, ref root.Left);
}
//if Right value less than arr length
if (pos * 2 + 2 > arr.Length – 1)
{
return;
}
else
{
root.Right = new BinNode(arr[pos * 2 + 2], null, null);
InsertArrayIntoTree(arr, pos * 2 + 2, ref root.Right);
}
}
8.判斷整數(shù)序列是不是二叉搜索樹(shù)的后序遍歷結(jié)果
比如，給你一個(gè)數(shù)組： int a[] = [1, 6, 4, 3, 5] ，則F(a) => false
算法思想：在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹(shù)的根結(jié)點(diǎn)。從頭開(kāi)始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分；從第一個(gè)大于跟結(jié)點(diǎn)開(kāi)始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹(shù)的右子樹(shù)。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹(shù)。
由于不能使用動(dòng)態(tài)數(shù)組，所以我們每次遞歸都使用同一個(gè)數(shù)組arr，通過(guò)start和length來(lái)模擬“部分”數(shù)組。
public static bool VerifyArrayOfBST(int[] arr, int start, int length)
{
if (arr == null || arr.Length == 0 || arr.Length == 1)
{
return false;
}
int root = arr[length + start - 1];
int i = start;
for (; i < length - 1; i++)
{
if (arr[i] >= root)
break;
}
int j = i;
for (; j < length - 1; 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 + 1);
}
return left && right;
}
9.求二叉樹(shù)的鏡像
算法1：利用上述遍歷二叉樹(shù)的方法（比如說(shuō)前序遍歷），把訪問(wèn)操作修改為交換左右節(jié)點(diǎn)的邏輯：
static void PreOrder(ref BinNode root)
{
if (root == null)
return;
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
PreOrder(ref root.Left);
PreOrder(ref root.Right);
}
算法2：使用循環(huán)也可以完成相同的功能。
static void PreOrder2(ref BinNode root)
{
if (root == null)
return;
Stack stack = new Stack();
stack.Push(root);
while (stack.Count > 0)
{
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
if (root.Left != null)
stack.Push(root.Left);
if (root.Right != null)
stack.Push(root.Right);
}
}
10.一棵排序二叉樹(shù)（即二叉搜索樹(shù)BST），令 f=(最大值+最小值)/2，設(shè)計(jì)一個(gè)算法，找出距離f值最近、大于f值的結(jié)點(diǎn)。復(fù)雜度如果是O(n2)則不得分。
算法思想：最小最大節(jié)點(diǎn)分別在最左下與最右下節(jié)點(diǎn)，O(N)
static BinNode Find(BinNode root)
{
BinNode min = FindMinNode(root);
BinNode max = FindMaxNode(root);
double find = (double)(min.Element + max.Element) / 2;
return FindNode(root, find);
}
static BinNode FindMinNode(BinNode root)
{
BinNode min = root;
while (min.Left != null)
{
min = min.Left;
}
return min;
}
static BinNode FindMaxNode(BinNode root)
{
BinNode max = root;
while (max.Right != null)
{
max = max.Right;
}
return max;
}
遞歸尋找BST的節(jié)點(diǎn)，O(logN)。
static BinNode FindNode(BinNode root, double mid)
{
//如果小于相等，則從右邊找一個(gè)最小值
if (root.Element <= mid)
{
if (root.Right == null)
return root;
BinNode find = FindNode(root.Right, mid);
//不一定找得到
return find.Element < mid
root : find;
}
//如果大于，則找到Left
else //temp.Element > find
{
if (root.Left == null)
return root;
BinNode find = FindNode(root.Left, mid);
//不一定找得到
return find.Element < mid
root : find;
}
}
11.把二叉搜索樹(shù)轉(zhuǎn)變成排序的雙向鏈表，如
//// 13
//// 10 15
//// 5 11 17
//// 16 22
轉(zhuǎn)變?yōu)長(zhǎng)ink：5=10=11=13=15=16=17=22
算法思想：這個(gè)就是中序遍歷啦，因?yàn)锽ST的中序遍歷就是一個(gè)從小到大的訪問(wèn)順序。局部修改中序遍歷算法，于是有如下代碼：
static void ConvertNodeToLink(BinNode root, ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (temp.Left != null)
ConvertNodeToLink(temp.Left, ref link);
//visit current node
link.Next = new DoubleLink(link, null, root);
link = link.Next;
if (temp.Right != null)
ConvertNodeToLink(temp.Right, ref link);
}
但是我們發(fā)現(xiàn)，這樣得到的Link是指向雙鏈表最后一個(gè)元素22，而我們想要得到的是表頭5，為此，我們不得不額外進(jìn)行while循環(huán)，將指針向前移動(dòng)到表頭：
static DoubleLink ReverseDoubleLink(BinNode root, ref DoubleLink link)
{
ConvertNodeToLink(root, ref link);
DoubleLink temp = link;
while (temp.Prev != null)
{
temp = temp.Prev;
}
return temp;
}
這么寫(xiě)有點(diǎn)蠢，為什么不直接在遞歸中就把順序反轉(zhuǎn)呢？于是有算法2：
算法2：觀察算法1的遞歸方法，訪問(wèn)順序是Left -> Root –> Right，所以我們要把訪問(wèn)順序修改為Right -> Root –> Left。
此外，算法的節(jié)點(diǎn)訪問(wèn)邏輯，是連接當(dāng)前節(jié)點(diǎn)和新節(jié)點(diǎn)，同時(shí)指針link向前走，即5=10=11=13=15=16=17=22=link
代碼如下所示：
link.Next = new DoubleLink(link, null, root);
link = link.Next;
那么，即使我們顛倒了訪問(wèn)順序，新的Link也只是變?yōu)椋?2=17=16=15=13=11=10=5=link。
為此，我們修改上面的節(jié)點(diǎn)訪問(wèn)邏輯——將Next和Prev屬性交換：
link.Prev = new DoubleLink(null, link, root);
link = link.Prev;
這樣，新的Link就變成這樣的順序了：link=5=10=11=13=15=16=17=22
算法代碼如下所示：
static void ConvertNodeToLink2(BinNode root, ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (temp.Right != null)
ConvertNodeToLink2(temp.Right, ref link);
//visit current node
link.Prev = new DoubleLink(null, link, root);
link = link.Prev;
if (temp.Left != null)
ConvertNodeToLink2(temp.Left, ref link);
}
以下算法屬于二叉樹(shù)的基本概念，未列出：
1.Huffman Tree的生成、編碼和反編碼
2.BST的實(shí)現(xiàn)
3.Heap的實(shí)現(xiàn)，優(yōu)先隊(duì)列
4.非平衡二叉樹(shù)如何變成平衡二叉樹(shù)？
http://www.cppblog.com/bellgrade/archive/2009/10/12/98402.html
玩二叉樹(shù)，基本都要用到遞歸算法。
唉，對(duì)于遞歸函數(shù)，我一直糾結(jié)，到底要不要返回值？到底先干正事還是先遞歸？到底要不要破壞原來(lái)的數(shù)據(jù)結(jié)構(gòu)？到底要不要額外做個(gè)stack/queue/link/array來(lái)轉(zhuǎn)存，還是說(shuō)完全在遞歸里面實(shí)現(xiàn)？到底終結(jié)條件要寫(xiě)成什么樣子？ ref在遞歸里面貌似用的很多哦。
聯(lián)系客服
