二叉树与并查集

树的基本概念

可见于数据结构和算法的笔记，更加详细

1. 空树
2. 树的特性
   • 任意一个树的两个节点，有且只有一条边
   • 一个节点数为n的树，边的数量是n-1
   • 任意一个数加一条边就会变成图，也就是有回路

二叉树

1. 二叉树是有序树

2. 斜树

   全是右子树或者左子树

3. 满二叉树

   叶子全部出现最底层

4. 完成二叉树

   底层可以不完全存在，但是需要优先左子树

5. 第i 层具有2^1-1^个节点

6. 深度为k的树，最多有2^k^-1个节点，

7. 度为2的节点数为n，那么叶子节点而数量是2*n

8. 在完全二叉树中，如果一共有n个节点，那么右[log2 n]+1的层，[log2 n]是向下取整

9. 遍历

   • 前序：根，左，右
   • 中序：左，根，右
   • 后序：左，右，根

并查集

1.