What does a binary tree look like
Easy to understand
1. A tree has only one root node, which is 7.
2. A circle is a node, and a node can have or have no left and right child nodes, such as 7. The left node is 4, and the right node is 9.
3. A node has a parent node, which can be null. For example, the parent node of 7 is NULL, and the parent node of 4 is 7.
4. If a node has both left and right child nodes, the degree of this node is 2; A node has left child node (right child node) but no right child node (left child node), that is, there is only one child node, the degree of this node is 1; A node has no child node, that is, degree 0, and this node is called leaf node.
5. A tree always has N nodes, n1 nodes with degree 1, N2 nodes with degree 1, and N0 leaf nodes, so n = n2+ N1 + N0.
6. Derivation formula: leaf node N0 = n2+1.
7. All trees can be traversed. Traversal methods include pre-order traversal, post-order traversal, middle-order traversal and layer-order traversal.
8. A node has precursor nodes and subsequent nodes, that is, the data traversed by the tree in middle order (normally, the numerical order is from smallest to largest). For example, the precursor node of node 7 is 4, and the subsequent node is 9.
Generating node objects
node.js
// Generate node objects according to their characteristics
class Node {
constructor(val,parent) {
this.element = val ? val : null;
this.left=null;
this.right=null;
this.parent = parent ? parent : null;
}
hasTwoChildren(){
if(this.left ! =null && this.right! =null) {return true;
}else{
return false; }}}Copy the codeAn object that generates a universal tree
bstCommon.js
// Generate binary tree objects based on the universal binary tree
document.write("<script language=javascript src='./queue.js'></script>");
// Create a normal tree of the class, summarize the class properties and methods
class BSTCommon {
constructor(arg) {
this.size=0;
}
// Whether the tree is empty
isEmpty(){
return this.size;
}
/ / clear the tree
clear(){
this.size=0;
}
// Traversal (root -> left -> right)
beforeInOrder(node){
if(! (node==null)) {console.log(node.element)
this.beforeInOrder(node.left)
this.beforeInOrder(node.right)
}
}
// Run (left node -> right node -> root node)
behindInOrder(node){
if(! (node==null)) {this.beforeInOrder(node.left)
this.beforeInOrder(node.right)
console.log(node.element)
}
}
// Order traversal (left node -> root node -> right node)
middleInOrder(node){
if(! (node==null)) {this.beforeInOrder(node.left)
console.log(node.element)
this.beforeInOrder(node.right)
}
}
// sequence traversal
levelInOrder(node){
if(node==null) return;
var queue = new Queue();
queue.push(node)
while(! queue.isEmpty()){var node = queue.pop();
console.log(node)
if(node.left! =null){
queue.push(node.left)
}
if(node.right! =null){
queue.push(node.right)
}
}
}
// Returns the precursor node of the binary tree
beforeNode(node){
if(node ==null) return null;
// In the first case, the precursor is in the left subtree, i.e. node.left! =null
if(node.left! =null) {var p = node.left;
while(p.right! =null){
p = p.right;
}
return p;
}
Node. left==null, you can only search up until the search node is on the right of the parent node
while(node.parent ! =null && node == node.parent.right){
node = node.parent;
}
// Exit the loop from above with parent empty or node== node.parent-right
return node.parent
}
// Returns the subsequent nodes of the binary tree
beHideNode(node){
if(node ==null) return null;
// In the first case, the precursor is in the left subtree, i.e. node.left! =null
if(node.right! =null) {var p = node.right;
while(p.left! =null){
p = p.left;
}
return p;
}
Node. left==null, you can only search up until the search node is on the right of the parent node
while(node.parent ! =null && node == node.parent.left){
node = node.parent;
}
// Exit the loop from above with parent empty or node== node.parent-right
return node.parent
}
}
Copy the codequeue.js
// Queue objects
class Queue {
constructor(arg) {
this.dataStore = [];
}
/ / team
push(val){
this.dataStore.push(val)
}
/ / out of the team
pop(){
return this.dataStore.shift()
}
isEmpty(){
if(this.dataStore.length==0) {return true;
}else{
return false; }}}Copy the codeBinary search tree features
-
The value of any node is greater than the value of all nodes in its left subtree
-
The value of any node is less than the value of all nodes in its right subtree
The binary search tree generates an object that inherits from the universal tree object
bts.js
document.write("<script language=javascript src='./node.js'></script>");
class BST extends BSTCommon {
constructor(arg) {
super(a)this.root=new Node();
}
/* Parameters are not necessarily numeric values, but may be objects, which requires the individual to define the comparison rules, so that parameters are passed in for comparison */
add(data){ // The key point is parent
if(this.root==null) return this.root = new Node(data);
var node = this.root;
var parent;
while(true){
parent = node;
if(data<node.element){
node= node.left;
if(node==null){
parent.left = new Node(data,parent)
break; }}else{
node= node.right;
if(node==null){
parent.right = new Node(data,parent)
break; }}}this.size++
}
/* Find the current deleted node object */ based on the deleted value
remove(data){
this.removeNode(this.findNode(data))
// console.log(' Found node')
// console.log(this.findNode(data))
}
// Find the node object where the value is located
findNode(data){
if(this.root==null) return null;
var node = this.root;
while(node ! =null&& node.element! = data){if(data<node.element){
node= node.left;
}else{ node= node.right; }}return node;
}
// The actual delete operation
removeNode(node){
if(node==null) return;
this.size--;
// The left and right nodes of the node are not empty
if(node.hasTwoChildren()){
var succeedNode = this.beHideNode(node); // Find subsequent nodes of node
node.element = succeedNode.element;
node = succeedNode; // Do not delete it for the time being
}
// The node to this node must be degree 1 or degree 0. If degree 1 is left or right, get the value first
varreplacement = node.left ! =null ? node.left : node.right;
if(replacement! =null) {// This is a node of degree 1, since the value has been taken from the left or right side of node
// Change the parent point of replacement
replacement.parent = node.parent;
// Then update the left and right directions of the parent
// check whether parent is null
if(node.parent ==null) {this.root = replacement;
}else{
if(node == node.parent.left){
node.parent.left = replacement
}else if(node == node.parent.right){
node.parent.right = replacement
}
}
}else{ // Here is a node with degree 0, but we don't know if it is the root node
if(node.parent == null) {/ / the root node
this.root=null;
}else{ // Not the root node
if(node == node.parent.left){
node.parent.left=null
}else{
node.parent.right=null}}}}// Contains a node
contain(data){
if(this.root==null) return false;
var node = this.root;
while(node ! =null&& node.element! = data){if(data<node.element){
node= node.left;
}else{ node= node.right; }}// Exit the loop, node may be null, or node's element is already equal to data
return Boolean(node); }}Copy the codeThe test runs after the object is generated
Test in binary tree.html:
// binary tree. HTML<! DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> </body> </html> <script type="text/javascript" src="./bstCommon.js"></script> <script type="text/javascript" src="./bst.js"></script> <script Type ="text/javascript"> var BST = new BST() var arr = [4,2,8,6,9, 5] for(var I =0; i<arr.length; I++) {BST. Add (arr) [I]} / / console log (' preorder traversal) / / BST beforeInOrder (BST) root) / / console log (' after sequence traversal) / / Bst.behindinorder (bst.root) // console.log(bst.middleinOrder (bst.root) console.log(bst.middleinOrder (bst.root) console.log(bst.behindinOrder (bst.root) console.log(bst.middleinOrder (bst.root) console.log(bst.middleinOrder (bst.root) console.log(bst.middleinOrder (bst.root) console.log) Bst.levelinorder (bst.root) // console.log(bst.contain(3)) bst.remove(6) console.log(' folder ') bst.levelinOrder (bst.root) </script>Copy the codeconclusion
This is based on js code generated by the simple binary search tree interface, and the object inside can add a lot of properties and methods, here write only for a very simple way, add, delete, traverse, this a few method is convenient to know the binary tree of the knowledge, and based on binary search tree, on the basis of a lot of AVL tree, B tree, red and black tree, These trees can inherit objects from the binary search tree.