The tree

Concept:

  • Nodes that have the same parent are called siblings
  • Depth of node: The number of edges experienced from the root node to the node
  • Height of node: the longest path from node to leaf node
  • Tree height: The height of the root node

Binary tree

A binary tree is a tree with at most two child nodes

Binary tree storage method:

  1. Linked storage (i.e. linked list storage)
  2. Linear storage (that is, array storage)

Common types of binary trees

Complete binary tree: If all nodes of a binary tree are numbered, the convention is to number them from the root, top-down, and from left to right. Then, a binary tree with depth k and n nodes is called a complete binary tree if and only if each node corresponds to nodes numbered from 1 to n in a full binary tree with depth K.

Full binary tree: A binary tree with depth k and (2 to the k – 1) nodes is called full binary tree. That is, every node except the leaf has left and right cotyledons and the leaf nodes are at the bottom of the binary tree

Note: a full binary tree must be a complete binary tree, and a complete binary tree is not necessarily a full binary tree

Balanced binary tree: in a binary tree, the height difference between the left and right subtrees of each node cannot be greater than 1. So both of these could be balanced binary trees.

Binary search tree (binary sorting tree) : A binary search tree has the following properties: If its left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node; If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are binary search trees respectively.

Implement a binary search tree

Function Tree(){// The root node is null this.root = null; Function Node(val) {this.val = val; this.left = null; this.right = null; } this.insert(val) {let newNode = newNode (val); if(this.root === null) { this.root = newNode; }else { insertNode(this.root, newNode); }} function insertNode(node, inserttree) newNode) { if(node.val > newNode.val) { if(node.left === null) { node.left = newNode; }else { insertNode(node.left, newNode); } }else { if(node.right === null) { node.right = newNode; }else { insertNode(node.right, newNode); }}}} / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- to test the let a = new Tree (); a.insert(10); a.insert(7); a.insert(11); a.insert(5); a.insert(6); a.insert(8); a.insert(12); console.log(a);Copy the code

Results:

Traversal of binary trees

Depth-first traversal

  1. Foreorder traversal (middle left)
  2. Middle order traversal (left middle right)
  3. Post-order traversal (left and right center)

Example: to implement binary tree code to write

Prior traversal: 10,7,5,6,8,11,12 (do your own mental calculations)

This.preergodic = ()=>{// let res = []; function preErgodicTree(root) { if(root ! == null) { res.push(root.val); preErgodicTree(root.left); preErgodicTree(root.right); } } preErgodicTree(this.root); return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the output to the console. The console log (Amy polumbo reErgodic ());Copy the code

Results: (7) [10, 7, 5, 6, 8, 11, 12]

It’s hard to see the picture. Hey, hey, hey, put it down

Middle order traversal: 5,6,7,8,10,11,12 (do it in your head)

This.inorderergodic = () => {// let res = []; function inOrderErgodicTree(root) { if (root ! == null) { inOrderErgodicTree(root.left); res.push(root.val); inOrderErgodicTree(root.right); } } inOrderErgodicTree(this.root); return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the output to the console. The console log (Anderson nOrderErgodic ());Copy the code

Results :(7) [5, 6, 7, 8, 10, 11, 12]

Backward traversal: 6,5,8,7,12,11,10

This.postorderergodic = () => {// let res = []; function postOrderErgodicTree(root) { if (root ! == null) { postOrderErgodicTree(root.left); postOrderErgodicTree(root.right); res.push(root.val); } } postOrderErgodicTree(this.root); return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the output to the console. The console log (Amy polumbo ostOrderErgodic ());Copy the code

Results :(7) [6, 5, 8, 7, 12, 11, 10]

Breadth-first traversal

  1. Sequence traversal

Sequence traversal: 10,7,11,5,8,12,6

This.sequenceergodic = () => {// store the result array let res = []; // Let tempArr = [this.root]; for(let i=0; i<tempArr.length; i++) { if(tempArr[i] ! == null) { res.push(tempArr[i].val); Push (tempArr[I].left); push(tempArr[I].left); tempArr.push(tempArr[i].right); } } return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the output to the console. The console log (a.s equenceErgodic ());Copy the code

Results :(7) [10, 7, 11, 5, 8, 12, 6]

The search tree

Continue with the example above

Remember the characteristics of binary search trees: if the left subtree is not empty, then the value of all nodes in the left subtree is less than the value of its root node. If its right subtree is not empty, the value of all nodes in the right subtree is greater than the value of its root node. Its left and right subtrees are binary search trees respectively.

Search for random value

this.search = (targetVal) => { function searchNode(root, TargetVal) {return false if(root === null) return false; // If the value to be queried is greater than the value of the current node, that is, search the subtree to the right. // Equal, If (targetVal < root.val) {return searchNode(root.left, targetVal); }else if(targetVal > root.val){ return searchNode(root.right, targetVal); }else { return true; } } return searchNode(this.root, targetVal); } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the console. The console log (a.s earch (12));Copy the code

Results: true,

Find maximum value (same minimum value)

Because of the nature of a binary search tree, finding the maximum value requires only finding its rightmost node

This.searmax = () => {let res = null; // Let temp = this.root; while(temp ! == null) { res = temp.val; temp = temp.right; } return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the console. The console log (a.s earMax ());Copy the code

Results: 12

Similarly, to find the minimum, you just need to find its leftmost node

This.searmin = () => {// initial result, save each step let res = null; // Let temp = this.root; while (temp ! == null) { res = temp.val; temp = temp.left; } return res; } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the console. The console log (a.s earMin ());Copy the code

Results: 5

Removes a node from the tree

Three things happen when a node is removed

  1. The target node is a leaf node: Change the target node to NULL and return the changed node
  2. There is a child node: this child node needs to be added to the removed node to return the changed node
  3. There are two child nodes: the example I use here is a binary search tree, so in order to ensure that the tree remains a binary search tree after removing the node, that is, the minimum value in the right child node needs to be found, added to the removed node, and then deleted the node where the previous minimum value was, and returned to the node

Suppose you delete the number 7

This.remove = (targetVal) => {// if(! targetVal) return; function removeNode(root, targetVal) { if(root === null) return null; If (targetVal < root.val) {root.left = removeNode(root.left, targetVal); return root; }else if(targetVal > root.val) {root.right = removeNode(root.right, targetVal); return root; If (root.left === null && root.right === null) {root = null; return root; }else if(root.left ! == null && root.right === null) { root = root.left; return root; }else if(root.left === null && root.right ! == null) { root = root.right; return root; }else{function findMin(root) {while(root.left! == null) { root = root.left; } return root.val; } // Min let temp = findMin(root.right); // Add the minimum value to the deleted location root.val = temp; Root. right = removeNode(root.right, temp); // Return node return root; This. root = removeNode(this.root, targetVal); } //------------------------ console a.emove (7); console.log(a.sequenceErgodic());Copy the code

Results :(6) [10, 8, 11, 5, 12, 6]

The complete code

<script> function Tree() { this.root = null; this.insert = (val) => { let newNode = new Node(val); if (this.root === null) { this.root = newNode; } else { insertNode(this.root, newNode); Function Node(val) {this.val = val; this.left = null; this.right = null; } function insertNode(node, newNode) { if (node.val > newNode.val) { if (node.left === null) { node.left = newNode; } else { insertNode(node.left, newNode); } } else { if (node.right === null) { node.right = newNode; } else { insertNode(node.right, newNode); }}} / / preorder traversal enclosing preErgodic = () = > {let res = []; function preErgodicTree(root) { if (root ! == null) { res.push(root.val); preErgodicTree(root.left); preErgodicTree(root.right); } } preErgodicTree(this.root); return res; } this.inorderergodic = () => {let res = []; function inOrderErgodicTree(root) { if (root ! == null) { inOrderErgodicTree(root.left); res.push(root.val); inOrderErgodicTree(root.right); } } inOrderErgodicTree(this.root); return res; } this.postorderergodic = () => {let res = []; function postOrderErgodicTree(root) { if (root ! == null) { postOrderErgodicTree(root.left); postOrderErgodicTree(root.right); res.push(root.val); } } postOrderErgodicTree(this.root); return res; } this.sequenceergodic = () => {let res = []; // temporary store let tempArr = [this.root]; For (let I = 0; i < tempArr.length; i++) { if (tempArr[i] ! == null) { res.push(tempArr[i].val); tempArr.push(tempArr[i].left); tempArr.push(tempArr[i].right); } } return res; This. search = (targetVal) => {function searchNode(root, targetVal) {if (root === null) return false; if (targetVal < root.val) { return searchNode(root.left, targetVal); } else if (targetVal > root.val) { return searchNode(root.right, targetVal); } else { return true; } } return searchNode(this.root, targetVal); } this.searmax = () => {this.searmax = () => { // Let temp = this.root; while (temp ! == null) { res = temp.val; temp = temp.right; } return res; } this.searmin = () => {this.searmin = () => { // Let temp = this.root; while (temp ! == null) { res = temp.val; temp = temp.left; } return res; } this.remove = (targetVal) => {// to prevent not entering the target value if(! targetVal) return; function removeNode(root, targetVal) { if(root === null) return null; If (targetVal < root.val) {root.left = removeNode(root.left, targetVal); return root; }else if(targetVal > root.val) {root.right = removeNode(root.right, targetVal); return root; If (root.left === null && root.right === null) {root = null; return root; }else if(root.left ! == null && root.right === null) { root = root.left; return root; }else if(root.left === null && root.right ! == null) { root = root.right; return root; }else{function findMin(root) {while(root.left! == null) { root = root.left; } return root.val; } // Min let temp = findMin(root.right); // Add the minimum value to the deleted location root.val = temp; Root. right = removeNode(root.right, temp); // Return node return root; This. root = removeNode(this.root, targetVal); } } let a = new Tree(); a.insert(10); a.insert(7); a.insert(11); a.insert(5); a.insert(6); a.insert(8); a.insert(12); a.remove(7); </script>Copy the code

conclusion

If there are any mistakes, please give me some advice, I would be very grateful