javascript如何实现二叉树的创建和遍历？（代码示例）

PHP中文网 • 2025年3月7日 23:37:25 • 编程技术 • 阅读 2

本篇文章给大家介绍一下使用javascript实现二叉树的创建和遍历的方法。有一定的参考价值，有需要的朋友可以参考一下，希望对大家有所帮助。

1、先说二叉树的遍历，遍历方式：

前序遍历：先遍历根结点，然后左子树，再右子树

中序遍历：先遍历左子树，然后根结点，再右子树

立即学习“Java免费学习笔记（深入）”；

后续遍历：先遍历左子树，然后右子树，再根结点

上代码：主要还是利用递归

function TreeCode() {    let BiTree = function (ele) {        this.data = ele;        this.lChild = null;        this.rChild = null;    }    this.createTree = function () {        let biTree = new BiTree('A');        biTree.lChild = new BiTree('B');        biTree.rChild = new BiTree('C');        biTree.lChild.lChild = new BiTree('D');        biTree.lChild.lChild.lChild = new BiTree('G');        biTree.lChild.lChild.rChild = new BiTree('H');        biTree.rChild.lChild = new BiTree('E');        biTree.rChild.rChild = new BiTree('F');        biTree.rChild.lChild.rChild = new BiTree('I');        return biTree;    }}//前序遍历function ProOrderTraverse(biTree) {    if (biTree == null) return;    console.log(biTree.data);    ProOrderTraverse(biTree.lChild);    ProOrderTraverse(biTree.rChild);}//中序遍历function InOrderTraverse(biTree) {    if (biTree == null) return;    InOrderTraverse(biTree.lChild);    console.log(biTree.data);    InOrderTraverse(biTree.rChild);}//后续遍历function PostOrderTraverse(biTree) {    if (biTree == null) return;    PostOrderTraverse(biTree.lChild);    PostOrderTraverse(biTree.rChild);    console.log(biTree.data);}let myTree = new TreeCode();console.log(myTree.createTree());console.log('前序遍历')ProOrderTraverse(myTree.createTree());console.log('中序遍历')InOrderTraverse(myTree.createTree());console.log('后续遍历')PostOrderTraverse(myTree.createTree());

登录后复制

二叉树的非递归遍历

深度优先遍历（主要利用栈的先进后出）

广度优先遍历（主要利用队列的先进先出）

//深度优先非递归function DepthFirstSearch(biTree) {    let stack = [];    stack.push(biTree);    while (stack.length != 0) {        let node = stack.pop();        console.log(node.data);        if (node.rChild) {            stack.push(node.rChild);        }        if (node.lChild) {            stack.push(node.lChild);        }    }}//广度优先非递归function BreadthFirstSearch(biTree) {    let queue = [];    queue.push(biTree);    while (queue.length != 0) {        let node = queue.shift();        console.log(node.data);        if (node.lChild) {            queue.push(node.lChild);        }        if (node.rChild) {            queue.push(node.rChild);        }    }}

登录后复制

深度优先主要是利用栈，先压右子树，再压左子树

广度优先主要利用队列，先入左子树，再入右子树

深度优先的遍历结果与前序遍历相同ABDGHCEIF，广度优先的遍历结果是 ABCDEFGHI

2、创建二叉树

1中创建二叉树的方式过于笨拙，假入我们根据完全二叉树的模型建立自己的二叉树，空数据的地方用#表示，如下图所示我们称之为扩展二叉树，我们取其前序遍历的序列 AB#D##C##。

上代码：也是利用递归

//前序遍历得到的字符串let strArr = 'AB#D##C##'.split('');function BiTree(ele) {    this.data = ele;    this.lChild = null;    this.rChild = null;}var newTree = new BiTree('#');function createBiTree(biTree) {    if (strArr.length == 0) return;    let str = strArr.shift();    if (str == '#') return;    biTree.data = str;    if (strArr[0] != '#') {        biTree.lChild = new BiTree('#')    }    createBiTree(biTree.lChild);    if (strArr[0] != '#') {        biTree.rChild = new BiTree('#')    }    createBiTree(biTree.rChild);}createBiTree(newTree);console.log(newTree);ProOrderTraverse(newTree)

登录后复制

你也可以用中序遍历或者后序遍历实现二叉树的创建，代码里生成结点和构建左右子树的代码顺序交换一下就行了

推荐教程：《JavaScript视频教程》

以上就是javascript如何实现二叉树的创建和遍历？（代码示例）的详细内容，更多请关注【创想鸟】其它相关文章！

发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2726713.html