二叉树排序是一种数据结构、根据左孩子小于根节点、右孩子大于根节点的顺序进行构造
任意给一个数组，对其进行二叉树排序。
```javascript
function BinaryTree() {
// 二叉树的节点
let Node = function (key) {
this.key = key; //当前节点的值
this.left = null; // 左孩子
this.right = null; // 右孩子
}
// 插入子节点
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);
}
}
}
// 初始化根节点、就是一个数组的第一个元素当做二叉树的根节点
let root = null;
this.insert = function (key) {
let newNode = new Node(key);
if(root === null){
root = newNode;
}else{
insertNode(root,newNode)
}
};
// 查看二叉树结构
this.show = function () {
console.log(root);
}
// 中序遍历
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 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 nextOrderTraverseNode = function (node,callback) {
if(node !== null){
nextOrderTraverseNode(node.left,callback);
nextOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
this.nextOrderTraverse = function (callback) {
nextOrderTraverseNode(root,callback);
}
}
```
调用
```javascript
let nodes = [18,13,102,11,6,14,4,7,131];
const bt = new BinaryTree();
nodes.forEach( key => {
bt.insert(key)
})
bt.show()
// 中序遍历
// bt.inOrderTraverse((key) => {
// console.log(key);
// })
// 前序遍历
// bt.preOrderTraverse((key) => {
// console.log(key);
// })
// 后序遍历
bt.nextOrderTraverse((key) => {
console.log(key);
})
```
二叉树遍历
中序遍历
首先遍历左子树、然后遍历根节点、最后遍历右子树 -- 左-根-右
作用: 将一个二叉树进行升序排序输出
前序遍历
首先遍历根节点、然后遍历左子树、最后遍历右子树 -- 根-左-右
作用: 复制一个二叉树、复制一个二叉树比重新生成一个二叉树的效率高10倍左右
后序遍历
首先遍历左子树、然后遍历右子树、最后遍历根节点 -- 左-右-根
适用于操作系统的文件遍历
二叉树查找
查找最小值
查找最大值
查找某一个值
// 查找最小值 let minNode = function (node) { if(node){ while(node && node.left !== null){ node = node.left; } return node.key; } return null; } this.min = function () { return minNode(root); } // 查找最大值 let maxNode = function (node) { if(node){ while(node && node.right !== null){ node = node.right; } return node.key; } return null; } this.max = function () { return maxNode(root); } // 查找某个具体的值 let findNode = function (node,key) { if(node === null){ return false; } // 若是查找的值小于当前节点的值，那么就去其左子树进行查找 // 若是大于,就去右子树进行查找 // 若是相等 则返回true 代表存在 if(key < node.key){ return findNode(node.left,key) }else if(key > node.key){ return findNode(node.right, key) }else{ return true; } } this.find = function (key) { return findNode(root,key); }