二叉树前序遍历的非递归实现:
function Node (data, left, right) { this.data = data this.left = left || null this.right = right || null } function BST () { this.root = null } function insertNode (parentNode, newNode) { if (newNode.data < parentNode.data) { if (parentNode.left === null) { parentNode.left = newNode } else { insertNode(parentNode.left, newNode) } } else { if (parentNode.right === null) { parentNode.right = newNode } else { insertNode(parentNode.right, newNode) } } } BST.prototype.insert = function (data) { const node = new Node(data, null, null) if (this.root === null) { this.root = node } else { insertNode(this.root, node) } } const bst = new BST(); [23, 45, 16, 37, 3, 99, 22].forEach((item) => { bst.insert(item) }) function preTraverseBST (bst) { let node = bst.root let arr = [node] // 作为一个栈来使用,只用它的shift和unshift方法 while (node !== null && arr.length > 0) { console.log(node.data) if (node.left !== null) { arr.unshift(node.left) node = node.left } else { node = arr.shift() while (node.right === null && arr.length > 0) { node = arr.shift() } node = node.right arr.unshift(node) } } } preTraverseBST(bst)
最新评论
大哥资深网民啊,01年我还在念小学。。
看着有点难过。。。
嘿嘿,谢谢老哥,也祝老哥事业蒸蒸日上。
我是你唯一的药学类友情链接网站。 作为一个80后的过来人祝福你,生活越来越好。
这篇文章,我们中学那会老师课堂上念给我们听的。
哈哈哈哈哈,没想到啊, 我有手抄版
嗯,是的
好心办坏事多了去啦
哈哈,是的,我15年末来上海写代码了,一晃三年多过去了,好快。
今天看QQ好友的时候突然看到了你的名字,想起几年前在药品国际注册群挺活跃/厉害的你,现在不见踪影了。就搜了一下,没想到你现在转行去写代码了... (刚才打漏了一句话...)