前端樹遞歸

⑴ java使用遞歸實現樹形結構

sql">

inserttb_menu(id,name,parent)(640000000000,北京市,0);
inserttb_menu(id,name,parent)(640100000000,昌平區,1);
inserttb_menu(id,name,parent)(640101000000,霍營,2);
inserttb_menu(id,name,parent)(640101001000,回龍觀東大街,3);

添加一個節點屬性， 根據數據不同代表的地位不同，0就代表父節點 ，1是0的子節點，2是1的子節點，以此類推。

⑵ 求jsp中如何實現遞歸樹

你可以用一些JS框架, 比如extjs, 有現成的樹控制項, 你把數據組織成json格式的,就可以顯示了

⑶ js 遞歸樹

用jquery easyui~ 把它當json數據源給tree就可以顯示。
網址：http://www.jeasyui.com/demo/main/index.php?plugin=Tree&theme=default&dir=ltr&pitem=
望採納~

⑷ 請給出樹的遞歸定義。

樹的定義
樹（tree）是包含n（n>0）個結點的有窮集合，其中：

（1）每個元素稱為結點（node）；

（2）有一個特定的結點被稱為根結點或樹根（root）。

（3）除根結點之外的其餘數據元素被分為m（m≥0）個互不相交的結合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹也可以這樣定義：樹是有根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關系構成的。集合中的元素稱為樹的結點，所定義的關系稱為父子關系。父子關系在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。
我們可以形式地給出樹的遞歸定義如下:
單個結點是一棵樹，樹根就是該結點本身。
設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱n1,n2,..,nk為結點n的子樹。
空集合也是樹，稱為空樹。空樹中沒有結點

⑸ JTree，如何用遞歸演算法構建樹

public void addChild(DefaultMutableTreeNode fatherNode,int fatherId) {
List<Map>list=codeservices.getAssetCode( fatherId);
for(Map map:list){
DefaultMutableTreeNode child=new DefaultMutableTreeNode((String)map.get("TYPENAME"));
int id=Integer.parseInt((String)map.get("TYPEID"));
fatherNode.add(child);
addChild(child,id);
}
}

其中list是從資料庫獲取的所有節點，fatherNode是根節點，fatherid是父id，後面的id是自身節點id

⑹ 如何用遞歸寫一個簡單的樹形結構示例

模式要點

CharacterComposite 是一個抽象類，定義了所有容器類或葉節點的介面，容器應當實現的功能有：獲取子組件、對子組件進行計數、定義組件的格式化輸出規則。Sentence(句子) 和 Word (單詞)都屬於容器，而 Character (字母)則屬於葉節點，因為字母中無法再添加子組件了，它是層次結構中的最末端。

EnglishWord 組件前應當輸出一個空格，EnglishSentence 組件後應當輸出一個「.」，ChineseSentence 組件後應當輸出一個「。」等。

Word 作為 Sentence 的子容器，Character 作為 Word 的子組件，屬於葉節點。

Writer 為句子生成器，各個組件及子組件均由它負責填充，最終形成一個完成的結構。

效果

⑺ 樹的遞歸演算法

答案是正確的啊。
if(root)就是如果root!=0，這里root是一個指針，指向結構體struct node的指針，第一次進入函數它就是指向根節點A的指針
運行步驟：
如果指向A的指針不為空(不為0),列印'A',
遞歸調用函數指向A的左孩子節點
如果指向B的指針不為空(不為0),列印'B',
遞歸調用函數指向B的左孩子節點
如果指向C的指針不為空(不為0),列印'C',
遞歸調用函數指向C的左孩子節點
由於C的左孩子節點為空，所以本次遞歸traversal(root->lchild)結束，回到上一層遞歸中即從C的左孩子節點回到C中，然後執行traversal(root->lchild)這一句下面一句，列印出'C'
然後遞歸調用traversal(root->rchild);指向C的右孩子節點
如果指向E的指針不為空(不為0),列印'E',
然後再遞歸指向E的左孩子節點，為空再返回到E中，再次列印出'E',然後再指向E的右孩子節點，為空，E的遞歸結束返回上一層遞歸即C中，然後C也到達末尾結束返回上一層遞歸B中，然後執行traversal(root->lchild)這一句下面一句，列印出'B'
然後遞歸調用traversal(root->rchild);指向B的右孩子節點
......
如此不斷進入某個節點的子節點操作後再從子節點返回父節點，層層進入再層層向上返回，從而遍歷樹中各個節點，最終得出結果：
A B C C E E B A D F F D G G

