演算法建樹

A. 二叉樹的中序、前序、後序的遞歸、非遞歸遍歷演算法，應包含建樹的實現

#include "stdlib.h"
#include "iostream"
using namespace std;
#define ok 1
#define null 0
typedef char telemtype;
typedef struct bitnode
{telemtype data;<br> struct bitnode *lchild,*rchild;<br> }bitnode,*bitree;/* void visit(bitnode *p)
{printf("%c",p->data);<br> }*/
//先序建樹
bitree createbitree(void)
{char ch;bitnode *t;<br> scanf("%c",&ch);<br> if(ch=='#')<br> t=null;<br> else<br> {t=(bitnode *)malloc(sizeof(bitnode));<br> t->data=ch;<br> t->lchild=createbitree();<br> t->rchild=createbitree();<br> } return t;
}
//中序遞歸遍歷
void inorder(bitree T){
if(T)
{inorder(T->lchild);<br> printf("%c",T->data);<br> inorder(T->rchild);}
} //先序遞歸遍歷
void preorder(bitree T)
{if(T)<br> {<br> printf("%c",T->data);<br> preorder(T->lchild);<br> preorder(T->rchild);<br>}
}//後序遞歸遍歷
void Post_order(bitree T)
{if(T)<br> {<br> Post_order(T->lchild);<br> Post_order(T->rchild);<br> printf("%c",T->data);<br>}
}//先序非遞歸遍歷二叉樹
void PreTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{
cout<<p->data<<" ";
node[top]=p;
top++;
p=p->lchild; }
if(top>0){top--;p=node[top];p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}//中序非遞歸遍歷二叉樹
void InTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{

node[top]=p;
top++;
p=p->lchild; }
if(top>0){
cout<<p->data<<" ";
top--;p=node[top];
p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}//後序非遞歸遍歷二叉樹
void PostTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{
cout<<p->data<<" ";
node[top]=p;
top++;
p=p->lchild; }
if(top>0){top--;p=node[top];p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}void leaf(bitree T,int &count)
{
if(T)
{
if(T->lchild==NULL&&T->rchild==NULL)
count++;
else
{
leaf(T->lchild,count);
leaf(T->rchild,count);
}
}}
int deepth(bitree T)
{
int leftdep,rightdep;
if(!T)
return 0;
else
{
leftdep=deepth(T->lchild);
rightdep=deepth(T->rchild);
if(leftdep>rightdep)
return leftdep+1;
else
return rightdep+1;
}

}
void level_order(bitree T)
{}
//輸出菜單
void print_menu(){
cout<<"請選擇你要進行的操作："<<endl;
cout<<"1.先序建立二叉樹! "<<" "<<"2.中序遞歸遍歷二叉樹!"<<endl;
cout<<"3.先序遞歸遍歷二叉樹!"<<" "<<"4.後序遞歸遍歷二叉樹!"<<endl;
cout<<"5.先序非遞歸遍歷二叉樹!"<<" "<<"6.中序非遞歸遍歷二叉樹!"<<endl;
cout<<"7.後序非遞歸遍歷二叉樹!"<<" "<<"8.求葉子結點個數!"<<endl;
cout<<"9.求樹的深度! "<<" "<<"10.層序遍歷二叉樹!"<<endl;
cout<<"11.退出!"<<endl;
}
void main()
{
bitree t;
int k,c=0,d;
print_menu();
cin>>k;
while(k!=11)
{

switch(k)
{
case 1:
cout<<"請輸入樹的先序字元序列，空樹以#表示"<<endl;
t=createbitree();
cout<<"建樹成功"<<endl;
break;
case 2:
inorder(t);
break;
case 3:
preorder(t);
break;
case 4:
Post_order(t);
break;
case 5:
PreTree(t);
break;
case 6:
InTree(t);
break;
case 7:
PostTree(t);
break;
case 8:
leaf(t,c);
cout<<"葉子結點數為："<<c<<endl;
break;
case 9:
d=deepth(t);
cout<<"樹的深度為："<<d<<endl;
break;
case 10:
level_order(t);
break;
case 11:
exit(0);
default:
cout<<"不存在您選擇的項，請重新輸入："<<endl;
} //switch
print_menu();
cin>>k;
}//while
}//main

