二叉树遍历

二叉树的遍历是指从根节点出发，按照某种顺序依次访问所有节点，而且只访问一次，二叉树的遍历方式很多，如果限制了从左到右的方式，那么主要有4种：

前序遍历：根左右
中序遍历：左根右
后续遍历：左右根
层序遍历：按层级、从上到下，在同一层从左到右遍历

以上一篇的二叉树为例子，先序遍历先访问根节点，在访问左节点，在访问右节点，如图：

先(根)序遍历（根左右）：A、B、D、E、C、F、G
中(根)序遍历（左根右） : D、B、E、A、F、C、G
后(根)序遍历（左右根） : D、E、B、F、G、C、A
层序序遍历（上到下，左到右）：A、B、C、D、E、F、G

递归实现先序、中序、后序、层序遍历

　　二叉树的创建用上一篇链表方法存储的二叉树，只不过增加了4个遍历的方法而已。一颗大的树都是若干颗小树（根节点、左节点、右节点）构成，根节点也有可能是其他节点的左子树（树的根节点除外），所以递归遍历就是不断的递归子树的过程。

 1 /*
 2  * @Description: 
 3  * @Version: 1.0
 4  * @Autor: longbs
 5  */
 6 class Node {
 7   constructor (data = '#') {
 8     this.data = data
 9     this.lNode = null
10     this.rNode = null
11   }
12 }
13 
14 class BiTree {
15   root = null
16   nodeList = []
17   constructor (nodeList) {
18     this.root = new Node()
19     this.nodeList = nodeList
20   }
21   createNode (node) {
22     const data = this.nodeList.shift()
23     if (data === '#') return
24     node.data = data
25     // 下一个元素是不是空节点, 如果不是创建左节点
26     if (this.nodeList[0] !== '#') {
27       node.lNode = new Node(data)
28     }
29     this.createNode(node.lNode)
30 
31     // 下一个元素是不是空节点, 如果不是创建右节点
32     if (this.nodeList[0] !== '#') {
33       node.rNode = new Node(data)
34     }
35     this.createNode(node.rNode)
36     
37   }
38   preorderTraverse (node) {
39     if (node === null) return
40     console.log(node.data)
41     this.preorderTraverse(node.lNode)
42     this.preorderTraverse(node.rNode)
43   }
44   inorderTraverse (node) {
45     if (node === null) return
46     this.inorderTraverse(node.lNode)
47     console.log(node.data)
48     this.inorderTraverse(node.rNode)
49   }
50   postorderTraverse (node) {
51     if (node === null) return
52       this.postorderTraverse(node.lNode)
53       this.postorderTraverse(node.rNode)
54       console.log(node.data)
55   }
56   sequenceTraverse (root) {
57     if (!root) return
58     let queue = []
59     queue.push(root)
60     while (queue.length) {
61       const node = queue.shift()
62       console.log(node.data)
63       if(node.lNode) {
64         queue.push(node.lNode)
65       }
66       if (node.rNode) {
67         queue.push(node.rNode)
68       }
69     }
70   }
71 }
72 
73 let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']
74 let bi = new BiTree(arr)
75 bi.createNode(bi.root)
76 console.log(bi.root)
77 
78 console.log('----先序----')
79 console.log(bi.preorderTraverse(bi.root))
80 
81 console.log('----中序----')
82 console.log(bi.inorderTraverse(bi.root))
83 
84 console.log('----后序----')
85 console.log(bi.postorderTraverse(bi.root))
86 
87 console.log('----层序----')
88 console.log(bi.sequenceTraverse(bi.root))

层级遍历使用了队列来实现，思路也比较简单，一开始入队根节点，出队最后一个节点，出队时把相关左节点、右节点入队，如此循环，队列为空即遍历完成。

非递归实现先序、中序、后序

二叉树的递归遍历非常容易理解，但因为是递归调用需要在内存栈中分配内存用来保存参数，层数多了内存容易溢出。

非递归先序基本思路：使用数组来模拟栈的数据结构，首先根节点入栈，然后出栈，在出栈的时候把相关需要的节点按要求把左右节点入栈，如此循环一直到这个栈为空。

步骤：

根节点放入栈
取出栈顶的节点，把该节点结果放入数组
如果该右节点存在，将该节点右节点放入栈
如果该左节点存在，将该节点左节点放入栈
重复 2-4
栈为空退出循环

 1 /*
 2     非递归：用栈来模拟递归
 3   */
 4   preorderNonRecursion (root) {
 5     if (!root) return ''
 6     let stack = []
 7     let result = []
 8     stack.push(root)
 9     while (stack.length) {
10       const node = stack.pop()
11       result.push(node.data)
12 
13       // 如果存在右节点，先压入右节点
14       if (node.rNode) {
15         stack.push(node.rNode)
16       }
17       if (node.lNode) {
18         stack.push(node.lNode)
19       }
20     }
21     return result
22   }

