golang遞歸樹形,golang 尾遞歸

本文目錄一覽：

• 1、golang如何創建目錄
• 2、golang變量(二)——map和slice詳解
• 3、怎麼將數據庫中存的樹轉化為樹形列表
• 4、怎麼用遞歸實現1-10的求和 golang
• 5、golang結構體組合與「多態」 2021-08-06
• 6、Linq To Sql 如何實現遞歸查詢 樹形結構

golang如何創建目錄

golang中關於目錄與文件名等操作都在os這個包中，具體的創建目錄都是通過Mkdir和MkdirAll這2個函數來實現的，這兩個函數用法一致

os.Mkdir(dirName string, perm FileMode)

dirName即要創建的目錄(文件夾路徑)，可以是絕對路徑，也可以是相對路徑(相對於GOPATH)

perm表示創建的目錄的權限，如0777(讀r權限值為4,寫權限w值為2,執行權限x值為1)

如：我要在/data/program/goapp這個目錄下創建一個golang這個子目錄，示例如下:

package main

import (

   “os”

   “fmt”

)

func main() {

   err := os.Mkdir(“/data/program/goapp/golang”, 0666)

   if err != nil {

      fmt.Println(err)

   }

}

註：Mkdir和MkdirAll的區別

Mkdir創建目錄，它的父級目錄必須是存在的，不然創建會失敗

MkdirAll可以遞歸創建目錄，即只要根目錄存在即可，如下：

err := os.MkdirAll(“/data/program/goapp/golang/test/hello”, 0766)

if err != nil {

   fmt.Println(err)

}

本例中:/data/program/goapp是已經存在的目錄，而子目錄golang/test/hello是不存在，此時要使用MkdirAll來創建

golang變量(二)——map和slice詳解

衍生類型，interface{} , map, [] ，struct等

map類似於java的hashmap，python的dict，php的hash array。

常規的for循環，可以用for k,v :=range m {}. 但在下面清空有一個坑注意：

著名的map[string]*struct 副本問題

結果：

Go 中不存在引用傳遞，所有的參數傳遞都是值傳遞，而map是等同於指針類型的，所以在把map變量傳遞給函數時，函數對map的修改，也會實質改變map的值。

slice類似於其他語言的數組（list，array），slice初始化和map一樣，這裡不在重複

除了Pointer數組外，len表示使用長度，cap是總容量，make([]int, len, cap)可以預申請 比較大的容量，這樣可以減少容量拓展的消耗，前提是要用到。

cap是計算切片容量，len是計算變量長度的，兩者不一樣。具體例子如下：

結果：

分析：cap是計算當前slice已分配的容量大小，採用的是預分配的夥伴算法（當容量滿時，拓展分配一倍的容量）。

append是slice非常常用的函數，用於添加數據到slice中，但如果使用不好，會有下面的問題：

預期是[1 2 3 4 5 6 7 8 9 10]， [1 2 3 4 5 6 7 8 9 10 11 12]，但實際結果是：

注意slice是值傳遞，修改一下：

輸出如下：

== 只能用於判斷常規數據類型，無法使用用於slice和map判斷，用於判斷map和slice可以使用reflect.DeepEqual，這個函數用了遞歸來判斷每層的k，v是否一致。

當然還有其他方式，比如轉換成json，但小心有一些異常的bug，比如html編碼，具體這個json問題，待後面在分析。

怎麼將數據庫中存的樹轉化為樹形列表

樹狀結構的數據保存在數據庫中的常用方法有一下兩種：

1、鄰接表(adjacency list model)

2、預排序遍歷樹算法(modified preorder tree traversal algorithm)

用一下的例子討論這兩種方法的差異：

現有一棵樹如下：

鄰接表模式：

這種模式我們經常用到，很多的教程和書中也介紹過。我們通過給每個節點增加一個屬性 parent 來表示這個節點的父節點從而將整個樹狀結構通過平面的表描述出來。根據這個原則，例子中的數據可以轉化成如下的表:

我們看到 Pear 是Green的一個子節點，Green是Fruit的一個子節點。而根節點’Food’沒有父節點。 為了簡單地描述這個問題， 這個例子中只用了name來表示一個記錄。 在實際的數據庫中，你需要用數字的id來標示每個節點，數據庫的表結構大概應該像這樣：id, parent_id, name, description。

以下是代碼：

?php

// $parent is the parent of the children we want to see

// $level is increased when we go deeper into the tree,

// used to display a nice indented tree

function display_children($parent, $level)

