Went out to interview, was asked about the computer data structure and algorithm, awkward, I did not understand, although I am front-end development, usually algorithm problems or consider less, summed up by myself ~ more precipitation point ~
- What is a tree?
Tree is a kind of data structure, it is composed of N (N >=1) finite nodes of a hierarchical relationship set. Attached picture:
Trees have the following characteristics:
(1) Each node has zero or more children
(2) Nodes without parent nodes are called root nodes
(3) Each non-root node has only one parent node
(4) In addition to the root node, each child node can be divided into multiple disjoint subtrees.
2. What is a binary tree?
A binary tree is a tree structure with at most two subtrees per node. It has five basic forms: binary trees can be empty sets; The root can be an empty left or right subtree; Or both left and right subtrees are empty.
Properties of binary trees
- The maximum number of nodes at the i-layer of the binary tree is: 2i-1(I >=1)
- A binary tree of depth k has at most 2K-1 nodes (k>=1)
- A binary tree with n nodes has a height of at least (log)2n)+1
Full binary tree, complete binary tree, binary tree search tree
- Full binary tree
Definition: a binary tree with height H and consisting of 2H-1 nodes is called a full binary tree
- Complete binary tree
Definition: in a binary tree, the degree of only the lowest two nodes can be less than 2, and the lowest leaf nodes are concentrated in several positions to the left. Such a binary tree is called a complete binary tree.
Features: Leaf nodes can only appear at the lowest and lower levels, and the lowest level of leaf nodes are concentrated in the left part of the tree. Obviously, a full binary tree must be a complete binary tree, and a complete binary tree is not necessarily a full binary tree.
- Binary tree search tree
Definition: Binary search tree is also called binary search tree. Let x be a node in the binary search tree, where x contains the keyword key and the key value of x is counted as key[x]. If y is a node in the left subtree of x, then key[y]<=key[x]; Key [y]>=key[x] if y is a node of the right subtree of x
Find tree species in binary:
(1) If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
(2) If the right subtree of any node is not empty, the values of all nodes in the right subtree are greater than the values of its root node.
(3) The left and right subtrees of any node are binary search trees respectively.
(4) There are no nodes with equal key values.
4. Binary tree traversal
This means that all nodes in a binary tree are accessed from the root node in some order, such that each node is accessed only once.
Traversal in three ways:
First-order (root) traversal: left-right middle (root) traversal: left-right back-order (root) traversal: left-right root
(function() {/ / sequential storage structure traversal tree = var [1, 2, 3, 4, 5, and 6,,, 7]. console.log('preOrder:'); void function preOrderTraverse(x, visit) { visit(tree[x]); if (tree[2 * x + 1]) preOrderTraverse(2 * x + 1, visit); if(tree[2 * x + 2]) preOrderTraverse(2 * x + 2, visit); } (0,function(value) { console.log(value); }); //1, 2, 4, 5, 7, 3, 6 console.log('inOrder:'); void function inOrderTraverse(x, visit) { if (tree[2 * x + 1]) inOrderTraverse(2 * x + 1, visit); visit(tree[x]); if (tree[2 * x + 2]) inOrderTraverse(2 * x + 2, visit); } (0,function(value) { console.log(value); }); //4, 2, 7, 5, 1, 3, 6 console.log('postOrder:'); void function postOrderTraverse(x, visit) { if (tree[2 * x + 1]) postOrderTraverse(2 * x + 1, visit); if(tree[2 * x + 2]) postOrderTraverse(2 * x + 2, visit); visit(tree[x]); } (0,function(value) { console.log(value); }); } ()); //4, 7, 5, 2, 6, 3, 1Copy the codeThese are the three traversals of binary trees (implemented recursively)
To make it clearer, use the form of a view:
Sequential traversal: ABCDEFGHK
Middle order traversal: BDCAEHGKF
Sequential traversal: DCBHKGFEA
(Follow-up: the middle is also a computer professional colleague to help me point, take a nap is also suddenly understand \(^o^)/~)
Binary tree there are many operations, create, find, maximum value, minimum value of the problem is also a lot of online, here, I will only post binary sorting tree method ~
function BinaryTree (arr) { if(Object.prototype.toString.call(arr).slice(8, -1) ! = ='Array') { throw new TypeError('Take only one array as an argument') } this.root = null; / / this root node. Arr = arr | | []; // take the arguments passed in - array // initialize each TreeNode var TreeNode =function(key) { this.key = key; This. left = null; // Left subtree this.right = null; } // Build a binary tree this.init =function () { if(! this.arr) { console.warn('Please select an array parameter'); } for(var i = 0, len = this.arr.length; i < len; I ++) {this.insert(this.arr[I])}} // Insert the node this.insert =function(key) {var newNode = new TreeNode(key) // The node to be insertedif(this.root === null) {// Insert the node into the root node when no value exists. }else{ this.insertNode(this.root, newNode) } } this.insertNode = function (rootNode, newNode) { if(rootNode.key > newNode.key) {// If the key of the current node is smaller than that of the parent node, the current node should be inserted into the left subtreeif(rootNode.left === null) {// If the left subtree does not have a node, put the current node in rootNode.left = newNode;return; } this.insertNode(rootNode.left, newNode) // There is a node in the left subtree, recursively compare with the left node again}else{// When the key of the current node is greater than or equal to the parent node, the current node should be inserted into the right subtreeif(rootNode.right === null) {// If there is no node in the right subtree, put the current node in rootNode.right = newNode;return; } this.insertnode (rootnode. right, newNode)}} var arr = [8, 13,3,7,19,21,15]; var tree = new BinaryTree(arr); tree.init(); console.log(100,tree)Copy the codeThe following is the generated binary sort tree structure:
Behind still have time to continue to update summary ~ give oneself a careful heart, slowly accumulate ~ refueling refueling ！！！！