Tree of 7.
Tree is a kind of one to many nonlinear data structure, which is composed of N (N >=0) finite nodes. A binary tree means that a node in the tree has at most two child nodes, one on the left and one on the right. A binary search tree is a type of binary tree, but it only allows you to store values smaller than the parent on the left node and larger or equal values on the right node.
The data structure of the binary search tree can be expressed in JavaScript as:
// The data structure of each node in the binary search tree
function TreeNode(value) {
this.value = value;
this.left = null;
this.right = null;
}
function SearchTree() {
this.root = null;
}
// Insert a node. The left node of a binary search tree is smaller than the root node and the right node is larger than the root node
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); }}}}If the root node exists, then the left subtree is traversed. The root node of the left subtree exists.
// Output, iterate over the left subtree of the left subtree, and iterate over the right subtree according to the same rules
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;
}
// Middle order traversal: Starting from the root node, if the left subtree exists, traversal the left subtree until the left subtree is empty, output the left node, then output the child root node, then output the right node,
// Follow the same rules to traverse the right subtree
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;
}
If the left subtree exists, the left subtree is traversed until the left subtree is empty. The left node is output, the right node is output, and the root node is output
// Follow the same rules to traverse the right subtree
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;
}Copy the code(1) The maximum depth of the binary tree
// Given a binary tree, find its maximum depth.
// The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.
/** * 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; }};Copy the code(2) Verify the binary search tree
The results of middle order traversal of binary search tree are arranged from small to large, which can be used to verify the binary search tree.
(3) symmetric binary tree
// Given a binary tree, check if it is mirror - symmetric.
/** * 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;
};
Copy the code(4) Hierarchical traversal of binary tree
// Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right).
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;
};Copy the code(5) Transform the ordered array into a binary search tree
Converts an ordered array to a binary search tree, which is an INSERT method that places a binary search tree on top. If we want a highly balanced binary search tree, we need to divide the ordered array into two parts with the same number of elements or within 1.
// Convert an ordered array in ascending order to a highly balanced binary search tree.
// In this case, a highly balanced binary tree is one in which the absolute value of the height difference between the left and right subtrees of each node is less than 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;
};Copy the codeYou don’t need to call twoPart every time a new node is inserted. An ordered array can be divided into two parts, with the middle element as the root node and traversing forward from the middle node as the left subtree. Traverse backwards from the intermediate node as the right subtree.