乐趣区

关于javascript:二叉树相关-js描述

jiezi

起因

二叉树简直是面试过程中必问的知识点，大多数形容过程都是通过 C、C++、JAVA、python 等语言实现，这里用 js 语言实现下一下相似的性能，前端、nodejs 方向和全栈方向的同学能够作为参考。

示例

以下所有实现都是基于以下二叉树示例：

如图所示，建设过程应用 binarytree 这个库，代码如下：

const BinaryTree = require('binarytree');

let binaryTree = new BinaryTree('F');
let bNode = binaryTree.insert('B', 'left', binaryTree.root);
let aNode = binaryTree.insert('A', 'left', bNode);
let dNode = binaryTree.insert('D', 'right', bNode);
let cNode = binaryTree.insert('C', 'left', dNode);
let eNode = binaryTree.insert('E', 'right', dNode);
let gNode = binaryTree.insert('G', 'right', binaryTree.root);
let iNode = binaryTree.insert('I', 'right', gNode);
let hNode = binaryTree.insert('H', 'left', iNode);

DFS

深度遍历有前序、中序以及后序三种遍历办法，递归办法十分易懂，代码如下：

前序遍历：根结点 —> 左子树 —> 右子树 

function preorderDFS(root) {const nodeList = [];
  preorder(root, nodeList)
  return nodeList;

  function preorder(root, nodeList) {if (root !== null) {nodeList.push(root.data)
      preorder(root.left, nodeList);
      preorder(root.right, nodeList);
    }
  }
}

中序遍历：左子树 —> 根结点 —> 右子树 

function inorderDFS(root) {const nodeList = [];
  inorder(root, nodeList);
  return nodeList;

  function inorder(root, nodeList) {if (root !== null) {inorder(root.left, nodeList);
      nodeList.push(root.data);
      inorder(root.right, nodeList);
    }
  }
}

后序遍历：左子树 —> 右子树 —> 根结点 

function postorderDFS(root) {const nodeList = [];
  postorder(root, nodeList);
  return nodeList;

  function postorder(root, nodeList) {if (root !== null) {postorder(root.left, nodeList);
      postorder(root.right, nodeList);
      nodeList.push(root.data)
    }
  }
}

BFS

按档次遍历就能够，须要一个队列，根节点先退出队列。队列执行出队操作，出队元素有左孩子入队，没有则不论，有右孩子入队，没有则不论。而后持续以上操作，直到队列为空。

function BFS(root) {const q = [root];
  const nodeList = [];
  while (q.length > 0) {const node = q.pop();
    nodeList.push(node.data);
    if (node.left !== null) q.unshift(node.left);
    if (node.right !== null) q.unshift(node.right);
  }
  
  return nodeList;
}

蛇形打印

打印程序如图所示：

相似 BFS，然而又不同，能够用 BFS 的思维去思考。
前一层先打印的节点其孩子在下一层后打印，依照这个思路那么其孩子节点须要用栈进行存储。
前后两层，左右孩子的打印程序是相同的，因而咱们须要两个盏实现，一个盏存储奇数层节点入栈程序为先左孩子后右孩子，另一个盏存储偶数层节点入盏程序为先右孩子后左孩子。
假如 lrStack 存储奇数层节点，rlStack 存储偶数层节点：

  1. 根节点 F 为第一层，奇数层，因而，lrStack 盏入盏 F
  2. lrStack 出盏所有元素，即 F 出盏，同时因为下一层为偶数层，因而依照右孩子、左孩子的程序入盏 rlStack
  3. rlStack 出盏所有元素 B —> G，因为下一层为奇数层，因而依照左孩子、右孩子的程序入盏 lrStack
  4. lrStack 出盏所有元素 I —> D —> A，因为下一层为偶数层，因而依照右孩子、左孩子的程序入盏 rlStack
  5. rlStack 出盏所有元素 C —> E —> H，因为下一层曾经没有数据，完结

依照思路，代码如下：

function printBintryTree(root) {const lrStack = [];
  const rlStack = [];
  lrStack.push(root);
  while(lrStack.length > 0 || rlStack.length > 0) {if (lrStack.length > 0 && rlStack.length === 0) {while (lrStack.length > 0) {const tNode = lrStack.pop();
        console.log(tNode.data);
        if (tNode.right !== null) {rlStack.push(tNode.right);
        }
        if (tNode.left !== null) {rlStack.push(tNode.left);
        }
      }
    }
    if (rlStack.length > 0 && lrStack.length === 0) {while (rlStack.length > 0) {const tNode = rlStack.pop();
        console.log(tNode.data);
        if (tNode.left !== null) {lrStack.push(tNode.left);
        }
        if (tNode.right !== null) {lrStack.push(tNode.right);
        }
      }
    }
  }
}

示例调用 

// 蛇形打印
printBintryTree(binaryTree.root); // F B G I D A C E H
// 广度遍历
console.log(BFS(binaryTree.root)); // ['F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H']
// 深度遍历
console.log(preorderDFS(binaryTree.root)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
console.log(inorderDFS(binaryTree.root)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
console.log(postorderDFS(binaryTree.root)); // ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'];
退出移动版