假如树的形状如下所示:
- class Tree {
- constructor(v,children) {
- this.v = v
- this.children = children || null
- }
- }
- const tree = new Tree(10,[
- new Tree(5),
- new Tree(3,[
- new Tree(7),
- new Tree(11,[
- new Tree(3),
- new Tree(2)
- ])
- ]),
- new Tree(2)
- ])
先序
- function tree_transersef(tree) {
- console.log(tree.v)
- // forEach 里面可以直接跟函数, 就直接和递归连用了, 这种写法写起来比较省事
- tree.children && tree.children.forEach(tree_transersef)
- }
- tree_transersef(tree) //10 5 3 7 11 3 2 2
后序
- function tree_transverse_l(tree) {
- tree.children && tree.children.forEach(tree_transverse_l)
- // 如果树有孩子就把它的孩子都遍历完之后再来把 tree.v 打出来
- console.log(tree.v)
- }
- tree_transverse_l(tree) // 5 7 3 2 11 3 2 10
中序
- function tree_transverse_m(tree,ord = 0) {
- let transversed = false
- if(!tree.children) {
- console.log(tree.v)
- return
- }
- tree.children.forEach((child,i) => {
- if(i === ord ) {
- transversed = true
- console.log(tree.v)
- }
- tree_transverse_m(child,ord)
- });
- // 这里和上面的先序或者后序是同样的道理, 主要是看父级 tree 在遍历的时候前面有没有打出来过 ->
- // 如果打出来过了, 就不执行了, 如果没有打出来过, 就执行
- !transversed && console.log(tree.v)
- }
回调
- function tree_transverse(tree,ord = 0,callback) {
- let transversed = false
- if(!tree.children) {
- callback(tree.v)
- return
- }
- tree.children.forEach((child,i) => {
- if(i === ord ) {
- transversed = true
- callback(tree.v)
- }
- tree_transverse_m(child,ord)
- });
- !transversed && callback(tree.v)
- }
基于 Generator(相比于 forEach 在循环的时候可以 break)
- function* tree_transverse(tree,ord=0) {
- let transversed = false
- if(!tree.children) {
- yield tree
- return
- }
- for(let i =0;i < tree.children.length;i++) {
- if(i === ord) {
- transversed = true
- yield tree
- }
- yield *tree_transverse(tree.children[i],ord)
- }
- if(!transversed) {
- yield tree
- }
- }
- console.log([...tree_transverse(tree)],'test')
来源: http://www.bubuko.com/infodetail-2931756.html