理解树

树的定义

**树（Tree）**是n(n>=0)个结点的有限集。线性表是一对一的结构，而树则是一对多的结构。

定义条件：(1) 有且仅有一个根结点。(2) 子树的个数没有限制，但一定互不相交。

树的结点包含一个数据元素及若干个指向子树的分支。

百度百科的定义：

树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树

二叉树

**二叉树（binary tree）**是一种特殊的树结构

特点是

每个结点最多有2棵子树
左子树和右子树是有顺序的，
即使某结点只有一棵子树也要区分它是左子树还是右子树。

实现二叉树

js
二叉树的最小元素是节点，所以先定义一个节点
function Node(data, left, right) {
    this.left = left;
    this.right = right;
    this.data = data;
    this.show = () => {
        return this.data
    }
}
class BinaryTree {
    constructor() {
        this.root = null;
    }

    // 向二叉树插入节点
    insert(data) {
        var node = new Node(data, null, null);
        if (this.root === null) {
            this.root = node;
        } else {
            //设根节点为当前节点
            var current = this.root;
            var parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left; //到左子树
                    if (current === null) {
                        //如果左子树为空，说明可以将node插入在这里
                        parent.left = node;
                        break; //跳出while循环
                    }
                } else {
                    current = current.right;
                    if (current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }
    }

}

const tree = new BinaryTree()
tree.insert(10)
tree.insert(5)
tree.insert(6)

二查搜索树

二查搜索树：也称二查排序树或二叉查找树【BST】Binary Search Tree

二叉搜索树是一颗二叉树，可以为空

如果不为空，需要以下性质

非空左子树的所有键值小于其根节点的键值【较小的值保存在左节点中】

非空右子树的所有键值大于其根节点的键值【较大的值保存在右节点中】

左，右子树本身也都是二叉搜索树

步骤

1.Node 对象既保存数据，也保存和其他节点的链接（left 和right），show() 方法用来显示保存在节点中的数据

js
//二叉树的最小元素是节点，所以先定义一个节点
function Node(data,left,right) {
    this.left = left;
    this.right = right;
    this.data = data;
    this.show = () => {return this.data}
}

2.BST 先要有一个insert() 方法,用来向树中加入新节点
- 首先要创建一个Node 对象，将数据传入该对象保存。
3.其次检查BST 是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法到此也就完成了；否则，进入下一步。如果待插入节点不是根节点，那么就需要准备遍历BST，找到插入的适当位置。该过程类似于遍历链表。用一个变量存储当前节点，一层层地遍历BST。进入BST 以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循环。查找正确插入点的算法如下。 (1) 设根节点为当前节点。 (2) 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第4 步。 (3) 如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。 (4) 设新的当前节点为原节点的右节点。 (5) 如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。

二叉树

js
function BST() {
    this.root = null //初始化,root为null
}

BST初始化时，只有一个根节点，且没有任何数据。接下来，我们利用二叉查找树的规则，定义一个插入方法，这个方法的基本思想是:

如果 BST.root === null ，那么就将节点作为根节点
如果 BST.root !==null ，将插入节点进行一个比较，小于根节点，拿到左边的节点，否则拿右边，再次比较、递归。

最左变的叶子节点是最小的数，最右的叶子节点是最大的数

js
function insert(data) {
    var node = new Node(data,null,null);
    if(this.root === null) {
        this.root = node
    } else {
        //设根节点为当前节点
        var current = this.root;
        var parent;
        while(true) {
            parent = current; //把当前节点对象赋值给变量，利用同一对象指针指向
            if(data < current.data) {
                current = current.left; //到左子树遍历
                if(current === null) {  //如果左子树为空，说明可以将node插入在这里
                    parent.left = node; //改变parent，其实改变this.root，是指向同一对象地址
                    break;  //跳出while循环
                }
            } else {
                current = current.right;
                if(current === null) {
                    parent.right = node;
                    break;
                }
            }
        }
    }
}

使用了一个循环方法，不断的去向子树寻找正确的位置。循环和递归都有一个核心，就是找到出口，这里的出口就是当current 为null的时候，代表没有内容，可以插入

接下来，将此方法写入BST即可:

text
function BST() {
    this.root = null;
    this.insert = insert;
}

这样子，就可以使用二叉树这个自建的数据结构了:

text
var bst = new BST();
bst.insert(10); //根节点
bst.insert(8); //小于根节点，则在左节点
bst.insert(4); //大于根节点，则在右节点
bst.insert(7);
bst.insert(5);
console.log(bst.root, 'bst');

平衡二叉树

平衡二叉树定义(AVL)：（1）它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，（2）它的左子树和右子树都是一颗平衡二叉树。

二叉树的最大深度

js
function Node(data, left, right) {
    this.left = left;
    this.right = right;
    this.data = data;
}
class BinaryTree {
    constructor() {
        this.root = null;
    }

    // 向二叉树插入节点
    insert(data) {
        var node = new Node(data, null, null);
        if (this.root === null) {
            this.root = node;
        } else {
            //设根节点为当前节点
            var current = this.root;
            var parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left; //到左子树
                    if (current === null) {
                        //如果左子树为空，说明可以将node插入在这里
                        parent.left = node;
                        break; //跳出while循环
                    }
                } else {
                    current = current.right;
                    if (current === null) {
                        parent.right = node;
                        break;
                    }
                }
            }
        }
    }

}

// 定义二叉树
const tree = new BinaryTree()
tree.insert(10)
tree.insert(6)
tree.insert(11)


// 实现二叉树最大深度
const maxDepth = function (root) {
    let res = 0
    // 深度优先搜索 【Depth-First-Search，DFS】
    const dfs = (n, l) => {
        if (!n) return
        res = Math.max(res, l)
        console.log(n.data)
        dfs(n.left, l + 1)
        dfs(n.right, l + 1)
    }
    dfs(root, res)
    return res
}
const max = maxDepth(tree.root)
console.log(max);

// 优化算法
const maxDepth = function (root) {
    let res = 0
    // 深度优先搜索 【Depth-First-Search，DFS】
    const dfs = (n, l) => {
        if (!n) return
        //优化，只需要在叶子节点统计最大即可，不需要每次都统计
        if (!n.left && !n.right) {
            res = Math.max(res, l)
        }
        dfs(n.left, l + 1)
        dfs(n.right, l + 1)
    }
    dfs(root, res)
    return res
}

树的定义​

二叉树​

实现二叉树​

二查搜索树​

步骤​