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

• 2022 年 2 月 14 日
• 筆記
• 大前端, 大前端算法篇, 算法

二叉树遍历：

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())