Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to use recursive traversal and transform tree data in TypeScript". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

A friend asked me how to generate HTML from a tree's JSON array, using and to build page elements. So I simply drew a tree structure diagram.

Then write the corresponding simulation data (JavaScript object)

Const data = {name: "A", nodes: [{name: "B", nodes: [{name: "F"}]}, {name: "C"}, {name: "D", nodes: [{name: "G"}, {name: "H"} {name: "I", nodes: [{name: "J"}, {name: "K"}]}, {name: "E"}]}

* wrote a recursion to generate the tree structure of HTML. It was originally written in JavaScript ES6, but in order to show the data structure, here we use TypeScript to write:

Interface INode {name: string; nodes?: INode [];} function makeTree (roots: INode []): JQuery {function makeNode (node: INode): JQuery {const $div = $(") .text (node.name | |"); const $li = $("). Append ($div); if (node.nodes & node.nodes.length) {$li.append (makeNodeList (node.nodes)) } return $li;} function makeNodeList (nodes: INode []): JQuery {return nodes .map (child = > makeNode (child)) .reduce (($ul, $li) = > {return $ul.append ($li);}, $("));} return makeNodeList (roots);}

The effect is quite good.

Look at the source code (translated into JS): http://jsfiddle.net/y7bw4yj2/

Then the friend said he didn't understand. All right, let me start from the beginning.

Ergodic method

There are two ways to traverse tree data, as we all know: breadth traversal and depth traversal. In general, breadth traversal is implemented by queues, while depth traversal is more suitable for recursion.

Breadth traversal

The process of breadth traversal can be roughly understood from the diagram:

Prepare an empty queue

Put a root (single or multiple root) node in the queue

Remove a node from the queue

To process (such as printing) this node.

Check the children of the node and, if any, add them all to the queue in turn

Go back to step 3 and start processing until the queue is empty (processing is complete)

Function travelWidely (roots: INode []) {const queue: INode [] = [... roots]; while (queue.length) {const node = queue.shift ()!; / / print the node name and the number of its child nodes console.log (`${node.name} ${node.nodes & & node.nodes.length | | "}`) If (node.nodes & & node.nodes.length) {queue.push (.node.browse);} / / start traversing travelWidely ([data])

Const node = queue.shift ()!, back here! The suffix means to declare that its result is not undefined or null. This is a TypeScript syntax. Since .shift () returns undefined when there are no elements in the array, its return type is declared as INode | undefined. Since the slave logic can guarantee that .shift () will return a node object, use! The suffix ignores the undefined part of the type so that the type of node is deduced as INode.

What's a little harder to understand in the code is to note that the content and length of the queue are changing from time to time. If you want to use for instead of while loop, the node sequence number will change constantly because of .shift (), so I

< queue.length 这样的判断是错误的。 深度遍历 深度遍历是一个递归过程，递归一直是编程的难点。 递归是一个循环往复的处理过程，它有两个点需要注意： 递归调用点，递归调用自己(或另一个可能会调用自己的函数) 递归结束点，退出当前函数 以树节点为例，我们期望处理过程是处理(打印)一个树结点，即 printNode(node: INode)。那么它的 递归调用点：如果该节点有子节点，依次对子节点调用 printNode(children[i]) 递归结束点：处理完所有子节点(子节点数量是有限的，所以一定会结束) 用一段伪代码描述这一过程 function printNode(node: INode) { // 处理该节点 console.log(node.name); // 递归调用点：循环对子节点调用 printNode node.nodes!.forEach(child =>

PrintNode (child)); / / Recursive end point: loop completed, return}

The above two lines of code complete the recursion, but the situation is actually more complicated because you have to deal with entrances and fault tolerance.

/ / Note: single root or multiple roots are supported in the parameter. / / if only multiple roots are supported like travelWidely (single root is a special case), function travelDeeply (roots: INode | INode []) {function printNode (node: INode) {console.log (`${node.name} ${node.nodes & & root | | "}`) If (node.nodes & & node.nodes.length) {/ / recursively calls printNode node.nodes.forEach (child = > printNode (child)) on the child node;}} / / where printNode and node = > printNode (node) are equivalent (Array.isArray (roots)? Roots: [roots]) .forEach (printNode);} / / start traversing travelDeeply (data)

With regard to recursion, I happened to talk about generating data solutions on Mooc. com. If you are interested, you can have a look at it.

I haven't finished the tour yet.

Both of the above traverses have been covered, but we haven't finished yet-- because both traverses take printing as an example, and our goal is to generate a DOM tree. The difference between generating a DOM tree and pure print information is that we not only use node information, but also generate DOM returns from node information.

Deep traversal of the generation node

This time, let's start with deep traversal, because recursion is easier to implement. Recursion itself has hierarchical information, and each time it enters a recursive call point, it goes deeper, and each time it leaves a recursive end point, it decreases by one layer. So the algorithm itself can retain the structural information, and the corresponding code will be easier to implement. And at the beginning of this article, it has been implemented.

One thing to note is that the code uses two functions to complete the recursion process:

MakeNode handles a single node, which calls makeNodeList to process the list of child nodes

MakeNodeList traverses the list of nodes and calls makeNode to process them respectively.

The mutual calls between makeNode and makeNodeList form recursion, both of which are recursive call points, and there are also two recursive end points:

When the node processed by makeNode does not have child nodes, makeNodeList will not be called

When the loop in makeNodeList ends, makeNode is no longer called

Breadth traversal generation node

The process of breadth traversal is to flatten all the nodes into a queue, which is irreversible, in other words, we lose the tree structure information in the process. Then the DOM tree we are going to generate requires structural information-- therefore, we need to attach structural information to each node. Here we bind the generated DOM to the data node, and the DOM stores the structure information. To do this, you need to modify the node type

Interface INode {name: string; nodes?: INode []; dom: JQuery / / attach the generated DOM} function makeTreeWidely (roots: INode []): JQuery {/ / generated from a set of nodes, generated and attached for each node / / the structure information function makeUl (nodes: INode []) {return nodes .map (node = > {const $li = $(") .append ($(") .text (node.name | | ")) will be saved in the same time. Node.dom = $li; return $li;}) .reduce (($ul, $li) = > $ul.append ($li), $(""));} const $rootUl = makeUl (roots); const queue: INode [] = [. Roots]; while (queue.length) {const node = queue.shift ()! If (node.nodes & & node.nodes.length) {const $ul = makeUl (node.nodes); node.dom.append ($ul); queue.push (.node.ul);}} return $rootUl;}

Although the local function expression makeUl is defined here as in recursive traversal of printNode, there is no recursion because makeUl does not call itself, or a function that will call makeUl.

But the problem goes a little deeper, because the above code changes the original data. In general, we should try our best to avoid such side effects.

Breadth traversal generation node without side effects

/ / declare a new structure that combines INode and DOM. / / this structure will replace INode as the element type interface IDomNode {node: INode; dom: JQuery of the queue } function makeTreeWidely (roots: INode []): JQuery {/ / convert converts an array of nodes into an IDomNode array and / / does what makeUl did at the same time Return a $ul function convert (nodes: INode []) {const domNodes = nodes .map (node = > {const $li = $(") .append ($(") .text (node.name | | ")) Return {node, dom: $li};}); const $ul = domNodes .reduce (($ul, dn) = > $ul.append (dn.dom), $("")) / / return return {domNodes, $ul};} / parse the tuple, declare the variables queue and $rootUl, and assign the values of domNodes and $ul to the queue and $rootUl variables const {domNodes: queue, $ul: $rootUl} = convert (roots) While (queue.length) {const {node, dom} = queue.shift ()!; if (node.nodes & & node.nodes.length) {const {domNodes, $ul} = convert (node.nodes); dom.append ($ul); queue.push (.domNodes);} return $rootUl } look at the efficacy: how to use recursive traversal and transform tree data in http://jsfiddle.net/y7bw4yj2/1/"TypeScript, this is the end of the introduction. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.