B. 給定權3,4,5,6,7,8,9,試用演算法構造一棵最優二叉樹,畫出這棵樹並計算出...

建樹步驟：
3
4
5
6
7
8
9
7
5
6
7
8
9
7
11
7
8
9
11
14
8
9
11
14
17
25
17
42
建立後的最優二叉樹是這樣滴：(線和箭頭自己連一下吧汗~）
42
25
17
11
14
8
9
5
6
7
7
3
4
權(WPL):3*4+4*4+5*3+6*3+7*3+8*2+9*2=116

C. PyOD主要演算法（KNN、IForest 和 MCD）的原理及使用

https://pyod.readthedocs.io/en/latest/pyod.models.html

Python Outlier Detection（PyOD）是當下最流行的Python異常檢測工具庫（toolkit）。該工具庫的主要亮點包括：

對於特徵空間中的一個樣本，如果與之最相似的（即特徵空間中距離最近的）k個樣本中的大多數都屬於某一類別，則該樣本的分類結果也是這個類別。

https://www.cnblogs.com/lesleysbw/p/6074662.html

① 什麼叫做KD_tree

K：K鄰近查詢中的k；D：空間是D維空間（Demension）tree：二叉樹

② 建樹過程

K-D tree的建立就是分裂空間的過程

首先，我們對整個區間 [1 , 15] 建樹：先計算區間中所有點在第一維（也就是 x 坐標）上的方差：
平均值 ： ave_1 =5.4
方差 ： varance_1 =9.04
再計算區間中所有點在第二維（也就是 y 坐標）上的方差：
平均值：ave_2 =6.8
方差：varance_2 =10.96
明顯看見，varance_2 > varance_1 ，那麼我們在本次建樹中， 分裂方式 ：split_method =2 ， 再將所有的點按照第2維的大小 從小到大排序 ，得到了新的點的一個排列：
（4,2） （1,4） （5,8） （7,9） （10,11）
取中間的點作為分裂點 sorted_mid =（5，8）作為根節點，再把區間 [1 , 2] 建成左子樹 , [4 , 5] 建成右子樹，此時，直線 ： y = 8 將平面分裂成了兩半，前面一半給左兒子，後面一半給了右兒子，如圖：

建左子樹 [1, 3] 的時候可以發現，這時候 第一維的方差大 ，分裂方式就是1 ，把區間 [ 1, 2 ] 中的點按照 第一維 的大小，從小到大排序 ，取 中間點（1,4） 根節點，再以區間 [ 2, 2] 建立右子樹 得到節點 （4,2）

建右子樹 [4 , 5] 的時候可以發現，這時還是第一維的方差大， 於是，我們便得到了這樣的一顆二叉樹 也就是 K-D tree，它把平面分成了如下的小平面， 使得每個小平面中最多有一個點 ：

③ 查詢過程：
查詢，其實相當於我們要將一個點「添加」到已經建好的 K-D tree 中，但並不是真的添加進去，只是找到他應該 處於的子空間 即可，所以查詢就顯得簡單的。
每次在一個區間中查詢的時候，先看這個區間的 分裂方式 是什麼，也就是說，先看這個區間是按照哪一維來分裂的，這樣如果這個點對應的那一維上面的值比根節點的小，就在根節點的左子樹上進行查詢操作，如果是大的話，就在右子樹上進查詢操作。
每次回溯到了根節點（也就是說，對他的一個子樹的查找已經完成了）的時候，判斷一下，以該點為圓心，目前 找到的最小距離為半徑 ，看是否和分裂區間的那一維所構成的平面相交，要是相交的話，最近點可能還在另一個子樹上，所以還要再查詢另一個子樹，同時，還要看能否用根節點到該點的距離來更新我們的最近距離。為什麼是這樣的，我們可以用一幅圖來說明：

https://github.com/YinghongZhang/BallTree-MIPS

① 原理
為了改進KDtree的二叉樹樹形結構，並且沿著笛卡爾坐標進行劃分的低效率，ball tree將在一系列嵌套的超球體上分割數據。也就是說： 使用超球面而不是超矩形劃分區域 。雖然在構建數據結構的花費上大過於KDtree，但是在 高維 甚至很高維的數據上都表現的很高效。
球樹遞歸地將數據劃分為 由質心C和半徑r定義的節點 ，使得節點中的每個點都位於由r和C定義的超球內。通過使用三角不等式來減少鄰居搜索的候選點數量。

② 建樹過程
選擇一個距離當前圓心最遠的觀測點A，和距離A最遠的觀測點B，將圓中所有離這兩個點最近的觀測點都賦給這兩個簇的中心，然後計算每一個簇的中心點和包含所有其所屬觀測點的最小半徑。對包含n個觀測點的超圓進行分割，只需要線性的時間。

③ 查詢
使用ball tree時，先自上而下找到包含target的葉子結點（c, r），從此結點中找到離它最近的觀測點。這個距離就是 最近鄰的距離的上界 。檢查它的 兄弟結點 中是否包含比這個上界更小的觀測點。方法是： 如果目標點距離兄弟結點的圓心的距離d > 兄弟節點所在的圓半徑R + 前面的上界r，則這個兄弟結點不可能包含所要的觀測點 。否則，檢查這個兄弟結點是否包含符合條件的觀測點。

用一個隨機超平面來切割數據空間, 直到每個子空間裡面只有一個數據點為止。切割次數的多少可用來區分異常。

https://www.jianshu.com/p/5af3c66e0410

iForest 由t個iTree孤立樹組成，每個iTree是一個二叉樹，其實現步驟如下：

可以看到d最有可能是異常，因為其最早就被孤立（isolated）了。

獲得t個iTree之後，iForest 訓練就結束，然後我們可以用生成的iForest來評估測試數據了。對於一個訓練數據x，我們令其遍歷每一棵iTree，然後計算x最終落在每個樹第幾層（x在樹的高度），得到x在每棵樹的高度平均值。獲得每個測試數據的average path length後，我們可以設置一個閾值，低於此閾值的測試數據即為異常。
IForest具有線性時間復雜度。
IForest不適用於特別高維的數據。

最小協方差行列式（Minimum Covariance Determinant）

https://max.book118.com/html/2017/1217/144650709.shtm

論文《Minimum covariance determinant and extensions》中有更詳細描述。

論文《A Fast Algorithm for the Minimum Covariance Determinant Estimator》有更詳細描述。

D. 編寫遞歸演算法，求二叉樹的結點個數和葉子數

00DLR(liuyu *root) /*中序遍歷 遞歸函數*/
{if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}
DLR(root->lchild);
DLR(root->rchild); }
return(0);
}
法二：
int LeafCount_BiTree(Bitree T)//求二叉樹中葉子結點的數目
{
if(!T) return 0; //空樹沒有葉子
else if(!T->lchild&&!T->rchild) return 1; //葉子結點
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子樹的葉子數加
上右子樹的葉子數
}//LeafCount_BiTree