⑻ 如何用PyTorch實現遞歸神經網路

從 Siri 到谷歌翻譯，深度神經網路已經在機器理解自然語言方面取得了巨大突破。這些模型大多數將語言視為單調的單詞或字元序列，並使用一種稱為循環神經網路（recurrent neural network/RNN）的模型來處理該序列。但是許多語言學家認為語言最好被理解為具有樹形結構的層次化片語，一種被稱為遞歸神經網路（recursive neural network）的深度學習模型考慮到了這種結構，這方面已經有大量的研究。雖然這些模型非常難以實現且效率很低，但是一個全新的深度學習框架 PyTorch 能使它們和其它復雜的自然語言處理模型變得更加容易。

雖然遞歸神經網路很好地顯示了 PyTorch 的靈活性，但它也廣泛支持其它的各種深度學習框架，特別的是，它能夠對計算機視覺（computer vision）計算提供強大的支撐。PyTorch 是 Facebook AI Research 和其它幾個實驗室的開發人員的成果，該框架結合了 Torch7 高效靈活的 GPU 加速後端庫與直觀的 Python 前端，它的特點是快速成形、代碼可讀和支持最廣泛的深度學習模型。

開始 SPINN

鏈接中的文章（https://github.com/jekbradbury/examples/tree/spinn/snli）詳細介紹了一個遞歸神經網路的 PyTorch 實現，它具有一個循環跟蹤器（recurrent tracker）和 TreeLSTM 節點，也稱為 SPINN——SPINN 是深度學習模型用於自然語言處理的一個例子，它很難通過許多流行的框架構建。這里的模型實現部分運用了批處理（batch），所以它可以利用 GPU 加速，使得運行速度明顯快於不使用批處理的版本。

SPINN 的意思是堆棧增強的解析器-解釋器神經網路（Stack-augmented Parser-Interpreter Neural Network），由 Bowman 等人於 2016 年作為解決自然語言推理任務的一種方法引入，該論文中使用了斯坦福大學的 SNLI 數據集。

該任務是將語句對分為三類：假設語句 1 是一幅看不見的圖像的准確標題，那麼語句 2（a）肯定（b）可能還是（c）絕對不是一個准確的標題？（這些類分別被稱為蘊含（entailment）、中立（neutral）和矛盾（contradiction））。例如，假設一句話是「兩只狗正跑過一片場地」，蘊含可能會使這個語句對變成「戶外的動物」，中立可能會使這個語句對變成「一些小狗正在跑並試圖抓住一根棍子」，矛盾能會使這個語句對變成「寵物正坐在沙發上」。

特別地，研究 SPINN 的初始目標是在確定語句的關系之前將每個句子編碼（encoding）成固定長度的向量表示（也有其它方式，例如注意模型（attention model）中將每個句子的每個部分用一種柔焦（soft focus）的方法相互比較）。

數據集是用句法解析樹（syntactic parse tree）方法由機器生成的，句法解析樹將每個句子中的單詞分組成具有獨立意義的短語和子句，每個短語由兩個詞或子短語組成。許多語言學家認為，人類通過如上面所說的樹的分層方式來組合詞意並理解語言，所以用相同的方式嘗試構建一個神經網路是值得的。下面的例子是數據集中的一個句子，其解析樹由嵌套括弧表示：

( ( The church ) ( ( has ( cracks ( in ( the ceiling ) ) ) ) . ) )

這個句子進行編碼的一種方式是使用含有解析樹的神經網路構建一個神經網路層 Rece，這個神經網路層能夠組合詞語對（用詞嵌入（word embedding）表示，如 GloVe）、 和/或短語，然後遞歸地應用此層（函數），將最後一個 Rece 產生的結果作為句子的編碼：

X = Rece(「the」, 「ceiling」)
Y = Rece(「in」, X)
... etc.

但是，如果我希望網路以更類似人類的方式工作，從左到右閱讀並保留句子的語境，同時仍然使用解析樹組合短語？或者，如果我想訓練一個網路來構建自己的解析樹，讓解析樹根據它看到的單詞讀取句子？這是一個同樣的但方式略有不同的解析樹的寫法：

The church ) has cracks in the ceiling ) ) ) ) . ) )

或者用第 3 種方式表示，如下：

WORDS: The church has cracks in the ceiling .
PARSES: S S R S S S S S R R R R S R R

