乘风原创程序

  • js - 前序,中序遍历二叉搜索树非递归
  • 2020/8/10 11:24:44
  • 前序,中序遍历很像,都是用到了 这个数据结构,大家不明白栈的,可以去我的这篇博客 栈的介绍

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

    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