class TreeNode {
constructor(value) {
this.value = value; //数据域
this.left = null; //左孩子
this.right = null; //右孩子
}
}
// 二叉树工具类
class BinaryTree {
constructor() {}
// 数组严格表示法
static createTreeNode(arr, index) {
if (index > arr.length) {
return null;
}
if (arr[index] == null) {
return null;
}
const node = new TreeNode(arr[index]);
node.left = BinaryTree.createTreeNode(arr, index * 2 + 1);
node.right = BinaryTree.createTreeNode(arr, index * 2 + 2);
return node;
}
// 数组优化表示法
static arrayToTree(arr) {
if (arr.length === 0) {
return null;
}
const root = new TreeNode(arr[0]);
//是否是左孩子节点
let isLChild = true;
//用数组的push和shift模拟队列
const queue = [];
queue.push(root);
//从第二个节点开始遍历
for (let i = 1; i < arr.length; i++) {
//从队列中取出第一个元素
const node = queue[0];
if (isLChild) {
if (arr[i] != null) {
node.left = new TreeNode(arr[i]);
//把 left 节点插入队列
queue.push(node.left);
}
// left 完毕，开始处理 right
isLChild = false;
} else {
if (arr[i] != null) {
node.right = new TreeNode(arr[i]);
//把 right 节点插入队列
queue.push(node.right);
}
//right处理完毕，开始出队列
queue.shift();
isLChild = true;
}
}
return root;
}
}
二叉树工具类
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 数据结构在线工具 https://www.cs.usfca.edu/~galles/visualization/A...
- Tree 树是一种数据结构，由n(>=0)个有限节点Node组成的一个具有层次关系的集合。 树的特点 每个子节点都...
