This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 Hello everyone, I am Xiao Cheng, a sophomore front-end enthusiast

📢 This article explains trees in data structures

📢 Thank you very much for reading

📢 May you be true to yourself and love life

💡 Knowledge points look first

  • What is a tree structure?
  • Terminology for trees
  • What are the types of tree structures
  • Tree traversal before, middle, and back
  • Tree sequence traversal
  • Write a tree by hand

What is a tree structure?

Trees, like hash tables, are nonsequential data structures that are useful for storing data that needs to be looked up quickly

A tree is a hierarchical abstract model that can be understood layer by layer, similar to the genetic map of a high school organism

As shown in the figure below

Terms related to trees

From the diagram above, we have a general idea of what a tree is, although we have no idea how to implement it. Now let’s understand the terminology related to trees

Let’s start by making a list

The term meaning
node Every element in a book is called a node
Depth of node The number of its ancestor nodes
The height of the tree Maximum depth of all nodes
Internal nodes A node with at least one child node
External node A node with no child elements
The degree of node Number of subtrees owned by a node
A leaf node A node of degree 0

So what do we mean by each of these

The first node at the top of the tree, called the root node, has no parent, node 1

Each element in the tree is called a node

Nodes without child elements are also called external nodes, such as nodes 4,5 and 7 in the figure, which have no child elements

The remaining nodes are internal

A node has an attribute called depth, which depends on the number of ancestor nodes. For example, node 5 in the figure has two ancestor nodes, 2 and 1, so its depth is 2

For a tree, it has a height, and the height depends on the maximum node depth, which is node 7, which has a depth of 3, so the height of the tree is 3

The degree of the node, the degree is the number of subtrees that the node has. For example, node 1 has two subtrees, so the degree of node 1 is 2. For node 3, it has only one subtree, so the degree of node 3 is 1

For leaf nodes, that is, nodes with degree zero, that is, nodes with no subtrees, such as the nodes in the figure (4,5,7), these are called leaf nodes

What are the types of tree structure

For a tree it’s all kinds of things, it has many forms, for example

The most common binary tree, binary search tree

And of course it has

  • Red and black tree
  • Avl tree
  • N fork tree
  • Balanced binary tree…

There are a lot of different types, but I’m going to focus on binary trees, because the other ones are a little hard to learn

Binary tree: A node can have a maximum of two child nodes, one on the left and one on the right. The figure shows a binary tree

Binary search tree: the left node stores small values and the right node stores large values, so from left to right and from small to large. This is a binary search tree

4. Tree traversal before, middle and after order

For tree traversal, we have three conventional methods, pre-order traversal, middle-order traversal, post-order traversal

1. Preorder traversal

The order of foreorder traversal is: root node -> left child node -> right child node. For subtrees, traversal also follows this rule, as shown in the figure

Try it yourself with code oh ~~

2. Middle order traversal

The middle order traversal is as follows: left subtree -> root node -> right subtree, as shown in the figure

Recursive code implementation

const inorder = (root) = > {
    if(! root) {return }
    inorder(root.left)
    console.log(root.val);
    inorder(root.right)
}
Copy the code

3. Back-order traversal

The order of the back-order traversal is left subtree -> right subtree -> root node, as shown in the figure

const postorder = (root) = >{
    if(! root) {return}
    // First access the left subtree, then access the right subtree
    postorder(root.left)
    postorder(root.right)
    // Finally access the root node
    console.log(root.val);
}
Copy the code

How is the pre-traversal code implemented? Try it out for yourself. Try recursion and iteration

5. Tree sequence traversal

In LeetCode brush questions, there are often such questions, need to be traversed according to the hierarchy, what does it mean

It means: access all nodes layer by layer, from left to right

That is, iterate the way the diagram shows and return the result

Results: [[3], [9,20], [15,7]]

That is, the elements of each layer are returned in an array. How do you do that?

  • First we need to add hierarchical judgment on the basis of breadth-first traversal
  • The number of nodes in the current hierarchy is recorded, and when the current hierarchy is completed, the traversal continues from the next array