中序、后序代码基本思路类似代码如下：

 1 // 非递归-中序
 2   inorderNonRecursion (root) {
 3     if (!root) return ''
 4     let stack = []
 5     let result = []
 6     // stack.push(root)
 7     while (root !== null || stack.length) {
 8       // 找到左节点
 9       while (root !== null) {
10         stack.push(root)
11         root = root.lNode
12       }
13       root = stack.pop()
14       result.push(root.data)
15       // 右节点
16       root = root.rNode
17     }
18     return result
19   }
20   // 非递归-后序
21   postorderNonRecursion (root) {
22     if (!root) return ''
23     let stack = []
24     let result = []
25     stack.push(root)
26     while (stack.length) {
27       const node = stack.pop()
28       result.unshift(node.data)
29 
30       if (node.lNode) {
31         stack.push(node.lNode)
32       }
33       if (node.rNode) {
34         stack.push(node.rNode)
35       }
36     }
37     return result
38   }

递归遍历、非递归遍历完整代码

/*
 * @Description: 
 * @Version: 1.0
 * @Autor: longbs
 */
class Node {
  constructor (data = '#') {
    this.data = data
    this.lNode = null
    this.rNode = null
  }
}
class BiTree {
  root = null
  nodeList = []
  constructor (nodeList) {
    this.root = new Node()
    this.nodeList = nodeList
  }
  // 创建二叉树
  createNode (node) {
    const data = this.nodeList.shift()
    if (data === '#') return
    node.data = data
    // 下一个元素是不是空节点, 如果不是创建左节点
    if (this.nodeList[0] !== '#') {
      node.lNode = new Node(data)
    }
    this.createNode(node.lNode)
    // 下一个元素是不是空节点, 如果不是创建右节点
    if (this.nodeList[0] !== '#') {
      node.rNode = new Node(data)
    }
    this.createNode(node.rNode)
    
  }
  // 先序
  preorderTraverse (node) {
    if (node === null) return
    console.log(node.data)
    this.preorderTraverse(node.lNode)
    this.preorderTraverse(node.rNode)
  }
  // 中序
  inorderTraverse (node) {
    if (node === null) return
    this.inorderTraverse(node.lNode)
    console.log(node.data)
    this.inorderTraverse(node.rNode)
  }
  // 后序
  postorderTraverse (node) {
    if (node === null) return
      this.postorderTraverse(node.lNode)
      this.postorderTraverse(node.rNode)
      console.log(node.data)
  }
  // 层序
  sequenceTraverse (root) {
    if (!root) return
    let queue = []
    queue.push(root)
    while (queue.length) {
      const node = queue.shift()
      console.log(node.data)
      if(node.lNode) {
        queue.push(node.lNode)
      }
      if (node.rNode) {
        queue.push(node.rNode)
      }
    }
  }
  /*
    非递归-先序
    用栈来模拟递归
  */
  preorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    stack.push(root)
    while (stack.length) {
      const node = stack.pop()
      result.push(node.data)
      // 如果存在右节点，先压入右节点
      if (node.rNode) {
        stack.push(node.rNode)
      }
      if (node.lNode) {
        stack.push(node.lNode)
      }
    }
    return result
  }
  // 非递归-中序
  inorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    // stack.push(root)
    while (root !== null || stack.length) {
      // 找到左节点
      while (root !== null) {
        stack.push(root)
        root = root.lNode
      }
      root = stack.pop()
      result.push(root.data)
      // 右节点
      root = root.rNode
    }
    return result
  }
  // 非递归-后序
  postorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    stack.push(root)
    while (stack.length) {
      const node = stack.pop()
      result.unshift(node.data)
      if (node.lNode) {
        stack.push(node.lNode)
      }
      if (node.rNode) {
        stack.push(node.rNode)
      }
    }
    return result
  }
}
let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']
let bi = new BiTree(arr)
bi.createNode(bi.root)
console.log(bi.root)
console.log('----递归先序----')
console.log(bi.preorderTraverse(bi.root))
console.log('----非递归先序----')
console.log(bi.preorderNonRecursion(bi.root))
console.log('----递归中序----')
console.log(bi.inorderTraverse(bi.root))
console.log('----非递归中序----')
console.log(bi.inorderNonRecursion(bi.root))
console.log('----递归后序----')
console.log(bi.postorderTraverse(bi.root))
console.log('----非递归后序----')
console.log(bi.postorderNonRecursion(bi.root))
console.log('----层序----')
console.log(bi.sequenceTraverse(bi.root))