使用Generator处理二叉树的中序遍历

二叉树的中序遍历

let arr = [[['a'], 'b', ['c']], 'd', [['e'], 'f', ['g']]]
class Tree {
    constructor(left,root,right) { // 一棵树具有根节点，左孩子节点和右孩子节点
        this.left = left;
        this.root = root;
        this.right = right;
    }
}
// 将数组构造为树的处理函数
function arrToTree (arr) {
  if (arr.length === 1){ // 只有一个根节点
    return new Tree(null,arr[0],null)
  }
  if (arr.length === 2){ // 只有根节点和左孩子节点
    return new Tree(arrToTree(arr[0]),arr[1],null)
  }
  if (arr.length === 3) {
    return new Tree(arrToTree(arr[0]),arr[1],arrToTree(arr[2]))
  }
}
let tree = arrToTree(arr)
/* 对二叉树进行中序遍历处理（左根右的方式）
函数体内采用递归算法，所以左子树和右子树要用yield*遍历
*/
function* middleSort (that) { // that指向的是new Tree()对象
  if (that) {
    yield* middleSort(that.left) // 遍历左子树 
    yield that.root
    yield*  middleSort(that.right)// 遍历右子树
  }
}
let result = []
for (let node of middleSort(tree)) { 
  result.push(node)
}
console.log(result)
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

参考自ES6Generator