註：上機時要先建樹！例如實驗二的方案一。
① 列印葉子結點值（並求總數）
思路：先建樹，再從遍歷過程中列印結點值並統計。

E. 哈夫曼演算法中頻度建樹應該用什麼排序

最優二叉樹概念

1．樹的路徑長度
樹的路徑長度是從樹根到樹中每一結點的路徑長度之和。在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。

2．樹的帶權路徑長度(Weighted Path Length of Tree，簡記為WPL)
結點的權：在一些應用中，賦予樹中結點的一個有某種意義的實數。
結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積。
樹的帶權路徑長度(Weighted Path Length of Tree)：定義為樹中所有葉結點的帶權路徑長度之和，通常記為：
【數據結構】樹：哈夫曼樹及其應用 - 八月照相館 - 八月照相館
其中：

n表示葉子結點的數目
wi和li分別表示葉結點ki的權值和根到結點ki之間的路徑長度。
樹的帶權路徑長度亦稱為樹的代價。

3．最優二叉樹或哈夫曼樹
在權為wl，w2，…，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小(即代價最小)的二叉樹稱為最優二叉樹或哈夫曼樹。
【例】給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹(還有許多棵)，它們的帶權路徑長度分別為：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
其中(c)樹的WPL最小，可以驗證，它就是哈夫曼樹。
【數據結構】樹：哈夫曼樹及其應用 - 八月照相館 - 八月照相館

