js - 前序，中序遍历二叉搜索树非递归

前序，中序遍历很像，都是用到了 栈 这个数据结构，大家不明白栈的，可以去我的这篇博客 栈的介绍

这是插入二叉搜索树的代码。

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