二叉树

存储结构

顺序存储结构

JS中用数组实现

image-20200602105407681

结言:递归算法简洁精练、可读性好、易理解,但其执行效率较低

非递归算法

用栈来实现

前序遍历(preoder traversal)

从二叉树的根结点开始,沿左子树一直深入到最左下结点时止,在深入的过程中访问所遇到的结点,并把所遇到结点的非空右孩子进栈;当左子树结点全部处理完之后,从栈顶退出当前最近访问过结点的右孩子,再按上述过程遍历该结点的右子树;如此重复,直到栈空时为止。

const preOrderTraversal = (root) => {
    if(root===null){
        return [];
    }
    let nodestack = [];
    let res = [];
    //根节点入栈
    nodestack.push(root);
    while(nodestack.length>0){
        //栈顶结点出栈
        let node = nodestack.pop();
        //进入结果集
        res.push(node.val);
        
        //右、左子树进栈
        if(node.right){
            nodestack.push(node.right);
        }
        if(node.left){
            nodestack.push(node.left);
        }
    }
    return res;
}

中序遍历(inorder traversal)

是沿左子树向下搜索的过程中先将所遇结点进栈,待遍历完左子树返回时从栈顶退出结点并访问,然后再遍历右子树。

const inOrderTraversal = (root) => {
    if (!root) {
        return [];
    }
    let res = [];
    let nodestack = [];
    while (root || nodestack.length) {
        while (root) {
            nodestack.push(root);
            root = root.left;
        }
        root = nodestack.pop();
        root.val && res.push(root.val);
        root = root.right
    }
    return res
}

后序遍历(postorder traversal)

当搜索指针指向一个结点时不能马上访问,需要先遍历左子树,所以结点需要进栈保存;

当遍历完左子树返回再次搜索到该结点时还不能进行访问,还需要遍历其右子树,所以结点需要再次进栈保存;

即一个结点在两次进栈两次出栈之后才能访问。为了区别某一结点指针的两次出栈,需设置一标志flag同结点同时进出栈,flag定义如下:

image-20200605095630313

Continue...............

层次遍历(level-order traversal)

是从根结点开始访问,然后访问它的左孩子和右孩子,接下来是它左孩子的左孩子和右孩子,右孩子的左孩子和右孩子……

  1. 首先将根节点入队列
  2. 当队列不空,从队列中取出队头结点访问它,并在其左右孩子非空时,把它的左孩子和右孩子结点依次入队列
  3. 反复执行(2),直到队列为空时止
const levelOrderTraversal = (root) => {
  let queue = [];
  let result = [];
  if (root !== null) {
    queue.push(root);
  }
  while(queue.length !== 0) {
    let level = [];
    let len = queue.length;
    for (var i = 0; i < len; i ++) {
      let currentNode = queue.shift();
      //访问每层结点
      level.push(currentNode.val);
        
      //下一层结点入队
      if (currentNode.left !== null) queue.push(currentNode.left);
      if (currentNode.right !== null) queue.push(currentNode.right);
    }
    //每层遍历结束
    result.push(level);
  }
  //返回一个二维数组
  return result;
}