算法篇

算法的研究可参考: 算法通关之路

深度优先遍历（DFS）

栈实现 （非递归），右子树优先，先进后出

const root = {
  name: 'A',
  children: [
    {
      name: 'X',
      children: [
        {
          name: 'X1',
          children: []
        },
        {
          name: 'X2',
          children: []
        },
        {
          name: 'X3',
          children: []
        }

      ]
    },
    {
      name: 'Y',
      children: [
        {
          name: 'Y1',
          children: []
        },
        {
          name: 'Y2',
          children: [
            {
              name: 'M1',
              children: []
            },
            {
              name: 'M2',
              children: []
            }
          ]
        },
        {
          name: 'Y3',
          children: []
        }
      ]
    },
    {
      name: 'Z',
      children: [
        {
          name: 'Z1',
          children: []
        },
        {
          name: 'Z2',
          children: []
        },
        {
          name: 'Z3',
          children: []
        }
      ]
    }
  ]
}

const stack = [root]
while(stack.length) {
  current = stack.pop()
  console.log(`访问: ${current.name}`)
  if (current.children) {
    current.children.forEach(e => stack.push(e))
  }
}

function dfs(current) {
  if (current) {
    console.log(`访问: ${current.name}`)
    if (current.children) {
      current.children.forEach(e => dfs(e))
    }
  }
}

dfs(root)

const queue = [root]
while(queue.length) {
  current = queue.pop()
  console.log(`访问: ${current.name}`)
  if (current.children) {
    current.children.forEach(e => queue.unshift(e))
  }
}

const data = [2, 1, 5, 6, 3, 9]

// quick sort
function quick_sort(data, begin, end) {
  if (begin < end) {
    let key = data[begin];
    let left = begin;
    let right = end;
    while (left < right) {
      while (left < right && data[right] > key) {
        right--;
      }
      if (left < right) {
        data[left] = data[right]
        left++;
      }
      while(left < right && data[left] < key) {
        left++;
      }
      if (left < right) {
        data[right] = data[left];
        right--;
      }
    }
    data[left] = key;
    quick_sort(data, begin, left - 1);
    quick_sort(data, left + 1, end);
  }
}

quick_sort(data, 0, data.length - 1);

console.log(data)