書名：《圖說演算法-使用C#》
作者：吳燦銘、胡昭民
所讀版本：博碩文化
二叉樹
滿二叉樹（Fully Binary Tree）
節點數 = 2^(高度) – 1，高度>=0
完全二叉樹（Complete Binary Tree）
節點數 < 2^(高度) – 1，但其最底層缺少右邊若干節點
歪斜樹（Skewed Binary Tree）
完全沒有左/右節點
嚴格二叉樹（Strictly Binary Tree）
每個非終端節點均有非空的左右子樹
數組實作二叉樹
Left Index = Father Index * 2
Right Index = Father Index * 2 + 1
以一維數組建立二叉樹 = 建立一個二叉搜尋樹
可以是空集合，但若不是，則節點上一定要有一個鍵值
左子節點值<根節點；右子節點值>根節點
左右子樹本身也是搜尋樹
樹的每個節點值都不相同
static void Main(string[] args)
{
int[] data = new int[8] { 6, 3, 5, 9, 7, 8, 4, 2 };
int[] result = ConstructBinaryTreeByArray(data);
for (int i = 1; i < result.Length; i++)
{
Console.Write(result[i] + " ");
}
Console.WriteLine();
}
public static int[] ConstructBinaryTreeByArray(int[] data)
{
int[] tree = new int[data.Length * 2];
int treeIdx;
for (int i = 0; i < data.Length; i++)
{
for(treeIdx = 1; tree[treeIdx] != 0;)
{
if(data[i] > tree[treeIdx])
{
//Bigger than father
treeIdx = treeIdx * 2 + 1;
}
else
{
//Smaller than father
treeIdx = treeIdx * 2;
}
}
tree[treeIdx] = data[i];
}
return tree;
}
鏈表實作二叉樹
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
this.val = val;
left = null;
right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree(int root)
{
this.root = new TreeNode(root);
}
public void Add(int node)
{
TreeNode curr = root;
TreeNode newNode = new TreeNode(node);
while(true)
{
if(newNode.val >= curr.val)
{
if(curr.right == null)
{
curr.right = newNode;
return;
}
curr = curr.right;
}
else
{
if(curr.left == null)
{
curr.left = newNode;
return;
}
curr = curr.left;
}
}
}
}
二叉樹算法
前序/中序/後序遍歷
前：根 -> 左 -> 右
public void ForwardTraverse(TreeNode curr)
{
if (curr == null) { return; }
Console.WriteLine(curr.val);
ForwardTraverse(curr.left);
ForwardTraverse(curr.right);
}
中：左 -> 根 -> 右
public void MiddleTraverse(TreeNode curr)
{
if (curr == null) { return; }
MiddleTraverse(curr.left);
Console.WriteLine(curr.val);
MiddleTraverse(curr.right);
}
後：左 -> 右 -> 根
public void BackwardTraverse(TreeNode curr)
{
if (curr == null) { return; }
BackwardTraverse(curr.left);
BackwardTraverse(curr.right);
Console.WriteLine(curr.val);
}
二叉搜尋樹
一個二叉樹符合「每一何節點凡資料>左子節點且小於右小節點」，便可稱為二分樹。
二叉搜尋樹和二叉排序樹都是二分樹的一種
二叉搜尋樹和二叉排序樹是一體兩面，沒有分別，可以說是對二分樹的兩種操作方式
可以是空集合，但若不是，則節點上一定要有一個鍵值
左子節點值<根節點；右子節點值>根節點
左右子樹本身也是搜尋樹
樹的每個節點值都不相同
bool Finder(TreeNode curr, int target)
{
if(curr == null) { return false; }
else if(target == curr.val)
{
return true;
}
else if(target > curr.val)
{
return Finder(curr.right, target);
}
else
{
return Finder(curr.left, target);
}
}
二叉樹插入節點
if (!tree.Find(10))
{
tree.Add(10);
tree.Traverse(TraversalType.InOrder);
}
二叉樹刪除節點
如果刪除節點為葉節點，直接將其父樹指向它的引用置空
如果刪除節點只有一棵子樹，則將其父樹指向其子樹
如果刪除節點有兩個子樹，則可選擇令其父樹指向：
其左子樹中最右的葉節點
其右子樹中最左的葉節點
二叉排序樹
第一個輸入的資料作為樹根
之後的資料以遞歸的方式與樹根比較，比根節點小的置於左子樹，比根節點大的置於右子樹
對樹中序遍歷即可得出由小到大的結果
引線二叉樹
把節點中的空鏈結指向樹的其他節點，這些鏈結稱為「引線」
步驟：
中序遍歷二叉樹，將空鏈結改成引線
如果引線指向該節點的左鏈結，將該引線指到中序遍歷順序下的後一個節點
如果引線指向該節點的右鏈結，將該引線指到中序遍歷順序下的後一個節點
指向一個空節點，並將此空節點的右鏈結指向自己，空節點的左子樹是此引線二叉樹
引線二叉樹的結構
LBIT：左控制位元
LCHILD：左子樹鏈結
DATA：節點資料
RCHILD：右子樹鏈結
RBIT：右控制位元
如果LCHILD為正常指標，LBIT = 1；如果為引線，則=0
如果RCHILD為正常指標，RBIT = 1；如果為引線，則=0
優缺點
優點
中序遍歷不需要用Stack，而一般二叉樹需要
中序遍歷速度較快
避免鏈結閒置
任一節點都容易找出他的中序後繼者（右子樹最小）和中序前行者（左子樹最大）。
缺點
加入/刪除節點比一般二叉樹慢
引線子樹間不能共享
public class ThreadedNode
{
public int data, lbit, rbit;
public ThreadedNode lchild, rchild;
public ThreadedNode(int data)
{
this.data = data;
this.lbit = 0;
this.rbit = 0;
this.lchild = null;
this.rchild = null;
}
}
public class Threaded_Binary_Tree
{
//引線二元樹根節點
public ThreadedNode root;
public Threaded_Binary_Tree()
{
root = null;
}
public Threaded_Binary_Tree(int[] data)
{
foreach (var i in data)
{
AddNode(i);
}
}
public void AddNode(int val)
{
ThreadedNode newNode = new ThreadedNode(val);
ThreadedNode curr;
ThreadedNode parent;
ThreadedNode prev = new ThreadedNode(val);
int pos;
//設定起始節點
if(root == null)
{
root = newNode;
root.lchild = root;
root.rchild = null;
root.lbit = 0;
root.rbit = 1;
return;
}
//設定起始節點所指的節點
curr = root.rchild;
if(curr == null)
{
root.rchild = newNode;
newNode.lchild = root;
newNode.rchild = root;
return;
}
parent = root; //父節點是起始節點
pos = 0; //設定二叉樹的行進方向
while(curr != null)
{
if(curr.data > val)
{
if(pos != 1)
{
pos = -1;
prev = parent;
}
parent = curr;
if(curr.lbit == 1)
{
curr = curr.lchild;
}
else
{
curr = null;
}
}
else
{
if(pos != 1)
{
pos = 1;
prev = parent;
}
parent = curr;
if(curr.rbit == 1)
{
curr = curr.rchild;
}
else
{
curr = null;
}
}
if(parent.data > val)
{
parent.lbit = 1;
parent.lchild = newNode;
newNode.lchild = prev;
newNode.rchild = parent;
}
else
{
parent.rbit = 1;
parent.rchild = newNode;
newNode.lchild = parent;
newNode.rchild = prev;
}
return;
}
}
}
延伸二叉樹
任何一個二叉樹，若具有n個節點，則有n-1個非空鏈結，n+1個空鏈結。
在每一個空鏈結上加一個特定節點，稱為外節點。
其餘節點（不包括根節點）稱為內節點
該樹可被定義為「延伸二叉樹」。
外徑長 = 所有外節點到樹根距離的總和
內徑長 = 所有內節點到樹根距離的總和
如果每個外節點都有加權值（如搜尋機率等），則外徑長必須考慮相關加權值（加權外徑長）
霍夫曼樹
有n個權值（q1, q2 ….. qn），且構成一個有n個節點的二叉樹，每個節點外部節點權值為qi，則加權徑長度最小的稱為「最佳化二叉樹」（霍夫曼樹）
平衡樹（AVL樹）
二叉搜尋樹在加入資料後，有可能產生歪斜樹，使樹的高度增加，導致搜尋效率下降。
因此，需要通過保持二叉樹高度平衡，從而保證搜尋效率。
插入/刪除資料後，對二叉樹進行高度調整。
高度平衡樹條件：
左右子樹也是高度平衡樹
內部節點的左右子樹高度相差小於等於1