losetime

1. 二叉树特点

左子树 < 父节点 < 右子树

2. 中序遍历

先遍历左子树，再访问父节点，再遍历右子树, 可以实现从小到大的排序

3. 前序遍历

先访问父节点，再遍历左子树，再遍历右子树 可以实现复制一颗二叉树，比重新构建二叉树快十倍左右

4. 后序遍历

先遍历左子树，再遍历右子树，再访问父节点 可以应用到文件系统的中，先访问它的左右子树，最后来访问这个节点本身

5. 二叉树查找

• 最小值：递归查找左子树
• 最大数：递归查找右子树
• 具体数：先判断大于父节点还是小于父节点，如果小于父节点，进入左子树；如果大于父节点，进入右子树；递归查找

6. 二叉树子节点的删除,最终目标是保持二叉树的排序性

7.具体实现

function BinaryTree(){
		this.root = null;
		var Node = function(key){
				this.key = key;
				this.left = null;
				this.right = null;
		}
		var 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 node = new Node(key);
				if(this.root === null){
						this.root = node;
				}else {
						insertNode(this.root,node);
				}
		}
		var inOrderTravelNode = function(node,callback){
				if(node!==null){
						inOrderTravelNode(node.left,callback);
						callback(node.key);
						inOrderTravelNode(node.right,callback);
				}
		}
		// 中序遍历
		this.inOrderTravel = function(callback){
				inOrderTravelNode(this.root,callback)
		}
		var searchNode = function(node,key){
				if(node === null){
						console.log("查找失败");
				}
				else if(node.key > key){
						searchNode(node.left,key);
				}else if(node.key < key){
						searchNode(node.right,key);
				}else {
						console.log("找到了");
				}
		}
		//具体值查找
		this.search = function(key){
				if(this.root !== null){
						searchNode(this.root,key);
				}
		}
		//查找右子树最小节点(也就是当前父节点的右子树的左子树)
		var findMinNode = function(node){
				if(node){
						while(node && node.left !== null) {
								node = node.left;
						}
						return node;
				}
				return null;
		}
		var that = this;
		var removeNode = function(node,key){
				if(node === null){
						console.log("查找失败");
				}
				else if(node.key > key){
						node.left = removeNode(node.left,key);
						return node;
				}else if(node.key < key){
						node.right = removeNode(node.right,key);
						return node;
				}else {
						//没有子节点
						if(node.left === null && node.right === null){
								node = null;
								console.log("该节点已删除");
								return node;
						}
						//一个子节点
						if(node.left === null){
								node = node.right;
								return node;
						} else if(ndoe.right === null) {
								node = node.left;
								return node;
						}
						// 两个子节点，从右子树里找到最小子节点，然后替换父节点的值，并删除这个最小子节点
						var minNode = findMinNode(node.right);
						node.key = minNode.key;
						node.right = removeNode(node.right,minNode);
						return node;
				}
		}
		//删除子节点
		this.remove = function(key){
				this.root = removeNode(this.root,key);
		}
}
let node = [10,3,5,6,7,2,12,4,18,9,1]
let binaryTree = new BinaryTree();
//创建二叉树
node.forEach(key=>{
		binaryTree.insert(key);
})
var callback = function(key){
		console.log("中序遍历："+key);
}
// 中序遍历
binaryTree.inOrderTravel(callback);
// 二叉树查找子节点
binaryTree.search(7);
//二叉树删除子节点
binaryTree.remove(1);