前言
本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。
那么首先来看一下什么是二叉排序树？
二叉排序树
定义
二叉排序树，又称二叉查找树、二叉搜索树。
- 若左子树不为空，左子树上所有结点均小于它的根结点的值；
- 若右子树不为空，右子树上所有结点均大于它的根结点的值；
- 左右子树也分别为二叉排序树。
插入算法
我们知道了什么是二叉排序树，现在来看下它的具体算法实现。
// 构建二叉树function BinaryTree() { // 定义结点 let Node = function(key) { this.key = key this.left = left this.right = right } // 定义根结点 let root = null // 获得整棵树 this.getRoot = function() { return this.root } // 定义插入结点算法 let insertNode = function(node, newNode) { // 比较要插入结点与当前结点值的大小，若大于当前结点，插入左子树，反之，插入右子树 if(newNode.key < node.key) { if(node.left === null) { node.left = newNode } else { insertNode(node.left, newNode) } } else { if(node.right === null) { node.right = newNode } else { insertNode(node.right, newNode) } } } // 定义二叉排序树插入算法 this.insert = function(key) { let newNode = new Node(key) if(root === null) { root = newNode } else { insertNode(root, newNode) } }}let nodes = [8,3,30,1,6,14,4,7,13]// 创建树实例let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key)})console.log("创建的二叉树是：", tree.getRoot())至此，一棵二叉排序树就构造完啦。接下来我们根据构造的这颗二叉树进行相应遍历、查找与删除操作。
遍历二叉树
二叉树的遍历分为深度优先遍历和广度优先遍历。
深度优先遍历
深度优先遍历（Depth First Search）是指沿着树的深度进行遍历树的结点。其中深度优先遍历又分为三种：前序遍历、中序遍历、后序遍历。
这里前序、中序、后序是根据根结点的顺序命名的。
1、前序遍历
定义
前序遍历也叫做先根遍历、先序遍历、前序周游，记做 根左右。
- 先访问根结点；
- 前序遍历左子树；
- 前序遍历右子树。
前序遍历的作用是可以复制已有的二叉树，且比重新构造的二叉树的效率高。
下面我们来看它的算法实现。分为递归与非递归两种。
方法一 递归实现
function BinaryTree() { // 这里省略了二叉排序树的构建方法 // 定义前序遍历算法 let preOrderTraverseNode = function(node, callback) { if(node !== null) { callback(node.key) // 先访问当前根结点 preOrderTraverseNode(node.left, callback) // 访问左子树 preOrderTraverseNode(node.right, callback) // 访问右子树 } } // 定义前序遍历方法 this.preOrderTraverse = function(callback) { preOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key) // 构造二叉树})// 定义回调函数let callback = function(key) { console.log(key)}tree.preOrderTraverse(callback) // 8 3 10 1 6 14 4 7 13方法二 非递归实现
非递归的实现是借助于栈，先访问根结点，并将当前结点从栈中推出，再将当前结点的左右子树推进栈中。
function BinaryTree() { // ... // 定义前序遍历算法 let preOrderTraverseNode = function(node, callback) { let stack = [] if(node !== null) { stack.push(node) while(stack.length) { let temp = stack.shift() callback(temp.key) if(temp.left !== null) { stack.push(temp.left) } if(temp.right !== null) { stack.push(temp.right) } } } } // 定义前序遍历方法 this.preOrderTraverse = function(callback) { preOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key) // 构造二叉树})// 定义回调函数let callback = function(key) { console.log(key)}tree.preOrderTraverse(callback) // 8 3 10 1 6 14 4 7 132、中序遍历
定义
中序遍历也叫做中根遍历、中序周游，记做 左根右。
- 若左子树不为空，则先中序遍历左子树；
- 访问根结点；
- 若右子树不为空，则中序遍历右子树。
中序遍历二叉排序树，得到的数组是有序的且是升序的。
下面我们来看中序遍历算法的实现。分为递归和非递归两种。
方法一 递归实现
function BinaryTree() { // 省略二叉排序树的创建 // 定义中序遍历算法 let inOrderTraverseNode = function(node, callback) { if(node !== null) { inOrderTraverseNode(node.left, callback) // 先访问左子树 callback(node.key) // 再访问当前根结点 inOrderTraverseNode(node.right, callback) // 访问右子树 } } // 定义中序遍历方法 this.inOrderTraverse = function(callback) { inOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key) // 构造二叉树})// 定义回调函数let callback = function(key) { console.log(key)}tree.inOrderTraverse(callback) // 1 3 4 6 7 8 10 13 14方法二 非递归实现
借助于栈，先将左子树全部放进栈中，之后输出，最后处理右子树。
function BinaryTree() { // 省略二叉排序树的构建方法 // 定义中序遍历算法 let inOrderTraverseNode = function(node, callback) { let stack = [] while(true) { // 将当前结点的左子树推入栈 while(node !== null) { stack.push(node) node = node.left } // 定义终止条件 if(stack.length === 0) { break } let temp = stack.pop() callback(temp.key) node = temp.right } } this.inOrderTraverse = function(callback) { inOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key) // 构造二叉树})// 定义回调函数let callback = function(key) { console.log(key)}tree.inOrderTraverse(callback) // 1 3 4 6 7 8 10 13 143、后序遍历
定义
后序遍历也叫做后根遍历、后序周游，记做 左右根。
- 若左子树不为空，后序遍历左子树；
- 若右子树不为空，后序遍历右子树；
- 访问根结点。
后序遍历的作用用于文件系统路径中，或将正常表达式变成逆波兰表达式。
下面我们来看后序遍历算法的实现。分为递归和非递归两种。
方法一 递归实现
// 先构造一棵二叉树function BinaryTree() { // 省略二叉排序树的构建方法 // 定义后序遍历算法 let postOrderTraverseNode = function(node, callback) { if(node !== null) { postOrderTraverseNode(node.left, callback) // 遍历左子树 postOrderTraverseNode(node.right, callback) // 再遍历右子树 callback(node.key) // 访问根结点 } } // 定义后序遍历方法 this.postOrderTraverse = function(callback) { postOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key){ tree.insert(key)})// 定义回调函数let callback = function(key) { console.log(key)}tree.postOrderTraverse(callback) // 1 4 7 6 3 13 14 10 8方法二 非递归实现
// 先构造一棵二叉树function BinaryTree() { // 省略二叉排序树的构建方法 // 定义后序遍历算法 let postOrderTraverseNode = function(node, callback) { let stack = [] let res = [] stack.push(node) while(stack.length) { let temp = stack.pop() res.push(temp.key) if(temp.left !== null) { stack.push(temp.left) } if(temp.right !== null) { stack.push(temp.right) } } callback(res.reverse()) } // 定义后序遍历方法 this.postOrderTraverse = function(callback) { postOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key){ tree.insert(key)})// 定义回调函数let callback = function(key) { console.log(key)}tree.postOrderTraverse(callback) // 1 4 7 6 3 13 14 10 8广度优秀遍历
广度优先遍历（Breadth First Search），又叫做宽度优先遍历、层次遍历，是指从根结点沿着树的宽度搜索遍历。
下面来看它的实现原理
方法一 非递归
使用栈实现，未访问的元素入栈，访问后则出栈，并将其leve左右元素入栈，直到叶子元素结束。
function BinaryTree() { // 省略二叉排序树的构建 let wideOrderTraverseNode = function(node, callback) { let stack = [] if(node === null) { return [] } stack.push(node) while(stack.length) { // 每一层的结点数 let level = stack.length // 遍历每一层元素 for(let i = 0; i < level; i++) { // 当前访问的结点出栈 let temp = stack.shift() // 出栈结点的孩子入栈 temp.left ? queue.push(temp.left) : '' temp.right ? queue.push(temp.right) : '' callback(temp.key) } } } this.wideOrderTraverse = function(callback) { wideOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key)})// 定义回调函数let callback = function(key) { console.log(key)}tree.wideOrderTraverse(callback) // 8,3,10,1,6,14,4,7,13方法二 非递归
function BinaryTree() { // 省略二叉排序树的构建 let wideOrderTraverseNode = function(node, callback) { let stack = [] if(node === null) { return [] } stack.push(node) while(stack.length) { let temp = stack.shift() callback(temp.key) if(temp.left) { stack.push(temp.left) } if(temp.right) { stack.push(temp.right) } } } this.wideOrderTraverse = function(callback) { wideOrderTraverseNode(root, callback) }}let nodes = [8,3,10,1,6,14,4,7,13]let tree = new BinaryTree()nodes.forEach(function(key) { tree.insert(key)})// 定义回调函数let callback = function(key) { console.log(key)}tree.wideOrderTraverse(callback) // 8,3,10,1,6,14,4,7,13鉴于篇幅过长，二叉树结点的查找和删除会在下一篇文章内~