本文摘自PHP中文网,作者青灯夜游,侵删。
本篇文章给大家介绍一下使用javascript实现二叉树的创建和遍历的方法。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。
1、先说二叉树的遍历,遍历方式:
前序遍历:先遍历根结点,然后左子树,再右子树
中序遍历:先遍历左子树,然后根结点,再右子树
后续遍历:先遍历左子树,然后右子树,再根结点
上代码:主要还是利用递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
|
二叉树的非递归遍历
深度优先遍历(主要利用栈的先进后出)
广度优先遍历(主要利用队列的先进先出)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
深度优先主要是利用栈,先压右子树,再压左子树
广度优先主要利用队列,先入左子树,再入右子树
深度优先的遍历结果与前序遍历相同ABDGHCEIF,广度优先的遍历结果是 ABCDEFGHI
2、创建二叉树
1中创建二叉树的方式过于笨拙,假入我们根据完全二叉树的模型建立自己的二叉树,空数据的地方用#表示,如下图所示我们称之为扩展二叉树,我们取其前序遍历的序列 AB#D##C##。
上代码:也是利用递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
你也可以用中序遍历或者后序遍历实现二叉树的创建,代码里生成结点和构建左右子树的代码顺序交换一下就行了
推荐教程:《JavaScript视频教程》
以上就是javascript如何实现二叉树的创建和遍历?(代码示例)的详细内容,更多文章请关注木庄网络博客!
相关阅读 >>
更多相关阅读请进入《javascript》频道 >>
Vue.js 设计与实现 基于Vue.js 3 深入解析Vue.js 设计细节
本书对 Vue.js 3 技术细节的分析非常可靠,对于需要深入理解 Vue.js 3 的用户会有很大的帮助。——尤雨溪,Vue.js作者