Day11:[资料结构]Binary Tree - 二元树

想必大家在刷leetcode时候，刷到特定的题目的时候都曾经看过这样的图片，这就是Binary tree，但在认识Binary tree之前，让我们先来认识tree这种资料结构吧!

图片来源:101. Symmetric Tree

Tree

是一种抽象的资料结构，由一个以上的节点所组成，每个节点可以有多个子节点，最顶端的根节点称为root ，最下面的层级的节点称为leaves(2, 1, 7 …)

图片来源:working-with-trees

而节点与节点之间的关系名词可以参考下图

图片来源:understanding-binary-search-trees-4d90

Root - 根节点，最上层的节点
Edge- 节点与节点之间的连结
Parent - 父节点，与节点相邻的上层节点
Children - 子节点，与节点相邻的下层节点
Siblings - 兄弟节点，层级在同一层，而且拥有共同的父节点
Leaf nodes - 叶子节点，没有子节点的节点
Subtree - 子树，该节点以及其左右子节点
Height - 树的高度，可以解读为树有几层

Binary Tree(二元树)

每个节点的子节点最少0个，最多2个，每个节点会纪录三种资料

自己本身的值
left-child，左子节点
right-child，右子节点

图片来源:Binary Tree

与一般树的比较如下，Binary Tree每个节点最多就是两个子节点

图片来源:difference-between-general-tree-and-binary-tree

Binary Tree的种类

图片来源:5-types-of-binary-tree-with-cool-illustrations

full

所有的leaf node都在同一个层级
每个节点的子节点为0个或是2个

Complete

除了最後一层leaf node之外，每层都是填满的状态
所有的leaf node都会向左靠拢，因此leaf nodes有可能会没有右边的兄弟节点

Degenerate

每个节点只会有一个右子节点或是左子节点

Perfect

所有的leaf node都在同一个层级
除了leaf node之外，每个节点都有两个子节点

Balance

左子树和右子树的层级相差不超过1

Skewed

每个节点固定只有右子节点或左子节点，如下图

Skewed Binary Tree,图片来源:binary-tree

Binary Search Tree(缩写BST) - 二元搜寻树

具有Binary Tree的特性，每个节点的子节点不超过2个，除此之外，左边的子节点必定小於根节点，右边的子节点必定大於根节点，因此整棵树最左边的节点必定是最小的，最右边的节点必定是最大的，也因为Binary Search Tree这样的特性，所以不管是新增节点、删除节点、搜寻节点的时间复杂度都是O(log n)。

图片来源:implementing-binary-search-tree

用js实作出Binary Search Tree

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
        this.queue = [];
    }
    insertNode(value) {
        let current = new TreeNode(value);
        let target = null;
        let nowPos = this.root;
        while (nowPos !== null) {
            target = nowPos;
            if (current.value < nowPos.value) {
                nowPos = nowPos.left;
            } else {
                nowPos = nowPos.right;
            }
        }
        if (target === null) {
            this.root = current;
        } else if (current.value < target.value) {
            target.left = current;
        } else {
            target.right = current;
        }
    }
}

let tree = new BinarySearchTree();
tree.insertNode(10);
tree.insertNode(8);
tree.insertNode(11);
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(15);
tree.insertNode(2);
tree.insertNode(19);
tree.insertNode(13);

如果consolo.log(tree)可以看到我们成功用物件模拟出一颗Binary Search Tree