我所做的只是刪除開括弧，然後用「S」標記「shift」，並用「R」替換閉括弧用於「rece」。但是現在可以從左到右讀取信息作為一組指令來操作一個堆棧（stack）和一個類似堆棧的緩沖區（buffer），能得到與上述遞歸方法完全相同的結果：

1. 將單詞放入緩沖區。
2. 從緩沖區的前部彈出「The」，將其推送（push）到堆棧上層，緊接著是「church」。
3. 彈出前 2 個堆棧值，應用於 Rece，然後將結果推送回堆棧。
4. 從緩沖區彈出「has」，然後推送到堆棧，然後是「cracks」，然後是「in」，然後是「the」，然後是「ceiling」。
5. 重復四次：彈出 2 個堆棧值，應用於 Rece，然後推送結果。
6. 從緩沖區彈出「.」，然後推送到堆棧上層。
7. 重復兩次：彈出 2 個堆棧值，應用於 Rece，然後推送結果。
8. 彈出剩餘的堆棧值，並將其作為句子編碼返回。

我還想保留句子的語境，以便在對句子的後半部分應用 Rece 層時考慮系統已經讀取的句子部分的信息。所以我將用一個三參數函數替換雙參數的 Rece 函數，該函數的輸入值為一個左子句、一個右子句和當前句的上下文狀態。該狀態由神經網路的第二層（稱為循環跟蹤器（Tracker）的單元）創建。Tracker 在給定當前句子上下文狀態、緩沖區中的頂部條目 b 和堆棧中前兩個條目 s1\s2 時，在堆棧操作的每個步驟（即，讀取每個單詞或閉括弧）後生成一個新狀態：

context[t+1] = Tracker(context[t], b, s1, s2)

容易設想用你最喜歡的編程語言來編寫代碼做這些事情。對於要處理的每個句子，它將從緩沖區載入下一個單詞，運行跟蹤器，檢查是否將單詞推送入堆棧或執行 Rece 函數，執行該操作；然後重復，直到對整個句子完成處理。通過對單個句子的應用，該過程構成了一個大而復雜的深度神經網路，通過堆棧操作的方式一遍又一遍地應用它的兩個可訓練層。但是，如果你熟悉 TensorFlow 或 Theano 等傳統的深度學習框架，就知道它們很難實現這樣的動態過程。你值得花點時間回顧一下，探索為什麼 PyTorch 能有所不同。

圖論

圖 1：一個函數的圖結構表示

深度神經網路本質上是有大量參數的復雜函數。深度學習的目的是通過計算以損失函數（loss）度量的偏導數（梯度）來優化這些參數。如果函數表示為計算圖結構（圖 1），則向後遍歷該圖可實現這些梯度的計算，而無需冗餘工作。每個現代深度學習框架都是基於此反向傳播（backpropagation）的概念，因此每個框架都需要一個表示計算圖的方式。

在許多流行的框架中，包括 TensorFlow、Theano 和 Keras 以及 Torch7 的 nngraph 庫，計算圖是一個提前構建的靜態對象。該圖是用像數學表達式的代碼定義的，但其變數實際上是尚未保存任何數值的佔位符（placeholder）。圖中的佔位符變數被編譯進函數，然後可以在訓練集的批處理上重復運行該函數來產生輸出和梯度值。

這種靜態計算圖（static computation graph）方法對於固定結構的卷積神經網路效果很好。但是在許多其它應用中，有用的做法是令神經網路的圖結構根據數據而有所不同。在自然語言處理中，研究人員通常希望通過每個時間步驟中輸入的單詞來展開（確定）循環神經網路。上述 SPINN 模型中的堆棧操作很大程度上依賴於控制流程（如 for 和 if 語句）來定義特定句子的計算圖結構。在更復雜的情況下，你可能需要構建結構依賴於模型自身的子網路輸出的模型。

這些想法中的一些（雖然不是全部）可以被生搬硬套到靜態圖系統中，但幾乎總是以降低透明度和增加代碼的困惑度為代價。該框架必須在其計算圖中添加特殊的節點，這些節點代表如循環和條件的編程原語（programming primitive），而用戶必須學習和使用這些節點，而不僅僅是編程代碼語言中的 for 和 if 語句。這是因為程序員使用的任何控制流程語句將僅運行一次，當構建圖時程序員需要硬編碼（hard coding）單個計算路徑。

