﻿ 算法大全-面試題-數據結構(收錄)_電腦知識網

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

2022-06-13   來源: 數據結構

## 一單鏈表

?

?

{

public string Data;

{

thisNext = next;

thisData = data;

}

}

?

?

?

?

?

static void Main(string[] args)

{

while (curr != null)

{

ConsoleWriteLine(currData);

curr = currNext;

}

}

?

?

### 單鏈表反轉

{

//if no elements or only one element exists

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

{

}

//if more than one element

while (currNext != null)

{

next = currNext; //

nextnext = nextNext; //

currNext = nextnext; //

}

}

?

?

?

?

?

?

{

{

}

}

?

?

{

//if no elements or only one element exists

}

?

?

{

}

?

?

?

?

?

?

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

{

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;

}

?

?

{

int i = ;

while (currNext != null)

{

arr[i] = currNext;

curr = currNext;

i = (i + ) % ;

}

if (arr[i] == null)

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

return arr[i];

}

?

?

?

?

### 找出單鏈表的中間元素

{

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

{

first = firstNextNext;

second = secondNext;

}

return second;

}

static void Main(string[] args)

{

bool isOdd = true;

if (isOdd)

{

ConsoleWriteLine(middleData);

}

else

{

ConsoleWriteLine(middleData);

ConsoleWriteLine(middleNextData);

}

}

{

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

{

first = firstNextNext;

second = secondNext;

}

if (first != null)

isOdd = false;

return second;

}

?

?

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

?

?

currData = currNextData;

?

currNext = currNextNext;

?

?

?

?

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

{

//compare until one link run to the end

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

{

if (currNextData < currNextData)

{

curr = currNext;

}

else

{

curr = currNext;

}

preNext = curr;

pre = preNext;

}

//if head run to the end

while (currNext != null)

{

curr = currNext;

preNext = curr;

pre = preNext;

}

//if head run to the end

while (currNext != null)

{

curr = currNext;

preNext = curr;

pre = preNext;

}

}

?

?

?

{

//compare until one link run to the intersect

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

{

if (currNextData < currNextData)

{

curr = currNext;

}

else

{

curr = currNext;

}

preNext = curr;

pre = preNext;

}

//if head run to the intersect

if (currNext == intersect)

{

while (currNext != null)

{

curr = currNext;

preNext = curr;

pre = preNext;

}

}

//if head run to the intersect

else if (currNext == intersect)

{

while (currNext != null)

{

curr = currNext;

preNext = curr;

pre = preNext;

}

}

}

?

?

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

{

public int Data;

{

thisNext = next;

thisData = data;

}

}

{

{

thisNext = next;

}

}

?

?

{

}

–>

?

?

{

while (curr != null)

{

currNext = currNextNext;

while (currNext != null)

{

curr = currNext;

}

}

}

?

?

?

?

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

{

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

if (p == q)

//find p and q in the link

?

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;

}

?

?

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

{

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

{

second = secondNextNext;

first = firstNext;

if (second == first)

return true;

}

return false;

}

?

?

{

int length = ;

while (currNext != point)

{

length++;

curr = currNext;

}

return length;

}

?

?

{

int length = ;

while (curr != point)

{

length++;

curr = currNext;

}

return length;

}

?

?

{

//get the point in the circle

bool result = JudgeCircleExists(head ref p);

if (!result) return null;

int M = ;

while (curr != p)

{

M++;

curr = currNext;

}

//circle length

int N = ;

while (curr != p)

{

N++;

curr = currNext;

}

//recover curr & curr

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;

curr = currNext;

}

return null;

}

?

?

### 判斷兩個單鏈表是否相交

{

Hashtable ht = new Hashtable();

//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;

}

?

?

{

bool exists = false;

?

//goto the end of the link

while (currNext != null)

{

curr = currNext;

}

while (currNext != null)

{

{

exists = true;

break;

}

curr = currNext;

}

//recover original status whether exists or not

currNext = null;

return exists;

}

?

?

{

//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;

}

?

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

{

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++;

}

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;

curr = currNext;

}

return null;

}

?

?

>>>>NULL

{

// goto the end

return ;

int temp = ;

int result = ;

if (M > N)

{

return temp >=

: ;

}

else // M == N

{

return temp >=

: ;

}

}

?

?

### 單鏈表排序

?

?

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];

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

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

}

}

?

return arr;

}

{

{

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;

}

}

?

?

?

?

?

?

### 刪除單鏈表中重復的元素

{

Hashtable ht = new Hashtable();

while (curr != null)

{

if (currNext == null)

{

break;

}

if (ht[currNextData] != null)

{

currNext = currNextNext;

}

else

{

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

}

curr = currNext;

}

}

?

?

?

?

?

?

## 二棧和隊列

?

?

?

?

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

?

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函數的棧的另解

public class NewStack

{

private Stack stack;

public NewStack()

{

stack = new Stack();

}

public void Push(int element)

{

if (stackCount == )

{

stackPush(element);

stackPush(element);

}

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

{

stackPush(element);

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();

}

}

?

?

?

?

?

?

### 用兩個棧實現隊列

）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;

private Stack stack;

public NewQueue()

{

stack = new Stack();

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();

}

}

?

?

?

### 用兩個隊列實現棧

public class NewStack

{

private Queue queue;

private Queue queue;

public NewStack()

{

queue = new Queue();

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序列是否一致

?

?

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);

}

}

?

?

?

?

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

?

?

?

?

public class NewStack

{

object[] arr;

int top;

int top;

public NewStack(int capticy)

{

arr = new object[capticy];

top = ;

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];

}

}

}

?

?

?

?

?

public class NewStack

{

object[] arr;

int top;

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];

}

}

}

?

?

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

?

?

?

public class NewStack

{

object[] arr;

int top;

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 ];

}

}

}

?

?

?

?

## 三二叉樹

?

?

?

?

?

?

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);

}

?

?

?

?

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

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);

}

}

?

?

?

?

{

public BinNode Data;

{

thisNext = next;

thisData = data;

}

}

static void PrintTree(BinNode root)

{

if (root == null) return;

while (first != null)

{

if (firstDataLeft != null)

{

second = secondNext;

}

if (firstDataRight != null)

{

second = secondNext;

}

ConsoleWriteLine(firstDataElement);

first = firstNext;

}

}

?

?

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

static int GetDepth(BinNode root)

{

if (root == null)

return ;

int leftLength = GetDepth(rootLeft);

int rightLength = GetDepth(rootRight);

return (leftLength > rightLength

leftLength : rightLength) + ;

}

?

?

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);

}

?

?

?

?

### 設計一個算法找出二叉樹上任意兩個節點的最近共同父結點復雜度如果是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;

}

?

?

////

////

////

////

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

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所對應的節點

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);

}

?

?

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

)前序遍歷

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;

}

}

}

}

?

?

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

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);

}

}

?

?

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

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)則不得分

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;

}

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;

}

}

?

?

?

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

////

////

////

////

{

if (root == null)

return;

BinNode temp = root;

if (tempLeft != null)

//visit current node

if (tempRight != null)

}

?

?

{

while (tempPrev != null)

{

temp = tempPrev;

}

return temp;

}

?

?

{

if (root == null)

return;

BinNode temp = root;

if (tempRight != null)

//visit current node

if (tempLeft != null)

}

?

?

Huffman Tree的生成編碼和反編碼

BST的實現

Heap的實現優先隊列

?

?

From:http://tw.wingwit.com/Article/program/sjjg/201404/30577.html
• 上一篇文章：

• 下一篇文章：