[数据结构与算法]JavaScript数据结构（四）：树

概述

节点的度：节点的子树个数。
树的度：树的所有节点中最大的度数。
树的深度：树中所有节点的最大层次

二叉树特性

第i层的最大节点数：2^(i-1)
深度为k的最大节点数总数：2^k-1
对于任何非空二叉树T，若n0表示叶节点的个数，n2是度为2的非叶节点个数，那么两者满足关系：n0=n2+1

二叉树的遍历

给定二叉树
实现二叉树：

class TreeNode(val, left, right) {
	this.val = (val === undefined? null: val);
	this.left = (left === undefined? null: left);
	this.right = (right === undefined? null: right);
	}
let root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3); 

前序遍历

var preorderTraversal = function(root) {
	let number  = [];
	if(node) {
			number.push(node.val);
			number.push(...preorderTraversal (node.left));
			number.push(...preorderTraversal (node.right));
		}
	return number;
};

中序遍历

var inorderTraversal = function (root) {
    let number = []
    if (node) {
		number.push(...inorderTraversal (node.left));
		number.push(node.val);
		number.push(...inorderTraversal (node.right));
    }
    return number
}

后序遍历

var postorderTraversal = function(root) {
    let number = []
    if (node) {
		number.push(...postorderTraversal (node.left));
		number.push(...postorderTraversal (node.right));
		number.push(node.val);
    }
    return number
};

层序遍历

var averageOfLevels = function(root) {
    let queue = [], res = [];
    if (root !== null) {
        queue.push(root);
    }
    while (queue.length !== 0) {
        let size = queue.length;
        res.push(node.val);
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node.left !== null) {
                queue.push(node.left);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
        }
    }
    return res;
};

BFS:：队列，枚举所有可能
DFS：递归，找到目标就不再找