前言
树和图一样，是常用的数据结构模型，但是我的理解树是图的一个用于更具体的数据结构。今天温习的是树中比较简单、常用的二叉树。因为一个简单固定的结构更有利于查询，所以有了二叉查找树的概念。
简单介绍下
研究依然以点-线模型的分析理解，不过树是从一个方向顺势的分支结构。这里可以是自上向下，也可以自下向上。
树的常见术语有几个：
- 根节点
- 子节点
- 叶子节点
- 层
- 子树
- 路径
- 键（这里是抽象主要的数据）
二叉树：
- 子节点不超过两个
- 左节点
- 右节点
如果具备查找特性：
较小值在左，较大值在右
这里准备一组值来构建树：
[ 23, 45, 16, 37, 3, 99, 22 ]
然后我需要构建的树的成品是：
具体实现
- 首先需要构造一个节点对象，来表示节点这一个描述元素
class Node {
constructor (data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
getData () {
return this.data;
}
output() {
console.log(this.data);
}
}
主要包含：
- data: 节点的键
- left: 左节点
- right: 右节点
- getData: 获取键
output: 辅助输出函数
- 树的对象以及树的操作
class Tree {
constructor () {
// 根节点默认是 null
this.root = null;
}
// 插入节点
insert (data) {
const node = new Node(data, null, null);
if(this.root === null) {
this.root = node;
} else {
let current = this.root;
let parent = null;
while(1) {
parent = current;
if(data < current.data) {
current = current.left;
if(current === null) {
parent.left = node;
break;
}
} else {
current = current.right;
if(current === null) {
parent.right = node;
break;
}
}
}
}
return this;
}
// 中序遍历
ascOrder (node) {
if(node !== null) {
this.ascOrder(node.left);
node.output();
this.ascOrder(node.right);
}
}
// 先序遍历
rootOrder (node) {
if(node !== null) {
node.output();
this.rootOrder(node.left);
this.rootOrder(node.right);
}
}
// 后序遍历
leafOrder (node) {
if(node !== null) {
this.leafOrder(node.left);
this.leafOrder(node.right);
node.output();
}
}
// 执行路径的 action: left or right
action (path) {
let node = this.root;
while(node[path] !== null) {
node = node[path];
}
return node;
}
// 最小值
min () {
return this.action('left');
}
// 最大值
max () {
return this.action('right');
}
// 查找固定值
find (data) {
let node = this.root;
while(node !== null) {
if(data === node.data) {
return node;
} else if(data < node.data) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
}
最后我在 Node 环境下测试，所以导出一下 Tree 类:
module.exports = Tree;
对于每一种排序后的结果是不一样的，可以用图形来表示一下：
中序遍历的过程：
先序遍历的过程：

后序遍历的过程：

其实看图是最直观的，其实算法这玩意最好的就是能够体会思想，然后根据实际的场景进行映射建立数据结构模型，以最优或更平衡的去解决问题。
测试代码如下：
const Tree = require('./binTree');
const log = s => console.log(s);
const tree = new Tree();
[23, 45, 16, 37, 3, 99, 22].forEach(n => tree.insert(n));
log('中-排序：');
tree.ascOrder(tree.root);
log('先-排序：');
tree.rootOrder(tree.root);
log('后-排序：');
tree.leafOrder(tree.root);
console.log('=====================');
log('最小值：');
log( tree.min() );
log('最大值：');
log( tree.max() );
log('查找 3：');
log( tree.find(3) );
log('查找 11：');
log( tree.find(11) );
终端跑的结果如下：
