JavaScript 二叉树相关性质
二叉树相关性质
-
节点的度：一个节点含有的子树的个数称为该节点的度；
-
叶节点或终端节点：度为零的节点；
-
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
-
树的高度或深度：树中节点的最大层次。
-
在非空二叉树中，第 i 层的结点总数不超过 2^(i-1)，i>=1。
-
深度为 h 的二叉树最多有 2^h-1个结点(h>=1)，最少有 h 个结点。
-
对于任意一棵二叉树，如果其叶结点数为 N0，而度数为2的结点总数为 N2，则 N0 = N2+1；
-
给定 N 个节点，能构成 h(N) 种不同的二叉树。h(N)为卡特兰数的第 N 项。(2n)!/(n!(n+1)!)。
-
二叉树的前序遍历，首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
-
二叉树的中序遍历，首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
-
二叉树的后序遍历，首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
-
二叉树是非线性数据结构，但是顺序存储结构和链式存储结构都能存储。
-
一个带权的无向连通图的最小生成树的权值之和是唯一的。
-
只有一个结点的二叉树的度为 0 。
-
二叉树的度是以节点的最大的度数定义的。
-
树的后序遍历序列等同于该树对应的二叉树的中序序列。
-
树的先序遍历序列等同于该树对应的二叉树的先序序列。
-
线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列： debxac，中序遍历中在x左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a 。
-
递归式的先序遍历一个 n 节点，深度为 d 的二叉树，需要栈空间的大小为 O（d），因为二叉树并不一定是平衡的， 也就是深度d！=logn，有可能d»logn。所以栈大小应该是O（d）
-
一棵具有 N 个结点的二叉树的前序序列和后序序列正好相反 ，则该二叉树一定满足该二叉树只有左子树或只有右子树， 即该二叉树一定是一条链（二叉树的高度为N，高度等于结点数）。
-
引入二叉线索树的目的是加快查找结点的前驱或后继的速度。
-
二叉树线索化后，先序线索化与后序线索化最多有1个空指针域，而中序线索化最多有2个空指针域。
-
不管是几叉树，节点数等于=分叉数+1
-
任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序不发生改变。
详细资料可以参考： 《n 个节点的二叉树有多少种形态》 《数据结构二叉树知识点总结》 《还原二叉树–已知先序中序或者后序中序》 《树、森林与二叉树的转换》
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
