最近在出題目，必須弄出一顆隨機的樹。
我一開始只想到一個錯誤的方法: 將數字從$1$到$n$丟入一個陣列$A$，然後將他們打亂，從$A_1$連到$A_n$。
很明顯這是一棵樹，但是這只有一條鍊==
後來又想了一個: 選取一個數字當根，從集合裡面找出$k$個點，加入到根的子節點中，之後dfs，重複這個動作。
同樣的，這個方法也有漏洞，由於沒有限制深度，所以第一個子樹會很深，一點都不像是隨機的。
而加上限制深度後，有時候會無法將所有點都排上去，不過限制深度不失為一個好方法，但是與”隨機”還是有點差距。
如果改成bfs呢?
選取一個數字當根，從集合裡面找出$k$個點，加入到根的子節點中以及queue中，再從queue中拿出點，之後，重複這個動作。
還是有一個漏洞，因為放入queue的順序是有序的，所以一樣會跟dfs的結果一樣，不過這個比較好解決，直接在queue裡面shuffle就好了。
這樣複雜度只有$O(n)$
在洗澡時又想出了一個方法，不過複雜度比較高。
將每個點賦予兩個隨機數字$(x,y)$，分別灑在平面上，$n^2$建邊，距離當權值，接著選取最中心的點做根，再用最小生成樹的方法來做成樹即可。
複雜度$O(n^2)$，也沒有比較快。但是感覺比較帥(笑
寫這篇文章時發現只要將第一個方法改良一下就行了，從那些未使用的點中選取$k$個，做成一條鍊，從樹集合中挑出一個點，接上剛剛的鍊就好。
複雜度$O(n)$
至於賦值的部分，可以依需求直接random在陣列上，或是因應樹的結構dfs動態賦值。
11.5.20更新
普呂弗序列，這個更適合用來建樹。