注意：
① 葉子上的權值均相同時，完全二叉樹一定是最優二叉樹，否則完全二叉樹不一定是最優二叉樹。
② 最優二叉樹中，權越大的葉子離根越近。
③ 最優二叉樹的形態不唯一，WPL最小

構造最優二叉樹

1．哈夫曼演算法
哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法，故稱其為哈夫曼演算法。其基本思想是：
(1)根據給定的n個權值wl，w2，…，wn構成n棵二叉樹的森林F={T1，T2，…，Tn}，其中每棵二叉樹Ti中都只有一個權值為wi的根結點，其左右子樹均空。
(2)在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，將這兩棵樹合並成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，並將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。
(3)對新的森林F重復(2)，直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。
用哈夫曼演算法構造哈夫曼樹的過程見【動畫演示】。
注意：
① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子
② n個葉子的哈夫曼樹要經過n-1次合並，產生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。
③ 哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。

2．哈夫曼樹的存儲結構及哈夫曼演算法的實現
（1） 哈夫曼樹的存儲結構
用一個大小為2n-1的向量來存儲哈夫曼樹中的結點，其存儲結構為：
#define n 100 //葉子數目
#define m 2*n-1//樹中結點總數
typedef struct { //結點類型
float weight； //權值，不妨設權值均大於零
int lchild，rchild，parent； //左右孩子及雙親指針
}HTNode；
typedef HTNode HuffmanTree[m]； //HuffmanTree是向量類型
注意：
因為C語言數組的下界為0，故用-1表示空指針。樹中某結點的lchild、rchild和parent不等於-1時，它們分別是該結點的左、右孩子和雙親結點在向量中的下標。
這里設置parent域有兩個作用：其一是使查找某結點的雙親變得簡單；其二是可通過判定parent的值是否為-1來區分根與非根結點。

（2）哈夫曼演算法的簡要描述
在上述存儲結構上實現的哈夫曼演算法可大致描述為(設T的類型為HuffmanTree)：
(1)初始化
將T[0．．m-1]中2n-1個結點里的三個指針均置為空(即置為-1)，權值置為0。
(2)輸人
讀人n個葉子的權值存於向量的前n個分量(即T[0．．n-1])中。它們是初始森林中n個孤立的根結點上的權值。
(3)合並
對森林中的樹共進行n-1次合並，所產生的新結點依次放人向量T的第i個分量中(n≤i≤m-1)。每次合並分兩步：
①在當前森林T[0．．i-1]的所有結點中，選取權最小和次小的兩個根結點[p1]和T[p2]作為合並對象，這里0≤p1，p2≤i-1。
② 將根為T[p1]和T[p2]的兩棵樹作為左右子樹合並為一棵新的樹，新樹的根是新結點T[i]。具體操作：
將T[p1]和T[p2]的parent置為i，
將T[i]的lchild和rchild分別置為p1和p2
新結點T[i]的權值置為T[p1]和T[p2]的權值之和。
注意：
合並後T[pl]和T[p2]在當前森林中已不再是根，因為它們的雙親指針均已指向了T[i]，所以下一次合並時不會被選中為合並對象。