7.树
树是一种一对多的非线性数据结构,是由n(n>=0)个有限结点组成一个具有层次关系的集合。二叉树是指树的节点最多有两个子节点,一个左侧子节点,一个右侧子节点。二叉搜索树是二叉树的一种,但是它只允许你在左侧的节点存储比父节点小的值,在右侧的节点存储比父节点大的或者相等的值。
二叉搜索树的数据结构在JavaScript中可表示为:
//二叉搜索树的每个节点的数据结构
function TreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}
function SearchTree() {
this.root = null;
}
//插入一个节点。二叉搜索树的左节点小于根节点,右节点大于根节点
SearchTree.prototype.insert = function (val) {
let node = new TreeNode(val);
if (this.root == null) {
this.root = node;
} else {
insertNode(node, this.root)
}
function insertNode(node, root) {
if (node.value < root.value) {
if (root.left == null) {
root.left = node;
} else {
insertNode(node, root.left);
}
} else {
if (root.right == null) {
root.right = node;
} else {
insertNode(node, root.right);
}
}
}
}
// 先序遍历:如果根节点存在,输出根节点,然后遍历左子树,左子树的根节点存在,
// 输出,再遍历左子树的左子树,依照同样规则遍历右子树
SearchTree.prototype.preOrder = function () {
let result = [];
preOrderTraverse(this.root);
function preOrderTraverse(node) {
if (node !== null) {
result.push(node.value);
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
}
return result;
}
//中序遍历:从根节点开始,如果左子树存在,遍历左子树直到左子树为空,输出左节点,再输出子树根节点,再输出右节点,
//按照同样的规则遍历右子树
SearchTree.prototype.inOrder = function () {
let result = [];
inOrderTraverse(this.root);
function inOrderTraverse(node) {
if (node !== null) {
inOrderTraverse(node.left);
result.push(node.value);
inOrderTraverse(node.right);
}
}
return result;
}
//后序遍历:从根节点开始,如果左子树存在,遍历左子树直到左子树为空,输出左节点,再输出右节点,最后输出根节点
//按照同样的规则遍历右子树
SearchTree.prototype.postOrder = function () {
let result = [];
postOrderTraverse(this.root);
function postOrderTraverse(node) {
if (node !== null) {
postOrderTraverse(node.left);
postOrderTraverse(node.right);
result.push(node.value);
}
}
return result;
}
//给定一个二叉树,找出其最大深度。
//二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
if (root) {
let left = maxDepth(root.left) + 1;
let right = maxDepth(root.right) + 1;
let result = left > right ? left : right;
return result;
} else {
return 0;
}
};
二叉搜索树的中序遍历得到的结果是从小到大排列的,可以根据这一特性验证二叉搜索树。
//给定一个二叉树,检查它是否是镜像对称的。
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
var result = true;
if (root === null) return true;
compare(root.left, root.right);
function compare(node1, node2) {
if (node1 && node2) {
if (node1.val != node2.val) {
result = false;
return;
} else {
compare(node1.left, node2.right);
compare(node1.right, node2.left);
}
} else if (!node1 && !node2) {
} else {
result = false;
return;
}
}
return result;
};
//给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
var levelOrder = function (root) {
var result = [];
if (root) order([root]);
function order(arr) {
let temp = [];
let arrNode = [];
if (arr.length === 0) return;
for (let i = 0; i < arr.length; i++) {
if (arr[i]) {
temp.push(arr[i].val);
if (arr[i].left) arrNode.push(arr[i].left);
if (arr[i].right) arrNode.push(arr[i].right);
}
}
result.push(temp);
order(arrNode);
}
return result;
};
将有序数组转换为二叉搜索树,即上放二叉搜索树的insert方法。题目要求是一个高度平衡的二叉搜索树,则需要将有序数组划分为两部分,两部分元素数量相同或相差不超过1。
//将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
//本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function (nums) {
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function insertNode(node, val) {
let t = new TreeNode(val);
if (val < node.val) {
if (node.left === null) {
node.left = t;
} else {
insertNode(node.left, val);
}
} else {
if (node.right === null) {
node.right = t;
} else {
insertNode(node.right, val);
}
}
}
var root = null;
twoPart(nums);
function twoPart(nums) {
if (nums.length > 0) {
if (root === null) {
let index = parseInt(nums.length / 2);
root = new TreeNode(nums[index]);
twoPart(nums.slice(index + 1));
twoPart(nums.slice(0, index));
} else {
let index = parseInt(nums.length / 2);
insertNode(root, nums[index]);
twoPart(nums.slice(index + 1));
twoPart(nums.slice(0, index));
}
}
}
return root;
};
上数方法中twoPart部分,可以不用每次插入一个新节点都调用twoPart。可以将有序数组分为两部分,中间元素作为根节点,自中间节点向前遍历,作为左子树。自中间节点向后遍历作为右子树。