例如，通過詞向量（從初始狀態 h0 開始）運行循環神經網路單元（rnn_unit）需要 TensorFlow 中的特殊控制流節點 tf.while_loop。需要一個額外的特殊節點來獲取運行時的詞長度，因為在運行代碼時它只是一個佔位符。

# TensorFlow
# (this code runs once, ring model initialization)
# 「words」 is not a real list (it』s a placeholder variable) so
# I can』t use 「len」
cond = lambda i, h: i < tf.shape(words)[0]
cell = lambda i, h: rnn_unit(words[i], h)
i = 0
_, h = tf.while_loop(cond, cell, (i, h0))

基於動態計算圖（dynamic computation graph）的方法與之前的方法有根本性不同，它有幾十年的學術研究歷史，其中包括了哈佛的 Kayak、自動微分庫（autograd）以及以研究為中心的框架 Chainer和 DyNet。在這樣的框架（也稱為運行時定義（define-by-run））中，計算圖在運行時被建立和重建，使用相同的代碼為前向通過（forward pass）執行計算，同時也為反向傳播（backpropagation）建立所需的數據結構。這種方法能產生更直接的代碼，因為控制流程的編寫可以使用標準的 for 和 if。它還使調試更容易，因為運行時斷點（run-time breakpoint）或堆棧跟蹤（stack trace）將追蹤到實際編寫的代碼，而不是執行引擎中的編譯函數。可以在動態框架中使用簡單的 Python 的 for 循環來實現有相同變數長度的循環神經網路。

# PyTorch (also works in Chainer)
# (this code runs on every forward pass of the model)
# 「words」 is a Python list with actual values in it
h = h0
for word in words:
h = rnn_unit(word, h)

PyTorch 是第一個 define-by-run 的深度學習框架，它與靜態圖框架（如 TensorFlow）的功能和性能相匹配，使其能很好地適合從標准卷積神經網路（convolutional network）到最瘋狂的強化學習（reinforcement learning）等思想。所以讓我們來看看 SPINN 的實現。

代碼

在開始構建網路之前，我需要設置一個數據載入器（data loader）。通過深度學習，模型可以通過數據樣本的批處理進行操作，通過並行化（parallelism）加快訓練，並在每一步都有一個更平滑的梯度變化。我想在這里可以做到這一點（稍後我將解釋上述堆棧操作過程如何進行批處理）。以下 Python 代碼使用內置於 PyTorch 的文本庫的系統來載入數據，它可以通過連接相似長度的數據樣本自動生成批處理。運行此代碼之後，train_iter、dev_iter 和 test_itercontain 循環遍歷訓練集、驗證集和測試集分塊 SNLI 的批處理。

from torchtext import data, datasets
TEXT = datasets.snli.ParsedTextField(lower=True)
TRANSITIONS = datasets.snli.ShiftReceField()
LABELS = data.Field(sequential=False)train, dev, test = datasets.SNLI.splits(
TEXT, TRANSITIONS, LABELS, wv_type='glove.42B')TEXT.build_vocab(train, dev, test)
train_iter, dev_iter, test_iter = data.BucketIterator.splits(
(train, dev, test), batch_size=64)

你可以在 train.py中找到設置訓練循環和准確性（accuracy）測量的其餘代碼。讓我們繼續。如上所述，SPINN 編碼器包含參數化的 Rece 層和可選的循環跟蹤器來跟蹤句子上下文，以便在每次網路讀取單詞或應用 Rece 時更新隱藏狀態；以下代碼代表的是，創建一個 SPINN 只是意味著創建這兩個子模塊（我們將很快看到它們的代碼），並將它們放在一個容器中以供稍後使用。

import torchfrom torch import nn
# subclass the Mole class from PyTorch』s neural network package
class SPINN(nn.Mole):
def __init__(self, config):
super(SPINN, self).__init__()
self.config = config self.rece = Rece(config.d_hidden, config.d_tracker)
if config.d_tracker is not None:
self.tracker = Tracker(config.d_hidden, config.d_tracker)

當創建模型時，SPINN.__init__ 被調用了一次；它分配和初始化參數，但不執行任何神經網路操作或構建任何類型的計算圖。在每個新的批處理數據上運行的代碼由 SPINN.forward 方法定義，它是用戶實現的方法中用於定義模型向前過程的標准 PyTorch 名稱。上面描述的是堆棧操作演算法的一個有效實現，即在一般 Python 中，在一批緩沖區和堆棧上運行，每一個例子都對應一個緩沖區和堆棧。我使用轉移矩陣（transition）包含的「shift」和「rece」操作集合進行迭代，運行 Tracker（如果存在），並遍歷批處理中的每個樣本來應用「shift」操作（如果請求），或將其添加到需要「rece」操作的樣本列表中。然後在該列表中的所有樣本上運行 Rece 層，並將結果推送回到它們各自的堆棧。