var levelOrder = function (root) {
    / / empty tree
    if(! root)return []
    // queue breadth-first traversal,[root node, hierarchy]
    const q = [
        root
    ]
    const res = []
    while (q.length) {
        // Record how many nodes are left over from the previous loop. These nodes are all nodes in the current hierarchy
        let len = q.length
        res.push([])
        // Unqueue all of these nodes
        while (len--) {
            const n = q.shift()
            res[res.length - 1].push(n.val)
            if (n.left) q.push(n.left)
            if (n.right) q.push(n.right)
        }
        // In the next outer loop, a new empty array is created
    }
    return res
};
Copy the code

What are the methods of binary search tree?

Here are a few common ones

methods role
insert Inserts data into the binary search tree
serach Find a value
remove Remove a value

There’s a whole bunch of other ways that you can do things like return a maximum, return a minimum, but I’m not going to write that much here

Seven, handwritten realization of binary search tree

1. Create the Node class

Create a node class to instantiate to create a new node. The binary search tree has a maximum of two nodes

This class is used to create a node. The default value is NULL. Both the left and right child nodes are null

class Node {
    constructor(data = null, left = null, right = null){
        this.data = data
        this.left = left
        this.right = right
    }
}
Copy the code

2. Create BinarySearchTree

The method used to add the entire tree

class BinarySearchTree {
    constructor() {
        this.root = null}}Copy the code

3. Implement insert method

Insert method to insert an element, according to the characteristics of binary search multi-tree, the left subtree value is less than the right subtree value, we need to design a reasonable insertion method

  • First we need to create a new node and pass it indataAnd node data
  • If the first node is inserted, that node is the root node
  • If it is not the first node to insert, then we need a function to assist the insertion
insert(data) {
    const newNode = new Node(data)
    // insertNode is an auxiliary function
    this.root === null ? this.root = newNode : insertNode(this.root, newNode)
}
Copy the code

Here we write insert method, simple logic, whether or not the root node, the next processing to the insertNode function to achieve

How do you do that?

According to the characteristics of binary search tree, we use recursive method

  • First, determine the size relationship between the incoming node and the root node
  • If it’s smaller than the root, it goes to the left subtree, and vice versa
  • If the current left (right) subtree is empty, it becomes the first node in the left tree
  • If it is not empty, we then compare it to the left (or right) subtree size to achieve recursion
function insertNode(node, newNode) {
    // If the value is less than the root node, insert the left subtree
    if(newNode.data < node? .data) {// If there is no left subtree, it is the left node
        if (node.left === null) {
            node.left = newNode
        } else {
            / / recursion
            insertNode(node.left, newNode)
        }
    }else {
        if(node.right === null) {
            node.right = newNode
        }else {
            insertNode(node.left,newNode)
        }
    }
}
Copy the code

Now that we’ve implemented an insert method, let’s see how it works

const tree = new BinarySearchTree()
tree.insert(344)
tree.insert(31114)
tree.insert(324)
tree.insert(34)
Copy the code

See the record in the debugger panel, as we expected

Let’s see how the insertion is implemented step by step

const tree = new BinarySearchTree()
tree.insert(15)
tree.insert(31)
tree.insert(6)
tree.insert(48)
Copy the code

Implement the search method

The search method needs to receive a lookup value, and we return true or false. This is similar to the has method before. So how do we do that?

Again, we need a helper function to do this

  • First of all, let’s make a statementsearchMethod, passing in the tree and the value to look up
  • When our tree is empty, it must be impossible to find a value
  • When looking fordataLess than the root nodedata, we need to recurse the left subtree to continue the judgment
  • When greater than the root node, recursive right subtree judgment
  • Returns if exactly equal to the root nodetrue

Implement the search method

search(data) {
    return searchNode(this.root, data)
}
Copy the code

Implement the searchNode method to implement the lookup

