1:节点的度是子节点的个数
2:树的度是最大节点的度
3:子孙节点,一个点子树里面所有节点
4:森林是所有互不相交的树构成的集合
数学归纳法证明第i层最多有2^(i-1)个节点
证:只要看第n层满足,第n+1层满不满足
先边界n = 1 满足 Kn <= 2K(n-1) = 2 * 2^(n-1) = 2 ^ n
证明:任何一颗二叉树,n为总节点数 n1度为1的节点 n0度为0 结论n0 = n2 + 1
首先e = n - 1
n = n0 + n1 + n2; e = 0 * n0 + 1 * n1 + 2 * n2联立
n个节点二叉树深度为 log2 n 向下取整 + 1 推理 2(k-1)<=n<= 2k - 1
线索二叉树:分前中后,假设前序,如果没左儿子,就指向前序里面他的前驱,没右儿子指向后继
存树:1:只保存父节点 (并查集)
2: 邻接表
3: 左儿子右兄弟(二叉树和森林的转化)
树和森林只有前序遍历和后续遍历
森林F和二叉树T的转换
1:原树中叶子节点数 = 转换后的树中有右节点的节点数 + 1 (数学归纳法证明)
2: 原森林的前序遍历是转化后的前序,后序是转化后的中序 (证明递归相同)
根据前序和后序构造二叉树 , 如果所有节点的度数都为0 或者1 那么构造的二叉树唯一。 因为度为1的节点在左儿子和右儿子前序后续遍历是相同的
包含n个节点的不同二叉树个数就是第 n个卡特兰数,(C(2n,n) / (n + 1)
证明树问题1:数学归纳法2:先求点数,在求边数然后e = n - 1
平衡树(AVL)
平衡因子概念
有n个节点的平衡树高度是logn , 左旋和右旋操作
表达式树