preface

Link up with the last Node file operation, specifically write a tree structure understanding and implementation, while deepening their understanding of tree structure data

What is a tree

  • Linear structure

Arrays, stacks, queues, by default, are linear;

  • Nonlinear structure

Trees are nonlinear structures. Common tree structures include binary trees and multi-fork trees (trees with more than two forks). Common tree structures include file directories, DOM structure, react virtual DOM, routing configuration, etc.

Common concepts of trees

  • Nodes:

    Root node, parent node, byte point, brother node

  • A tree:

    Left subtree, right subtree, the number of subtrees

  • Leaf node:

    Node of degree O (no subtree of its own)

  • Non-leaf node:

    A node with a non-zero degree (has its own subtree)

  • Depth of a node (a node) :

    The total number of nodes to pass through from the root node to the current child node

  • Node height:

    The total number of nodes to pass from the current node to the farthest leaf node

  • The number of layers of a tree:

    The height of the tree, the depth of the tree

The classification of the tree

  • Binary tree
  • Many tree

This paper deals only with binary trees

Binary tree implementation

  • Classic case: binary tree conversion of an array, the left subtree is a tree smaller than the root node, the right node is a tree larger than the root node

Code implementation

Spanning tree node

Class Node {constructor(element, parent) {// This. Element = element; // This. Parent = parent; // Parent this.left = null; this.right = null; }}Copy the code

Spanning tree

Constructor initializes the root node to null

Constructor () {// Default root = null this.root = null; }}Copy the code
  • Node to the add ()

Ideas:

  1. If the root Node is null new a Node and is the root Node
  2. The root node is not empty, while loop, set the current node as the root node, parent is the current node, compare the current node elment is less than the add input parameter to get the Boolean value of compare
  3. If compare is true, change the current node to the right subtree of the current node, or set the left subtree of the current node to the current node until the end of the loop returns the final compare and parent
  4. New Node(element, parent) : compare the right or left Node of the parent Node

Code implementation:

Add (element) {if (this.root === null) {// 1: if the root Node is null new a Node and the current Node is the root Node return (this.root = new Node(element));  } // update currentNode let currentNode = this.root; // let parent; let compare; while (currentNode) { compare = currentNode.element < element; parent = currentNode; CurrentNode = currentNode.right; currentNode = currentNode.right; } else {// true then the left is the root node currentNode = currentNode.left; } } //compare; // parent; Let node = new node (element, parent); if (compare) { parent.right = node; } else { parent.left = node; }}Copy the code

test

let tree = new Tree();
[10, 9, 8, 16, 22, 30, 20].forEach((item) => {
  tree.add(item);
});

console.dir(tree, { depth: 100 });
Copy the code

Test result (perfect)

Tree traversal

Depth-first traversal

  • The root node starts to traverse vertically
  • Use the diff algorithm of the virtual DOM in the React scenario

The first sequence traversal

  • Traverse the order root left and right
  • Code implementation
PreOderTraversal () {function traversal(node) {if (node === null) return; console.log(node.element); traversal(node.left); traversal(node.right); } traversal(this.root); }Copy the code
  • Execution Result:

In the sequence traversal

  • Traversal order left root right
  • Code implementation
InOderTraversal () {function traversal(node) {if (node === null) return; traversal(node.left); console.log(node.element); traversal(node.right); } traversal(this.root); }Copy the code
  • Execution Result:

After the sequence traversal

  • Traverse the order left and right roots
  • Code implementation
PostOderTraversal () {function traversal(node) {if (node === null) return; traversal(node.left); traversal(node.right); console.log(node.element); } traversal(this.root); }Copy the code
  • Execution Result:

Breadth-first traversal

  • The root node starts by traversing each level from left to right
  • Code implementation
LevelOrderTraversal (cb) {let stack = [this.root]; levelOrderTraversal(cb) {let stack = [this.root]; let index = 0; let currentNode; // console.log(" breadth-first traversal "); while ((currentNode = stack[index++])) { cb(currentNode); // console.log(currentNode.element); if (currentNode.left) { stack.push(currentNode.left); } if (currentNode.right) { stack.push(currentNode.right); }}}Copy the code
  • Application scenario: Binary tree flipping, ast tree operations in WebPack Operations on AST trees performed by plug-ins

Breadth-first traversal using scenario binary tree flipping

  • Code implementation
reverseTree(cb) { let stack = [this.root]; let index = 0; let currentNode; // console.log(" breadth-first traversal "); while ((currentNode = stack[index++])) { let temp = currentNode.left; currentNode.left = currentNode.right; currentNode.right = temp; if (currentNode.left) { stack.push(currentNode.left); } if (currentNode.right) { stack.push(currentNode.right); }}}Copy the code
  • The execution result

Depth first vs. breadth first

  1. There is no difference in depth-first traversal performance
  2. Depth-first traversal performs slightly worse than breadth-first traversal
  3. – Dom Diff does not compare breadth first to depth first – dom Diff does not compare breadth first to depth first – Dom Tree parsing is top – down For example, A1, A2 and A3 components at the same level should be executed first, otherwise it will cause hierarchy confusion. Finally: FROM the perspective of spatial complexity, I would like to say that the breadth first traversal retains all nodes and occupies a large space

The complete code

Class Node {constructor(element, parent) {// This. Element = element; this.parent = parent; this.left = null; this.right = null; }} class Tree {constructor() {// Default root = null this.root = null; } add(element) { if (this.root === null) { return (this.root = new Node(element)); } let currentNode = this.root; // let parent; let compare; while (currentNode) { compare = currentNode.element < element; parent = currentNode; If (compare) {currentNode = currentNode.right; } else { currentNode = currentNode.left; } } let node = new Node(element, parent); if (compare) { parent.right = node; } else { parent.left = node; }} // PreOderTraversal () {function traversal(node) {if (node === null) return; console.log(node.element); traversal(node.left); traversal( node.right); } traversal(this.root); } function traversal(node) {function traversal(node) {if (node === null) return; traversal(node.left); console.log(node.element); traversal(node.right); } traversal(this.root); } // postOderTraversal() {function traversal(node) {if (node === null) return; traversal(node.left); traversal(node.right); console.log(node.element); } traversal(this.root); } levelOrderTraversal(cb) {// r Let stack = [this.root]; let index = 0; let currentNode; // console.log(" breadth-first traversal "); while ((currentNode = stack[index++])) { cb(currentNode); // console.log(currentNode.element); if (currentNode.left) { stack.push(currentNode.left); } if (currentNode.right) { stack.push(currentNode.right); ReverseTree (cb) {}} reverseTree(cb) {let stack = [this.root]; let index = 0; let currentNode; // console.log(" breadth-first traversal "); while ((currentNode = stack[index++])) { let temp = currentNode.left; currentNode.left = currentNode.right; currentNode.right = temp; if (currentNode.left) { stack.push(currentNode.left); } if (currentNode.right) { stack.push(currentNode.right); } } } } let tree = new Tree(); [10, 9, 8, 16, 22, 30, 20].forEach((item) => { tree.add(item); }); tree.levelOrderTraversal console.dir(tree, { depth: 100 }); tree.preOderTraversal(); console.dir(tree, { depth: 100 }); tree.inOderTraversal(); tree.postOderTraversal(); Tree. LevelOrderTraversal ((node) => {// example: Webpack ast traversal node.element *= 2; // console.log(" element of current node ", node.element); }); console.dir(tree, { depth: 100 }); tree.reverseTree(); console.dir(tree, { depth: 100 });Copy the code

The last

Finally, if you find this article helpful, please remember to like three times oh, thank you very much