二叉树的存储结构和遍历

Hokori 6月7日

二叉树

存储结构

顺序存储结构

JS中用数组实现

优点

遍历简单

缺点

容易造成存储空间的浪费

链式存储结构

双链法

左子树该结点右子树
lchilddatarchild

缺点

频繁查找双亲或祖先不方便

class node{
    /**
     * @params {Object} val
     * @params {node} left
     * @params {node} right
     */
    constructor(val, left, right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

三链法

左子树该结点右子树双亲结点
lchildvalrchildparent

class node{
    /**
     * @params {Object} val
     * @params {node} left
     * @params {node} right
     * @params {node} parent
     */
    constructor(val, left, right, parent){
        this.val = val;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

递归算法

前序遍历(preoder traversal)

  • 若二叉树为空树则遍历结束

    1. 访问根节点
    2. 前序遍历根节点的左子树
    3. 前序遍历根节点的右子树
const preOrderTranversal = (root) => {
    console.log(root.val);
    preOrderTranversal(root.left);
    preOrderTranversal(root.right);
}

中序遍历(inorder traversal)

  • 若二叉树为空树则遍历结束

    1. 中序遍历根节点的左子树
    2. 访问根节点
    3. 中序遍历根节点的右子树
const inOrderTranversal = (root) => {
    inOrderTranversal(root.left);
    console.log(root.val);
    inOrderTranversal(root.right);
}

后序遍历(postorder traversal)

  • 若二叉树为空树则遍历结束

    1. 后序遍历根节点的左子树
    2. 后序遍历根节点的右子树
    3. 访问根节点
const postOrderTranversal = (root) => {
    postOrderTranversal(root.left);
    postOrderTranversal(root.right);
    console.log(root.val);
}

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;
}
icon_biggrin.pngicon_neutral.pngicon_twisted.pngicon_arrow.pngicon_eek.pngicon_smile.pngicon_sad.pngicon_cool.pngicon_evil.pngicon_mrgreen.pngicon_exclaim.pngicon_surprised.pngicon_razz.pngicon_rolleyes.pngicon_wink.pngicon_cry.pngicon_confused.pngicon_lol.pngicon_mad.pngicon_question.pngicon_idea.pngicon_redface.png
expand_less