二叉樹

目錄
二叉樹三種周游（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

{
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/201405/30936.html