What is a tree?

An abstract model of hierarchical data

1. Common trees in front-end work include: DOM tree, cascading selection, tree control…

2. There is no tree in JS, but you can build a tree with Object and Array

{
  value: "",
  label: "",
	children: [
    {
      value: "",
      label: "",
      children: []
    }
  ]
}
Copy the code

3. Common operations of trees: depth/breadth first traversal, middle first and order first traversal

What is depth/breadth first traversal?

Depth-first traversal: Search as deep a branch of the tree as possible

Depth-first traversal process

1. Accessing the root node
2. Children of root node are traversed depth-first one by one

(recursive)

​

Code implementation

const tree = {
  val: "a".children: [{val: "b".children: [{val: "d".children: []}, {val: "e".children: [],},],}, {val: "c".children: [{val: "f".children: []}, {val: "g".children: [],},],},],};Depth-first traversal
const dfs = (root) = > {
    console.log(root.val);
    root.children.forEach((child) = > {dfs(child)});
}

dfs(tree);
Copy the code

Breadth-first traversal: Visits the node closest to the root node first

Breadth-first traversal process

1. Create a queue and queue the root node
2. Take the team leader out of the team and visit
3. Put the children in the team one by one
4. Repeat steps 2 and 3 until the queue is empty

​

Code implementation

const tree = {
  val: "a".children: [{val: "b".children: [{val: "d".children: []}, {val: "e".children: [],},],}, {val: "c".children: [{val: "f".children: []}, {val: "g".children: [],},],},],};// width first traversal
const bfs = (root) = > {
    const q = [root];
    while(q.length > 0) {
      const n = q.shift();
      console.log(n.val);
      n.children.forEach(child= > {
        q.push(child);
      })
    }
    
}

bfs(tree);
Copy the code

Three, the order of binary tree traversal

Binary tree definition

Each node in the tree can have a maximum of two child nodes

Object is commonly used to simulate binary trees in JS

const binaryTree = {
  val: 1.left: {
    val : 2.left: null.right: null
  },
  right: {
    val: 3.left: null.right: null}}Copy the code

Sequential traversal: root left and right

1. Accessing the root node
2. Preemptive traversal of the left subtree of the root node
3. Preemptive traversal of the right subtree of the root node

Recursive version of the code implementation

const bt = {
    val: 50.left: {
      val: 10.left: {
        val: 5.left: null.right: null,},right: {
        val: 15.left: null.right: null,}},right: {
      val: 70.left: {
        val: 60.left: null.right: null,},right: {
        val: 80.left: null.right: null,}}}; The first sequence traversalconst preorder = (root) = > {
    if(! root) {return };
    console.log(root.val);
    preorder(root.left);
    preorder(root.right);
}
// 50 10 5 15 70 60 80 

preorder(bt);
Copy the code

Non-recursive version of the code implementation

const bt = {
    val: 50.left: {
      val: 10.left: {
        val: 5.left: null.right: null,},right: {
        val: 15.left: null.right: null,}},right: {
      val: 70.left: {
        val: 60.left: null.right: null,},right: {
        val: 80.left: null.right: null,}}};const preorder = (root) = > {
    if(! root) {return; }
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        console.log(n.val);
        if (n.right) stack.push(n.right);
        if(n.left) stack.push(n.left); }};// 50 10 5 15 70 60 80 

preorder(bt);
Copy the code

Middle order traversal: left root right

1. Middle order traversal of the left subtree of the root node
2. Accessing the root node
3. Middle order traversal is performed on the right subtree of the root node

Recursive version of the code implementation

const bt = {
    val: 56.left: {
      val: 22.left: {
        val: 10.left: null.right: null,},right: {
        val: 30.left: null.right: null,}},right: {
      val: 81.left: {
        val: 77.left: null.right: null,},right: {
        val: 92.left: null.right: null,}}}; In the sequence traversalconst inorder = (root) = > {
    if(! root) {return; }
    inorder(root.left);
    console.log(root.val);
    inorder(root.right);
};

// 10 22 30 56 77 81 92

inorder(bt);
Copy the code

Non-recursive version of the code implementation

const bt = {
    val: 56.left: {
      val: 22.left: {
        val: 10.left: null.right: null,},right: {
        val: 30.left: null.right: null,}},right: {
      val: 81.left: {
        val: 77.left: null.right: null,},right: {
        val: 92.left: null.right: null,}}};const inorder = (root) = > {
    if(! root) {return; }
    const stack = [];
    let p = root;
    while (stack.length || p) {
        while (p) {
            stack.push(p);
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val); p = n.right; }};// 10 22 30 56 77 81 92

inorder(bt);
Copy the code

​

Post-order traversal: left and right roots

1. A post-order traversal of the left subtree of the root node is performed
2. A post-order traversal is performed on the right subtree of the root node
3. Accessing the root node

Recursive version of the code implementation

const bt = {
    val: 23.left: {
      val: 16.left: {
        val: 3.left: null.right: null,},right: {
        val: 22.left: null.right: null,}},right: {
      val: 45.left: {
        val: 37.left: null.right: null,},right: {
        val: 99.left: null.right: null,}}};// after the sequence traversal
const postorder = (root) = > {
    if(! root) {return; }
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
};

// 3 22 16 37 99 45 23

postorder(bt);
Copy the code

Non-recursive version of the code implementation

const bt = {
    val: 23.left: {
      val: 16.left: {
        val: 3.left: null.right: null,},right: {
        val: 22.left: null.right: null,}},right: {
      val: 45.left: {
        val: 37.left: null.right: null,},right: {
        val: 99.left: null.right: null,}}};const postorder = (root) = > {
    if(! root) {return; }
    const outputStack = [];
    const stack = [root];
    while (stack.length) {
        const n = stack.pop();
        outputStack.push(n);
        if (n.left) stack.push(n.left);
        if (n.right) stack.push(n.right);
    }
    while(outputStack.length){
        const n = outputStack.pop();
        console.log(n.val); }}; postorder(bt);Copy the code