JS树的遍历
程序员文章站
2022-03-14 18:12:49
...
先序、中序、后序、层次遍历:
//树的数据结构
function TreeNode(x){
this.val = x;
this.left = null;
this.right = null;
}
//先序遍历(Degree Left Right)
function DLR(root){
console.log(root.val);
if(root.left){
DLR(root.left);
}
if(root.right){
DLR(root.right);
}
}
//中序遍历(Left Degree Right)
function LDR(root){
if(root.left){
LDR(root.left);
}
console.log(root.val);
if(root.right){
LDR(root.right);
}
}
//后序遍历(Left Right Degree)
function LRD(root){
if(root.left){
LRD(root.left);
}
if(root.right){
LRD(root.right);
}
console.log(root.val);
}
//层次遍历
function levelTraversal(root){
if(!root) return false; //如果头结点为空,返回假
let result = []; //创建一个数组,存放结果
let tree = []; //创建一个数组存放二叉树
tree.push(root); //先传入头结点
//当tree数组长度不为空
while(tree.length){
let node = tree.shift(); //将数组第一个结点放到node中
result.push(node.val); //将node结点的值压到result数组中
//如果node结点左子树不为空
if(node.left){
tree.push(node.left);
}
//如果node结点右子树不为空
if(node.right){
tree.push(node.right);
}
}
return result;
}
let tnode = new TreeNode(3);
tnode.left = {"val":2};
tnode.right = {"val":1};
console.log(tnode);
console.log("先序遍历:");
DLR(tnode);
console.log("中序遍历:");
LDR(tnode);
console.log("后序遍历:");
LRD(tnode);
console.log("层次遍历:",levelTraversal(tnode));
上一篇: 石家庄网站建设公司:为什么不同建站公司价格有那么大差距
下一篇: XML的解析 SAX方式