function searchNode(node, data) {
    if (node === null) {
        return false
    }
    if (data < node.data) {
        return searchNode(node.left, data)
    } else if (data > node.data) {
        return searchNode(node.right, data)
    } else {
        return true}}Copy the code

How does that work? Let’s try it out

const tree = new BinarySearchTree()
tree.insert(59)
tree.insert(29)
tree.insert(48)
tree.insert(18)
tree.insert(79)
tree.search(48)
tree.search(1)
Copy the code

5. Implement the remove method

The remove method removes a node. This method is the most complex of all, with many things to consider

There are three types of node deletion

  1. Delete leaf nodes
  2. The node to be deleted has only one child node
  3. The node to be deleted has two children

How do we do that, step by step

First we need to implement a removeNode function to keep our class clean. We declare the remove method, where we expect removeNode to return the root node

remove(data) {
    this.root = removeNode(this.root, data)
}
Copy the code

To implement the removeNode method

So let’s do some boundary judgment work first

Here we first deal with the empty tree, when the tree is empty return null, then we need to delete the node search, the use of recursive implementation, when we find this node, the current node will point to the node to delete, and then judge

function removeNode(node, data) {
    if (node === null) return null
    if (data < node.data) {
        node.left = removeNode(node.left, key)
        return node
    } else if (data > node.key) {
        node.right = removeNode(node.right, key)
    } else {
        // Three cases}}Copy the code

If both left and right are null, delete the current node (node = null)

if(node.left === null && node.right === null) {
    node = null
    return node
}
Copy the code

Second case: Delete a node that has only one child node

In this case, we need to skip the current node and point to its child node, so to speak, replacing it with its child node

if(node.left === null) {
    node = node.right
    return node
}else if(node.right === null) {
    node = node.left
    return node
}
Copy the code

Third case: delete a node with two child nodes

This situation is the most complicated

  1. Find the minimum value in the right subtree of the node
  2. Then use this minimum value to replace the current deleted node
  3. Then we need to delete that node in the right subtree
  4. Finally, a reference to the updated node is returned

Here we’re using a method called findMinNode that we’ve wrapped ourselves, and you can try it yourself, and what it does is it returns the smallest node, okay

const min = findMinNode(node.right)
node.data = min.data
node.right = removeNode(node.right,min.data)
return node
Copy the code

So we’ve got all three cases, and together they work

Here we have achieved a few very common methods, the difficulty is quite large, need to practice more

LeetCode actual combat

Here are some Leetcode questions to try

  • 104. Maximum depth of a binary tree

  • 111. Minimum depth of a binary tree

  • 102. Sequence traversal of binary trees

  • 112. Sum of paths

  • 96. Different binary search trees

  • 98. Validate binary search trees

  • Restore binary search tree

  • 226. Flip the binary tree

These questions can try oh ~

📖 summary

In this article, we started from what is a tree, and finally encapsulated a binary search tree, the difficulty is still some, do tree-related topics, we must straighten out our thinking, use recursion to determine the recursion order. When we do the topic; don’t wrap a complete tree, we need to know about the data structure, only when we need to use, we extract its soul, learned so much of the data structure, can be found that they are packaged with array or object, so their nature is our most familiar things.

That’s the end of this article on trees, and I’m sure you’ll learn a lot from it. The next article will take you through the mysteries of the heap.

The rest of this column

Start here 👉 [Dissolving data Structures] Start here with data structures and algorithms

Stack 👉 what is a stack? Handwriting a stack structure!

Queue 👉 explain queue, priority queue, circular queue, and implement a queue

Linked list 👉 [dissolve data structure] explain linked list structure in detail, and implement a linked list

Set 👉 [dissolve data structure] detail set structure, and realize a set

Dictionary 👉 [resolve data structure] detail dictionary structure, and implement a dictionary

You are welcome to follow this column and stay tuned for the latest articles

Finally, I may not be clear enough in many places, please forgive me

💌 if the article has any mistakes, or have any questions, welcome to leave a message, also welcome private letter exchange