今天就跟大家聊聊有关如何在javascript中实现二叉树的创建和遍历？，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
1、先说二叉树的遍历，遍历方式：
前序遍历：先遍历根结点，然后左子树，再右子树
中序遍历：先遍历左子树，然后根结点，再右子树
后续遍历：先遍历左子树，然后右子树，再根结点
上代码：主要还是利用递归
计算
安全
数据库
网络和加速
企业服务
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中实现二叉树的创建和遍历？有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
