js(es6)实现二叉树的插入、前序遍历、中序遍历、后序遍历

导航:js(es6)实现单向链表——链表添加、删除、反转方法的实现.

基础

1、在二叉树的遍历中,前中后是指父节点遍历的顺序
2、三个遍历中,左子树永远比右子树先遍历

  • 前序遍历:根左右
  • 中序遍历:左根右
  • 后序遍历:左右中

举例说明
《js(es6)实现二叉树的插入、前序遍历、中序遍历、后序遍历》

  • 前序遍历:ABDC

  • 中序遍历:DBAC

  • 后序遍历:DBCA

ES6 代码实现

节点类

一个节点有左右指针和自身的value三个属性

class Node{ 
    constructor (data){ 
        this.left = null
        this.right = null
        this.value = data
    }
}

树类

class Tree{ 
    constructor (){ 
        this.root = null
    }
}

插入节点方法

这里构建的是二叉搜索树,即父节点的值大于左节点的值,小于右节点的值
以下insertByFather方法会判断新节点要插入到二叉搜索树的哪个位置,insert方法用来创建节点并调用insertByFather方法。

//根据给出的父节点,判断将新节点插在其左还是其右
insertByFather(node, newNode) { 
	//如果新节点value小于父节点value,则插入父节点左子树上,否则插入右子树上
    if(newNode.value < node.value){ 
    	//如果父左子树存在,则递归判断插入,否则新节点就是父左子节点
        if(node.left){ 
            insertNode(node.left, newNode)
        }else{ 
            node.left = newNode
        }
    }else{ 
        if(node.right){ 
            insertNode(node.right, newNode)
        }else{ 
            node.right = newNode
        }
    }
}
//插入节点方法
insert(value){ 
    let node = new Node(value)
    if(this.root){ 
        insertNode(this.root, node)
    }else{ 
        this.root = node
    }
}

前序遍历

节点若存在,先打印该节点value,然后递归调用左子树,最后递归调用右子树

preOrder(node){ 
    if(node){ 
        console.log(node.value)
        this.preOrder(node.left)
        this.preOrder(node.right)
    }
}

中序遍历

节点若存在,先递归调用左子树,然后打印该节点value,最后递归调用右子树

inOrder(node){ 
    if(node){ 
        this.midOrder(node.left)
        console.log(node.value)
        this.midOrder(node.right)
    }
}

后序遍历

节点若存在,先递归调用左子树,然后递归调用右子树,最后打印该节点value

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

完整代码

class Node{ 
    constructor (data){ 
        this.left = null
        this.right = null
        this.value = data
    }
}

class Tree{ 
    constructor (){ 
        this.root = null
    }
    //根据给出的父节点,判断将新节点插在其左还是其右
    insertByFather(node, newNode) { 
        if(newNode.value < node.value){ 
            if(node.left){ 
                insertNode(node.left, newNode)
            }else{ 
                node.left = newNode
            }
        }else{ 
            if(node.right){ 
                insertNode(node.right, newNode)
            }else{ 
                node.right = newNode
            }
        }
    }
    //创建并插入节点
    insert(value){ 
        let node = new Node(value)
        if(this.root){ 
            insertNode(this.root, node)
        }else{ 
            this.root = node
        }
    }
    //前序遍历
    preOrder(node){ 
        if(node){ 
            console.log(node.valu)
            this.preOrder(node.left)
            this.preOrder(node.right)
        }
    }
    //中序遍历
    inOrder(node){ 
        if(node){ 
            this.midOrder(node.left)
            console.log(node.value)
            this.midOrder(node.right)
        }
    }
    //后序遍历
    postOrder(node){ 
        if(node){ 
            this.postOrder(node.left)
            this.postOrder(node.right)
            console.log(node.value)
        }
    }
}
    原文作者:无聊人_
    原文地址: https://blog.csdn.net/weixin_44607531/article/details/113124575
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