This is the 8th day of my participation in the August Text Challenge.More challenges in August

First, the introduction of trees

  • Tree: n(n >= 0)A finite set of nodes
  • For any non-empty tree(n > 0), with the following properties:
    • The tree has a special node called **” root “**
    • The remaining nodes can be divided into M(m > 0)Two finite sets that do not intersect each otherT1, T2... , Tm,Where each set is itself a tree, called the **” subtree “of the original tree **

The properties of trees are many…

  • Degree of nodes: the number of nodes in the tree
  • 1. A node of degree 0 (also called a leaf node).
  • Node hierarchy: specify that the root node is at layer 1, and the number of layers of any other node is the number of layers of its parent node plus 1

Binary, binary tree

Properties of binary trees

  • The maximum number of nodes at the i-th level of a binary tree is: 2^(i-1), I >=1

    For example, the first layer (root node) is 1; The second layer has a maximum of 2 nodes

  • The maximum number of nodes in a binary tree of depth k is: 2^k-1, k>=1

  • For any non-empty binary tree T, if n0 represents the number of leaf nodes (degree 0) and n2 represents the number of non-leaf nodes with degree 2, then the relation n0 = n2 + 1 is satisfied

A. Complete binary tree

  • Except for the last layer of the binary tree, the number of nodes in other layers reaches the maximum

  • And the last layer reaches the continuous existence of leaf nodes from left to right, only missing several nodes on the right

  • In the graph below, from left to right, E has a right child but D doesn’t, so it’s not a complete binary tree. If you add a right child to D, then it’s a complete binary tree

B. Perfect binary tree (full binary tree)

  • In a binary tree, a full binary tree is formed when each node has 2 child nodes except the leaf node at the lowest level

Binary trees can be stored as arrays or linked lists, but we usually use linked lists. Because if you use an array if the binary tree is not a full binary tree, it’s going to waste a lot of space.

Three, binary search tree

  • Binary search tree is a binary tree, can be empty; If it is not empty, it satisfies the following properties:
  • All keys of a non-empty left subtree are less than the keys of its root node
  • All keys of a non-empty right subtree are greater than those of its root node
  • The left and right subtrees themselves are binary search trees

Binary search tree initialization

  • First, the binary search tree has a root node. Initialization makes the root node point to null. this.root = null;

  • Secondly, each node of the binary search tree contains three elements, left child node, right child node and key value. In the initial state, the pointer is null

    function Node() {
    this.key = key;
    this.left = null;
    this.right = null;
}
Copy the code

Four, binary search tree common methods

  • insert(key):Inserts a new key into the tree
  • search(key):Finds a key in the tree, returns true if the node exists; If not, return false
  • inOrderTraverse:All nodes are traversed by middle-order traversal
  • preOrderTraverse:All nodes are traversed by sequential traversal
  • postOrderTraverse:All nodes are traversed through the sequential traversal mode
  • min:Returns the smallest value/key in the tree
  • max:Returns the largest value/key in the tree
  • remove(key):Removes a key from the tree

1. insertmethods

  1. Create a node based on the key

  2. Determine whether the root node has a value; If the root node is null, go to the next step

    BinarySearchTree.prototype.insert = function (key) {
    var newNode = new Node(key);
    if (this.root == null) {
        this.root = newNode;
    } else {
        this.insertNode(this.root, newNode); }}Copy the code

  3. In search tree insertion operation, if the value of the insertion is greater than the root node, then the node should be inserted into the right child node of the root node. If the root node already has a right child, you should continue to compare the value of the node to the right child. The process is essentially a nesting doll until the left or right node is empty, so this is done recursively, another function is used to insert the node.

    BinarySearchTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) {
        if (node.left == null) {
            node.left = newNode;
        } else {
            this.insertNode(node.left, newNode); }}else {
        if (node.right == null) {
            node.right = newNode;
        } else {
            this.insertNode(node.right, newNode); }}}Copy the code

2. Traverse the binary search tree

Because the structure of the tree is special, we often use recursive method to achieve the traversal of nodes.

A. Sequential traversal

  • Accessing the root node
  • The left subtree is traversed first, and the right subtree is traversed first
BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
    if(node ! =null) {
        handler(node.key);
        this.preOrderTraversalNode(node.left, handler);
        // 3. Process the right child of the passed node
        this.preOrderTraversalNode(node.right, handler); }}//--------
var resultString = ' '
tree.preOrderTraversal(function (key) {
    resultString += key + ' ';
})
Copy the code

Handler is a callback function that handles the node so we can see the result of the loop; In preemptive traversal, we first traverse all the left child nodes, and then process the right child nodes that pass through the node. Like this one:

So the recursive idea here is a little bit more complicated, it’s a nesting of functions, and it jumps out one by one at the end of the walk, and it takes a little bit of time to understand.

After traversing the left node of 7 to 5, iterate through 3, which is the leaf node, and continue through 6 (node 5 at this point). After traversing the left node of 5, iterate through the right child node of 7.

B. Middle-order traversal

  • The order traverses its left subtree
  • Accessing the root node
  • Middle order traverses the right subtree
if(node ! =null) {
    this.inOrderTraversalNode(node.left, handler);
    handler(node.key);
    this.inOrderTraversalNode(node.right, handler);
}
Copy the code

C. Post-order traversal

  • The left subtree is traversed, and the right subtree is traversed
  • Accessing the root node
if(node ! =null) {
    this.inOrderTraversalNode(node.left, handler);
    this.inOrderTraversalNode(node.right, handler);
    handler(node.key);
}
Copy the code

After understanding preorder traversal, middle order traversal and post order traversal are implemented in a recursive way, the difference is when to process nodes.

3. Maximum & minimum

Maxima and minima are easy to find in numbers. The left-most child node (bottom left) is the minimum; The rightmost child node (bottom right) is the maximum. Here is a demonstration of finding the maximum value.

  • Get the root node
  • Search to the right until the node is null
BinarySearchTree.prototype.max = function () {
    var node = this.root;
    var key = null;
    while(node ! =null) {
        key = node.key
        node = node.right
    }
    return node.key
}
Copy the code

Keep searching for the right node until the value of the right node is empty and return the key value of the node.

4. Search for specific values

This method can be implemented recursively or through a loop for searching

  • Recursion; Key == key, returns true, or false if it cannot be found after these steps.

    BinarySearchTree.prototype.searchNode = function (node, key) {
    if (node == null) {
        return false;
    }
    if (node.key > key) {
        return this.searchNode(node.left, key);
    } else if (node.key < key) {
        return this.searchNode(node.right, key);
    } else {
        return true;
    }
    return false;
}
Copy the code

  • The loop retrieves the root node and then loops for the key

    A little bit easier to understand if you’re doing a loop, you’re doing a key-value comparison, and you’re going to go to the left subtree or the right subtree until you find the target value.

    var node = this.root;
while(node ! =null) {
    if (node.key > key) {
        node = node.left;
    } else if (node.key < key) {
        node = node.right;
    } else {
        return true; }}return false;
Copy the code

Deleting is the most complicated, so save it for the next article! I can’t go to school today aaa… Teacher CodeWhy really did a great job!