1. Define a binary tree node class as follows:

class Node {
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right
    }
    show() {
        console.log(this.data); }};Copy the code

2. Define a Tree class and set root to null

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

3. Insert operation of binary tree

    insert(data) {
        var node = new Node(data,null.null);
        if (!this.root) {
            this.root = node;
            return ;
        }
        var current = this.root;
        var parent = null;
        while (current) {
            // Parent always points to the root node of the subtree, and current is a pointer to the child node of the child root node.
            parent = current;
            if (data < parent.data) {
                current = current.left;
                if (! current) {
                    parent.left = node;
                    return; }}else if( data > parent.data){
                current = current.right;
                if(! current) { parent.right = node; }}else {
                return; }}}Copy the code

First define a node and assign the data to be inserted to the node. Define a parent that always points to the root node of the subtree. Then define a current pointer if data < current-data, current = current-left. The current pointer moves Douyao each time to check whether current is null. Parent. left = node or parent.right = node. Current is always one layer below parent.

4. Recursive traversal of binary trees

    // The node passed is the root node
    preOrder(node) {
        if (node) {
            node.show();
            this.preOrder(node.left);
            this.preOrder(node.right); }}// middle order traversal
    middleOrder(node) {
        if (node) {
            this.middleOrder(node.left);
            node.show();
            this.middleOrder(node.right); }}// after the sequence traversal
    laterOrder(node) {
        if (node) {
            this.laterOrder(node.left);
            this.laterOrder(node.right) node.show(); }}Copy the code

5. Obtain the maximum and minimum values of the binary tree

    // Get the minimum value of the binary tree
    getMin() {
        var current = this.root;
        while (current) {
            if (! current.left) {
                returncurrent } current = current.left; }}// Get the maximum value of the binary tree
    getMax() {
        var current = this.root;
        while (current) {
            if (! current.right) {
                returncurrent } current = current.right; }}Copy the code

To get the minimum value is to traverse all the nodes of the binary tree to the left. Check if current. Left is null, if current is null, return current, otherwise current = current. Left Continue the loop.

The way to get the maximum is the same as the way to get the minimum, which is to traverse the right node of the binary tree.

Get the height of the binary tree

    // Get the height of the binary tree
    getDeep(node,deep) {
        if (deep === undefined) {
            deep = 0
        }
        if (node === null) {
            return deep;
        }
        deep++;
        var dleft = this.getDeep(node.left,deep);
        var dright = this.getDeep(node.right,deep);
        return Math.max(dleft,dright);
    }
Copy the code

Return deep if node === null; return deep if node! ==null, deep adds one and continues to look for the left and right nodes of the node.

Finally return the larger of the left and right heights.

7. Tree search

    / / tree search
    getNode(data,node) {
        if (node) {
            if (data === node.data) {
                return node;
            }else if(data < node.data) {
                return this.getNode(data,node.left);
            } else {
                return this.getNode(data,node.right); }}else {
            return null; }}Copy the code

conclusion

The basic operation on binary trees is usually to use a current pointer, which is set to either current-. left or current-. right if one of the conditions is met. Continue the loop. I’ll do that next time for the specific problem of binary trees.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign