我们上一篇写了一个简易二叉树的创建。

学习二叉树的创建也是对经典的数据结构又有了一定的了解，而很多数据结构也是从二叉树演化而来的

我们在看一次这种图

而我们学习创建二叉树的主要目的还是进行遍历，查找，操作这三大点。

那我们这次就先从遍历，查找开始

首先是三种遍历逻辑

重点！递归调用时 一开始传参的node为根节点，后面则会依次传入node.left,node.right ！！下面的话语根节点也可能是node.right/left

遍历逻辑（比较抽象，因为是递归调用）前序遍历从根节点开始，打印当前节点，然后递归遍历左子树，然后打印当前节点，在递归遍历，直到遍历到叶子节点后返回上一层递归，在遍历右子树，中序遍历从根节点开始，如果有左孩子，则递归调用左孩子，然后没有就返回上一层打印节点，然后遍历右节点，中序遍历最后的输出结果为正序排序。后序遍历从跟节点开始，首先递归遍历左节点，直到为叶子节点，然后返回上一层在递归调用右节点，直到为叶子节点为止，然后返回上一层输出当前节点。这种方法根节点为最后输出。

最小/大值逻辑

首先我们从二叉树的创建就能看出，小节点在左边，那我们则可以这样，如果有左节点，则用循环一直访问当前节点的左节点，知道为null，此时当前节点的值就是最小值，最大值相反即可。

方法为min/max

查找指定值逻辑

比如我们查找一个在二叉树存在的值：1，

我们则先和根节点的值比较，如果小于当前跟节点则向左遍历，大于当前跟节点则向右遍历,如果等于则返回true, 这个时候我们查找一个不存在的值通过chrome最后可以看到root.node == null的情况，此时我们加个判断return false就可以了

删除节点（这个比较麻烦）还要保证删除节点后还是二叉树的数据结构。

有几种情况

实现逻辑叶子节点左右节点为空这种就是直接赋值为null就行了兄弟节点有左边或者右边有节点比如删除的为上图中的10，然后此时左子树为空，我们就此时将14的右子树赋值给根节点。兄弟节点左右都有节点比如上面的图我们删除节点3的值，然后我们需要从比他大的右子树找一个最小值，赋值给节点3，然后将找到的最小值删除

我们还是直接看代码吧。。。

callback 只是一个函数，作用：输出节点的值；

代码中有注释

看指定的方法时将其方法中的debugger和调用打开在chrome运行即可，主要是看递归调用时root的作为参数传入的变化和递归执行顺序。

class BinaryNode { constructor(node) { this.node = node this.right = null this.left = null } } class BinaryTree { constructor() { this.root = null } insert(newNode) { // debugger var newNode = new BinaryNode(newNode) if (this.root) { this.insertNode(this.root, newNode) } else { this.root = newNode } } insertNode(node, newNode) { // debugger if (node.node > newNode.node) { if (node.left === null) { node.left = newNode } else { this.insertNode(node.left, newNode) } } else { if (node.right === null) { node.right = newNode } else { this.insertNode(node.right, newNode) } } } // 前序遍历 preOrderTraverse(callback) { debugger this.preOrderTraverseNode(this.root, callback); } preOrderTraverseNode(node, callback) { debugger if (node !== null) { callback(node.node) this.preOrderTraverseNode(node.left, callback) this.preOrderTraverseNode(node.right, callback) } } // 中序遍历 inOrderTraverse(callback) { // debugger this.inOrderTraverseNode(this.root, callback) } inOrderTraverseNode(node, callback) { // debugger if (node !== null) { this.inOrderTraverseNode(node.left, callback) callback(node.node) this.inOrderTraverseNode(node.right, callback) } } // 后序遍历 postOrderTraverse(callback) { // debugger this.postOrderTraverseNode(this.root, callback) } postOrderTraverseNode(node, callback) { // debugger if (node !== null) { this.postOrderTraverseNode(node.left, callback) this.postOrderTraverseNode(node.right, callback) callback(node.node) } } // 最小值 min() { // debugger return this.minNode(this.root) } minNode(root) { // debugger if (root.left !== null) { // debugger while(root && root.left) { root = root.left } return root.node } return root.node } // 最大值 max() { // debugger return this.maxNode(this.root) } maxNode(root) { // debugger if(root.right !== null) { while(root && root.right) { root = root.right } return root.node } return root.node } // 查找一个指定node search(node) { // debugger return this.searchNode(this.root, node) } searchNode(root, node) { // debugger if (root === null ) { return false } if (root.node > node) { return this.searchNode(root.left, node) } else if (root.node < node) { return this.searchNode(root.right, node) } else { return true } } remove(node) { debugger this.removeNode(this.root, node) } removeNode(root, node) { debugger if (root === null) { return null } if (root.node > node) { root.left = this.removeNode(root.left, node) return root } else if (root.node < node) { root.right = this.removeNode(root.right, node) return root } else { if (root.left === null && root.right === null) { root = null return root } if (root.left === null) { root = root.right return root } else if (root.right === null) { root = root.left return root } var aux = this.findMinNode(root.right) root.node = aux.node root.right = this.removeNode(root.right, aux.node) return root } } findMinNode(root) { if (root) { while(root && root.left !== null) { root = root.left } return root } return null } } var nodes = [8, 3,10, 1, 6, 14, 4, 7, 13] var binaryTree = new BinaryTree() nodes.forEach(node => { binaryTree.insert(node) }) console.log(binaryTree.root) var callback = function(node) { console.log(node) } // 如果需要哪个代码则打开注释和方法中的debugger即可,打开一个要把不需要看的注释， // 先序遍历 binaryTree.preOrderTraverse(callback) //例如这条打开，这个方法中已经打好的debugger打开， 多看一遍函数的执行顺序和当前值，就好了。 // 中序遍历 // binaryTree.inOrderTraverse(callback) // 后序遍历 // binaryTree.postOrderTraverse(callback) console.log( // `最小值是：${binaryTree.min()}`, // `最大值是：${binaryTree.max()}`, ) console.log( // binaryTree.search(1) ? "search num 1 is fount" : "search num 1 is not found", // binaryTree.search(15) ? "search num 15 is fount" : "search num 15 is not found", ) // binaryTree.remove(1) // binaryTree.remove(3) // binaryTree.remove(10) // console.log(binaryTree.root)