【算法详解】二叉树（Binary Tree）

[SilenceHVK]

什么是二叉树

  二叉树是一种具有层级特性的数据结构，它是由一系列节点组成，其每个节点最多只能有两个子节点。 如图所示：

• 节点值：节点所表示的值；

• 孩子节点：一个节点的子节点，称之为该节点的 孩子节点；节点的左子节点，称为 左孩子节点；节点的右子节点，称为 右孩子节点；

• 根节点：一个节点位于树的顶部，并没有父节点；

• 叶子节点：一个节点位于树的最底部，并没有孩子节点；

• 节点层：根节点的层定义为 1；根的孩子节点为第二层，一次类推；

• 树的深度：树中最大的节点层；

二叉排序树

  二叉排序树，又称为二叉查找树，二叉搜索树。其特点为，左子树上所有的节点值均小于它的根节点值，右子树上所有的节点值均大于它的根节点值。且没有相等的节点值 如图所示：

二叉排序树的创建

• JavaScript

'use strict'

class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    insertNode(newNode) {
        /**
         * 二叉排序树的定义：
         * 左子树上所有子节点均小于其根节点，
         * 右子树上所有的子节点均大于其根节点
         */
        if (this.key > newNode.key) {
            if (this.left === null) {
                this.left = newNode;
            } else {
                this.left.insertNode(newNode);
            }
        } else {
            if (this.right === null) {
                this.right = newNode;
            } else {
                this.right.insertNode(newNode);
            }
        }
    }
}

function BinarySortTree(nodes) {
    let root = null;
    if (nodes && nodes.length > 0) {
        nodes.forEach(item => {
            const newNode = new Node(item);
            if (root === null) {
                root = newNode;
            } else {
                root.insertNode(newNode);
            }
        });
    }
    return root;
}