我要评论前序，中序遍历很像，都是用到了 栈 这个数据结构，大家不明白栈的，可以去我的这篇博客 栈的介绍
这是插入二叉搜索树的代码。
const COMPARE = {
LESS_THAN: 0,
BIGGER_THAN: 1,
IS_EQUAL: 2,
}
function compareFn(a, b) {
if (a > b) {
return COMPARE.BIGGER_THAN
} else if (a < b) {
return COMPARE.LESS_THAN
}
return COMPARE.IS_EQUAL
}
class Node {
constructor(key) {
this.key = key
this.left = null // 左子节点
this.right = null // 右子节点
}
}
class BinarySearchTree {
constructor(defaultCompareFn = compareFn) {
this.root = null
this.compareFn = defaultCompareFn
}
insert(key) {
if (!this.root) {
this.root = new Node(key)
} else {
this.insertNode(key, this.root)
}
}
insertNode(key, root) {
let node = new Node(key)
if (this.compareFn(key, root.key) === COMPARE.LESS_THAN) {
// 小于放左边
if (!root.left) {
root.left = node
} else {
this.insertNode(key, root.left)
}
} else {
// 大于等于放右边
if (!root.right) {
root.right = node
} else {
this.insertNode(key, root.right)
}
}
}
}
let f = new BinarySearchTree()
f.insert(9)
f.insert(15)
f.insert(5)
f.insert(4)
f.insert(6)
前序遍历的大致思路是，用一个指针cur指向根节点。一直遍历左节点，遍历一个，就输出一个（前序遍历要先输出根节点），并且入栈，一直遍历到没有左节点，遍历到4之后，4没有左节点了（已经输入了 9， 5， 4）。
从栈中弹出栈顶元素，此时是4，访问4的右节点,直接让 cur = stack.pop().right，stack.pop() 弹出的是栈顶元素，也就是4 ，4的右节点不存在，就不用管了，直接再次从栈中弹出它的父节点5，重复之前的cur = stack.pop().right(因为4是它的左节点，已经被访问了，所以直接看5的右节点)，发现5有右节点，对5 的右节点 6 ，进行输出，入栈，遍历完毕之后，就把6当前根节点，重复之前的。
PS: 大家可以把debugger打开，看这个函数是具体怎么执行的。
preOrder() { //前序遍历
// 节点不为空，将数据输出，然后将它压栈，访问左节点，不为空，继续输出，压栈
let stack = new Stack()
let cur = this.root // 指针 -> 指向当前访问的节点
while (cur || !stack.isEmpty()) {
// debugger
while (cur) {
// 节点不为空
// debugger
console.log(cur.key) // 输出节点
stack.push(cur) // 压栈
cur = cur.left // 压入最后一个值为4
}
// 一直遍历到了4, 从栈中弹出4，，看4的右节点，4没有右节点，里面的while循环不走，再次从栈中弹出5,5存在右节点，输出6，把6入栈，当前while循环走完，走到这里，弹出6,6没有子元素，于是弹出栈底元素9，按照之前的过程，输入15，结果循环。
cur = stack.pop().right // 4的子元素没有了，拿出栈顶元素4,访问它的右节点
}
}
中序遍历和前序遍历也很像，就是输出值的地方不同，中序遍历是一直遍历到左节点不存在，然后从栈中弹出栈顶元素，并且输出值，再让 cur = stack.pop().right, 重复之前的，一直遍历到栈为空截止
inOrder() { // 中序遍历
// 节点不为空，一直入栈，不需要输出值。当节点为空，从栈中弹出栈顶元素，并且输出
let stack = new Stack()
let cur = this.root
while (cur || !stack.isEmpty()) {
while (cur) {
// 一路往左走，遇到节点全部入栈，直接遇到空
stack.push(cur)
cur = cur.left
}
// debugger
// 左节点为空了，取出栈顶节点，让cur指向栈顶节点的右节点，访问右节点
let top = stack.pop() // 取出栈顶元素
console.log(top.key) // 输出值
cur = top.right // 查看右节点
}
}
大家有疑惑的地方，欢迎大家在评论区留言，有错误的地方也欢迎大家指出。
本文地址：https://blog.csdn.net/JDDDDDDyaya/article/details/107874214
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论