二叉树基本概念及遍历

Posted by Nutlee on 2016-06-02

 

基本概念

节点的度:一个结点拥有的子树数目称为该结点的度。
二叉树深度:树中节点的最大层次
叶节点:度为0的节点, 即不拥有子树的

满二叉树: 特点:对称,除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
完全二叉树:若设二叉树的深度h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

遍历二叉树

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。

  • 前序( 先序 )遍历规则:根节点->左子树->右子树
    对于非空树从根节点开始,先根节点,然后对左子树进行 先根节点—>左子树—>右子树 前序遍历规则,以此类推。

  • 中序遍历规则:左子树->根节点->右子树
    对于非空树从根节点开始,先左子树,然后对左子树进行 先左子树—>根节点—>右子树 中序遍历规则,以此类推。
    计算中序遍历拥有比较简单直观的 投影法

  • 后序遍历规则:左子树->右子树->根节点
    对于非空树从根节点开始,先左子树,然后对左子树进行 先左子树—>右子树—>根节点 后序遍历规则,以此类推。

  • 层序遍历
    除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。(即一层一层遍历)


    例如:求下面树的三种遍历

    前序遍历:abdefgc
    中序遍历:debgfac
    后序遍历:edgfbca

    注意此题特殊在于e是右分支不要当做左分支。

算法分析

其中 focusNodeList 是用来存放遍历结果的数组,通过遍历访问该数组可以展示不同算法的遍历顺序。以下代码均经过验证,请点击 Demo 查看效果。

  • 先序( 前序 )

    • 递归

      1
      2
      3
      4
      5
      6
      7
      var preOrder0 = function (node) {
      if (node) {
      focusNodeList.push(node);
      preOrder0(node.children[0]);
      preOrder0(node.children[1]);
      }
      }
    • 非递归

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      var preOrder1 =function (node) {
      if (!node) {
      throw new Error('Empty Tree')
      }
      var stack=[]; //模拟栈
      stack.push(node);
      do{
      //pop() 后进先出
      if((node=stack.pop())!=null){ //出栈
      focusNodeList.push(node);
      stack.push(node.children[1]); //右子节点入栈
      stack.push(node.children[0]); //左子节点入栈
      }
      }while(!!stack.length);
      }
  • 中序

    • 递归

      1
      2
      3
      4
      5
      6
      7
      var inOrder0 = function (node) {
      if (node) {
      inOrder0(node.children[0]);
      focusNodeList.push(node);
      inOrder0(node.children[1]);
      }
      }
    • 非递归

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      var inOrder1 = function (node) {
      if (!node) {
      throw new Error('Empty Tree')
      }
      var stack = []
      while (stack.length !== 0 || node) {
      if (node) {
      stack.push(node)
      node = node.children[0];
      } else {
      node = stack.pop()
      focusNodeList.push(node);
      node = node.children[1];
      }
      }
      }
  • 后序

    • 递归

      1
      2
      3
      4
      5
      6
      7
      var postOrder0 = function (node) {
      if (node) {
      postOrder0(node.children[0]);
      postOrder0(node.children[1]);
      focusNodeList.push(node);
      }
      }
    • 非递归

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      /**
      * 后序 非递归 使用1个栈
      * @param {[type]} node [输入tree]
      *
      */
      var postOrder1 = function (node) {
      if (!node) {
      throw new Error('Empty Tree');
      }
      var stack = [];
      stack.push(node);
      var tmp = null;
      while (stack.length !== 0) {
      tmp = stack[stack.length - 1]
      if (tmp.children[0] && node !== tmp.children[0] && node !== tmp.children[1]) {
      stack.push(tmp.children[0]);
      } else if (tmp.children[1] && node !== tmp.children[1]) {
      stack.push(tmp.children[1]);
      } else {
      focusNodeList.push(stack.pop());
      node = tmp;
      }
      }
      }
      /**
      * 后序 非递归 使用两个栈
      * @param {[type]} node [输入tree]
      *
      */
      var postOrder1 = function (node) {
      if (node) {
      var s1 = []
      var s2 = []
      s1.push(node)
      while (s1.length !== 0) {
      node = s1.pop()
      s2.push(node)
      if (node.children[0]) {
      s1.push(node.children[0])
      }
      if (node.children[1]) {
      s1.push(node.children[1])
      }
      }
      while (s2.length !== 0) {
      focusNodeList.push(s2.pop());
      }
      }
      }

参考资料:
二叉树基本概念
二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现
javascript描述数据结构:二叉树的遍历和基本操作
JS中的二叉树遍历详解
遍历二叉树的九种算法