{

// 獲得一個 父節點 $parent 的所有子節點

$result = mysql_query(‘SELECT name FROM tree ‘.

‘WHERE parent=”‘.$parent.'”;’);

// 顯示每個子節點

while ($row = mysql_fetch_array($result))

{

// 縮進顯示節點名稱

echo str_repeat(‘ ‘,$level).$row[‘name’].”n”;

//再次調用這個函數顯示子節點的子節點

display_children($row[‘name’], $level+1);

}

}

?

對整個結構的根節點（Food）使用這個函數就可以打印出整個多級樹結構，由於Food是根節點它的父節點是空的，所以這樣調用: display_children(”,0)。將顯示整個樹的內容：

Food

Fruit

Red

Cherry

Yellow

Banana

Meat

Beef

Pork

如果你只想顯示整個結構中的一部分，比如說水果部分，就可以這樣調用：display_children(‘Fruit’,0);

幾乎使用同樣的方法我們可以知道從根節點到任意節點的路徑。比如 Cherry 的路徑是　”Food ; Fruit ; Red”。 為了得到這樣的一個路徑我們需要從最深的一級”Cherry”開始， 查詢得到它的父節點”Red”把它添加到路徑中， 然後我們再查詢Red的父節點並把它也添加到路徑中，以此類推直到最高層的”Food”

以下是代碼：

?php

// $node 是那個最深的節點

function get_path($node)

{

// 查詢這個節點的父節點

$result = mysql_query(‘SELECT parent FROM tree ‘.

‘WHERE name=”‘.$node.'”;’);

$row = mysql_fetch_array($result);

// 用一個數組保存路徑

$path = array();

// 如果不是根節點則繼續向上查詢

// (根節點沒有父節點)

if ($row[‘parent’]!=”)

{

// the last part of the path to $node, is the name

// of the parent of $node

$path[] = $row[‘parent’];

// we should add the path to the parent of this node

// to the path

$path = array_merge(get_path($row[‘parent’]), $path);

}

// return the path

return $path;

}

?

如果對”Cherry”使用這個函數：print_r(get_path(‘Cherry’))，就會得到這樣的一個數組了：

Array

(

[0] =; Food

[1] =; Fruit

[2] =; Red

)

接下來如何把它打印成你希望的格式，就是你的事情了。

缺點：

這種方法很簡單，容易理解，好上手。但是也有一些缺點。主要是因為運行速度很慢，由於得到每個節點都需要進行數據庫查詢，數據量大的時候要進行很多查詢才能完成一個樹。另外由於要進行遞歸運算，遞歸的每一級都需要佔用一些內存所以在空間利用上效率也比較低。

預排序遍歷樹算法

現在讓我們看一看另外一種不使用遞歸計算，更加快速的方法，這就是預排序遍歷樹算法(modified preorder tree traversal algorithm) 這種方法大家可能接觸的比較少，初次使用也不像上面的方法容易理解，但是由於這種方法不使用遞歸查詢算法，有更高的查詢效率。

我們首先將多級數據按照下面的方式畫在紙上，在根節點Food的左側寫上 1 然後沿着這個樹繼續向下 在 Fruit 的左側寫上 2 然後繼續前進，沿着整個樹的邊緣給每一個節點都標上左側和右側的數字。最後一個數字是標在Food 右側的 18。 在下面的這張圖中你可以看到整個標好了數字的多級結構。（沒有看懂？用你的手指指着數字從1數到18就明白怎麼回事了。還不明白，再數一遍，注意移動你的手指）。

這些數字標明了各個節點之間的關係，”Red”的號是3和6，它是 “Food” 1-18 的子孫節點。 同樣，我們可以看到 所有左值大於2和右值小於11的節點 都是”Fruit” 2-11 的子孫節點

這樣整個樹狀結構可以通過左右值來存儲到數據庫中。繼續之前，我們看一看下面整理過的數據表。

注意：由於”left”和”right”在 SQL中有特殊的意義，所以我們需要用”lft”和”rgt”來表示左右字段。 另外這種結構中不再需要”parent”字段來表示樹狀結構。也就是 說下面這樣的表結構就足夠了。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

看到了吧，只要一個查詢就可以得到所有這些節點。為了能夠像上面的遞歸函數那樣顯示整個樹狀結構，我們還需要對這樣的查詢進行排序。用節點的左值進行排序：

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

那麼某個節點到底有多少子孫節點呢？很簡單，子孫總數=(右值-左值-1)/2

descendants = (right – left – 1) / 2 ，如果不是很清楚這個公式，那就去翻下書，我們在上數據結構寫的很清楚！

添加同一層次的節點的方法如下：

LOCK TABLE nested_category WRITE;

SELECT @myRight := rgt FROM nested_category WHERE name = ‘Cherry’;

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt @myRight;

UPDATE nested_category SET lft = lft + 2 WHERE lft @myRight;

INSERT INTO nested_category(name, lft, rgt) VALUES(‘Strawberry’, @myRight + 1, @myRight + 2);

UNLOCK TABLES;

添加樹的子節點的方法如下：

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft FROM nested_category WHERE name = ‘Beef’;

UPDATE nested_category SET rgt = rgt + 2 WHERE rgt @myLeft;

UPDATE nested_category SET lft = lft + 2 WHERE lft @myLeft;

INSERT INTO nested_category(name, lft, rgt) VALUES(‘charqui’, @myLeft + 1, @myLeft + 2);

UNLOCK TABLES;

每次插入節點之後都可以用以下SQL進行查看驗證：

SELECT CONCAT( REPEAT( ‘ ‘, (COUNT(parent.name) – 1) ), node.name) AS name

FROM nested_category AS node,

nested_category AS parent

WHERE node.lft BETWEEN parent.lft AND parent.rgt

GROUP BY node.name

ORDER BY node.lft;

刪除節點的方法，稍微有點麻煩是有個中間變量,如下：

LOCK TABLE nested_category WRITE;

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt – lft + 1

FROM nested_category WHERE name = ‘Cherry’;

DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt – @myWidth WHERE rgt @myRight;

UPDATE nested_category SET lft = lft – @myWidth WHERE lft @myRight;

UNLOCK TABLES;

這種方式就是有點難的理解，但是適合數據量很大規模使用，查看所有的結構只需要兩條SQL語句就可以了，在添加節點和刪除節點的時候略顯麻煩，不過相對於效率來說還是值得的。

怎麼用遞歸實現1-10的求和 golang

1、打出主函數defs(n)：ifn=1。

2、在打出條件函數return1else：result=n+s(n-1)return.result。

3、最後結尾返回函數的值result=s(10)print(result)。

golang結構體組合與「多態」 2021-08-06

如：

核心思想就是， 外層實現接口，通過遞歸嵌套將被實現的接口實例置於內層，從而達到外層定義，內層使用的效果 ：

BaseBase和Derived都是外層結構體，在它們這一層實現了F2()。ori_impl_1以及ori_impl_2都是外層結構體實現的B接口實例，置於內層完成調用

struct中的字段可以不用給名稱，這時稱為匿名字段。匿名字段的名稱強制和類型相同。例如：

如果struct中嵌套的struct類型是自己的指針類型，可以用來生成鏈表或二叉樹等數據結構

例如，定義一個單鏈表數據結構

Linq To Sql 如何實現遞歸查詢 樹形結構

–構造測試數據： 只作演示用

CREATE TABLE [dbo].[Tim_LinqTable](

[Id] int PRIMARY KEY IDENTITY(1,1) NOT NULL,

[Name] [varchar](50) NOT NULL,

[Parent] int NOT NULL,

)

GO

INSERT INTO [Tim_LinqTable]

SELECT ‘A’,0 UNION ALL

SELECT ‘A1’,1 UNION ALL

SELECT ‘A2’,1 UNION ALL

SELECT ‘B1’,2 UNION ALL

SELECT ‘B2’,3 UNION ALL

SELECT ‘C1’,4 UNION ALL

SELECT ‘C2’,4 UNION ALL

SELECT ‘D1’,5 UNION ALL

SELECT ‘D2’,5 UNION ALL

SELECT ‘D3’,5

GO

WITH temp

AS

(

SELECT * FROM [Tim_LinqTable] WHERE Parent = 3

UNION ALL

SELECT m.* FROM [Tim_LinqTable] AS m

INNER JOIN temp AS child ON m.Parent = child.Id

)

SELECT * FROM temp

GO

–查詢 Parent=3 的所有子數據結果如下:

Id Name Parent

———– ————————————————– ———–

5 B2 3

8 D1 5

9 D2 5

10 D3 5

(4 row(s) affected)

//好，下邊來看看用C#怎麼實現上邊的SQL語句吧：

void Main()

{

var query=GetClassID(3);

Console.WriteLine(“Id\tName\tParent”);

query.ToList().ForEach(q=Console.WriteLine(“{0}\t{1}\t{2}”,q.Id,q.Name,q.Parent));

/*

Id Name Parent

5 B2 3

8 D1 5

9 D2 5

10 D3 5

*/

}

public IEnumerableTim_LinqTable GetClassID(int p_id)

{

var query = from c in this.Tim_LinqTables

where c.Parent == p_id

select c;

return query.ToList().Concat(query.ToList().SelectMany(t = GetClassID(t.Id)));

}