前言

树和图一样,是常用的数据结构模型,但是我的理解树是图的一个用于更具体的数据结构。今天温习的是树中比较简单、常用的二叉树。因为一个简单固定的结构更有利于查询,所以有了二叉查找树的概念。

简单介绍下?

研究依然以点-线模型的分析理解,不过树是从一个方向顺势的分支结构。这里可以是自上向下,也可以自下向上。

树的常见术语有几个:

• 根节点
• 子节点
• 叶子节点
• 层
• 子树
• 路径
• 键(这里是抽象主要的数据)

二叉树:

• 子节点不超过两个
• 左节点
• 右节点

如果具备查找特性:

较小值在左,较大值在右

这里准备一组值来构建树:

[ 23, 45, 16, 37, 3, 99, 22 ]

然后我需要构建的树的成品是:

树

具体实现

1. 首先需要构造一个节点对象,来表示节点这一个描述元素

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) );

终端跑的结果如下:

测试结果