大前端算法篇之二叉树遍历

x33g5p2x  于2022-02-14 转载在 其他  
字(1.5k)|赞(0)|评价(0)|浏览(149)

二叉树遍历:

  1. 前序遍历:先输出当前节点;然后遍历左子树,如果左子树不为空,递归前序遍历;接着遍历右子树,如果右子树不为空,递归前序遍历
  2. 中序遍历:先遍历当前节点左子树,如果不为空,递归中序遍历;输出当前节点,接着遍历当前节点右子树,如果不为空,递归中序遍历
  3. 后序遍历:先遍历当前节点左子树,如果不为空,递归后序遍历;在遍历当前节点右子树,不过不为空,递归后序遍历,输出当前节点

怎么区分何种遍历,就是看当前节点的输出顺序

class HeroNode {
    constructor(no,name){
        this.no = no
        this.name = name
    }

    setLeft(left){
        this.left = left
    }

    setRight(right){
        this.right = right
    }
    toString(){
        console.log(this.name)
    }

    preOrder(){
        if(this.no == 2) {
            return false
        }
        if(this.left){
            this.left.preOrder()
        }
        
        if(this.right){
            this.right.preOrder()
        }
    }

    preOrderSearch(no){
        if(this.no == no) {
            return this
        }
        let res = null
        if(this.left){
            res = this.left.preOrderSearch(no)
        }
        if(res) return res
        if(this.right){
            return this.right.preOrderSearch(no)
        }
        return res
    }

    infixOrder(){
        if(this.left){
            this.left.infixOrder()
        }
        console.log(this.toString())
        if(this.right){
            this.right.infixOrder()
        }
    }

    postOrder(){
        if(this.left){
            this.left.postOrder()
        }
        if(this.right){
            this.right.postOrder()
        }
        console.log(this.toString())
    }
}

class BinaryTree {
    constructor(root){
        this.root = root
    }
    setRoot(root){
        this.root = root
    }
    preOrder(){
        if(this.root){
            this.root.preOrder()
        }
    }
    infixOrder(){
        if(this.root){
            this.root.infixOrder()
        }
    }
    postOrder(){
        if(this.root){
            this.root.postOrder()
        }
    }

    preOrderSearch(no){
        if(this.root){
            return this.root.preOrderSearch(no)
        }
    }
}

function exec(){
    // 创建二叉树
    const bt = new BinaryTree()

    // 创建节点
    const root = new HeroNode(1,'刘备')
    const h2 = new HeroNode(2,'关羽')
    const h3 = new HeroNode(3,'张飞')
    const h4 = new HeroNode(4,'赵云')

    root.setLeft(h2)
    root.setRight(h3)
    h3.setRight(h4)

    bt.setRoot(root)

    return bt.preOrderSearch(4)
}

console.log(exec())

相关文章

微信公众号

最新文章

更多