﻿ 二叉樹_電腦知識網

# 二叉樹

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

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

）前序周游（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);
}

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

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

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