526互联

二叉树

发布时间 2024-01-08 19:35:36作者: __Zed

概念

  1. 满二叉树：节点总数2^k -1
    image

  2. 完全二叉树：除了底层外，其他都满，而且底层必须从左到右连续
    image

  3. 二叉搜索树：左子树都小于中间节点，右子树都大于中间节点（子节点也必须满足左小右大）
    image

  4. 平衡二叉搜索树：左子树和右子树的高度差不超过1
    image

map set multimap multiset底层都是平衡二叉搜索树

存储方式

  1. 链式存储：用链表
    image

  2. 顺序存储：用数组（实际上很少应用）找到某节点的子节点 2k + 1 / 2k + 2
    image

遍历方式

  1. 深度优先遍历（一般通过递归实现，也可以迭代）：攒着一个方向一直搜到最后，然后回退，搜下一个方向
  • 前序 中左右
  • 中序 左中右
  • 后序 左右中
  1. 广度优先遍历：一层一层的搜索（迭代法，队列）
  • 层序
struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x),left(NULL),right(NULL){}
}