def forward(self, buffers, transitions):
# The input comes in as a single tensor of word embeddings;
# I need it to be a list of stacks, one for each example in
# the batch, that we can pop from independently. The words in
# each example have already been reversed, so that they can
# be read from left to right by popping from the end of each
# list; they have also been prefixed with a null value.
buffers = [list(torch.split(b.squeeze(1), 1, 0))
for b in torch.split(buffers, 1, 1)]
# we also need two null values at the bottom of each stack,
# so we can from the nulls in the input; these nulls
# are all needed so that the tracker can run even if the
# buffer or stack is empty
stacks = [[buf[0], buf[0]] for buf in buffers]
if hasattr(self, 'tracker'):
self.tracker.reset_state()
for trans_batch in transitions:
if hasattr(self, 'tracker'):
# I described the Tracker earlier as taking 4
# arguments (context_t, b, s1, s2), but here I
# provide the stack contents as a single argument
# while storing the context inside the Tracker
# object itself.
tracker_states, _ = self.tracker(buffers, stacks)
else:
tracker_states = itertools.repeat(None)
lefts, rights, trackings = [], [], []
batch = zip(trans_batch, buffers, stacks, tracker_states)
for transition, buf, stack, tracking in batch:
if transition == SHIFT:
stack.append(buf.pop())
elif transition == REDUCE:
rights.append(stack.pop())
lefts.append(stack.pop())
trackings.append(tracking)
if rights:
reced = iter(self.rece(lefts, rights, trackings))
for transition, stack in zip(trans_batch, stacks):
if transition == REDUCE:
stack.append(next(reced))
return [stack.pop() for stack in stacks]

在調用 self.tracker 或 self.rece 時分別運行 Tracker 或 Rece 子模塊的向前方法，該方法需要在樣本列表上應用前向操作。在主函數的向前方法中，在不同的樣本上進行獨立的操作是有意義的，即為批處理中每個樣本提供分離的緩沖區和堆棧，因為所有受益於批處理執行的重度使用數學和需要 GPU 加速的操作都在 Tracker 和 Rece 中進行。為了更干凈地編寫這些函數，我將使用一些 helper（稍後將定義）將這些樣本列表轉化成批處理張量（tensor），反之亦然。

我希望 Rece 模塊自動批處理其參數以加速計算，然後解批處理（unbatch）它們，以便可以單獨推送和彈出。用於將每對左、右子短語表達組合成父短語（parent phrase）的實際組合函數是 TreeLSTM，它是普通循環神經網路單元 LSTM 的變型。該組合函數要求每個子短語的狀態實際上由兩個張量組成，一個隱藏狀態 h 和一個存儲單元（memory cell）狀態 c，而函數是使用在子短語的隱藏狀態操作的兩個線性層（nn.Linear）和將線性層的結果與子短語的存儲單元狀態相結合的非線性組合函數 tree_lstm。在 SPINN 中，這種方式通過添加在 Tracker 的隱藏狀態下運行的第 3 個線性層進行擴展。

圖 2：TreeLSTM 組合函數增加了第 3 個輸入（x，在這種情況下為 Tracker 狀態）。在下面所示的 PyTorch 實現中，5 組的三種線性變換（由藍色、黑色和紅色箭頭的三元組表示）組合為三個 nn.Linear 模塊，而 tree_lstm 函數執行位於框內的所有計算。圖來自 Chen et al. (2016)。

⑼ javascript如何用遞歸寫一個簡單的樹形結構

vartree=[
{name:'node1'},
{name:'node2',children:[{name:'node-2-1'},{name:'node2-2'}]},
{name:'node3',children:[{name:'node-3-1',children:[{name:'node3-1-1'}]},{name:'node3-2'}]}
];

varrender=functionrender(tree){
if(!tree)returnnull

varul=document.createElement('ul');
tree.forEach(({name,children})=>{
varli=document.createElement('li')
varlabel=document.createElement('span');label.innerText=name;
li.appendChild(label);
varsub=render(children);
sub&&li.appendChild(sub);
ul.append(li);
})
returnul
};

document.body.innerHTML='';
document.body.appendChild(render(tree));