二叉树篇

二叉树篇

定义：

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
性质：

• 每个节点最多有两个子节点。
  
• 子节点的顺序不能颠倒（即左子树与右子树有严格区分）。
  
• 二叉树的第 i 层最多有 2^(i-1) 个节点。
  
• 深度为 k 的二叉树最多有 2^k - 1 个节点。
  

常见类型：

• 满二叉树：要么没有子节点，要么有两个子节点。
  
• 完全二叉树：除了最后一层，其他层都被填满了，并且最后一层节点靠左排列。
  
• 平衡二叉树：任意节点左右子树高度差不超过1。
  
• 二叉搜索树：任意节点左子树小于该节点，右子树大于该节点。
  

二叉树的遍历

• 深度优先遍历（DFS）
  1.1 先序遍历：根左右
  1.2 中序遍历：左根右
  1.3 后序遍历：左右根
  
• 广度优先遍历
  2.1 层序遍历：一层一层的遍历
  

理解：

二叉树这种结构是链表结构的扩展，链表描述的是线性结构，显然数据的结构不仅仅是线性的，还有非线性的。例如：java中就充满了继承结构，实现结构，这些结构都是树形结构，而二叉树是树的一种特殊形式。
对二叉树的一些操作，本质上都是转化为遍历二叉树。例如：求二叉树的直径，其实就是转化成二叉树中存在的最大路径，而最大路径也就是路径上的节点数减一，这无疑需要遍历二叉树。再例如：二叉树的右视图，实际上也是一种遍历，只不过要得到特定的遍历顺序。
二叉树的操作同时常常与递归相关，这是因为对一个树的操作，可以利用分治的思想转化成对其子树的操作，因为其子树有着相同的结构，同样可以应用原操作。例如：二叉树的遍历：实际上也是子树的遍历，遍历的操作同样可以利用在子树上。
思想：

• 颜色标记法实现树的深度优先遍历（迭代）
  1.1 颜色标记节点状态，白色表示新节点（之前未访问过），灰色表示之前访问到的节点。
  1.2 遍历的节点为白色，将其标记为灰色，然后将其自身、右子节点、左子节点按一定次序入栈（调整入栈顺序即可实现先中后序遍历）
  1.3 遍历的节点为灰色，则将其输出。
  注意： 栈先进后出：前 根左右 => 右左中（入栈顺序）
  
• 递归过程计算机隐式记录了递归返回节点（通过栈），而循环迭代的过程则需要我们显示实现这个栈。在Java中，堆栈是通过双端队列实现的。
  
• 在写递归函数时，可以假设递归返回的结果一定是正确的，这个说法的本质其实就是数学归纳法。
  

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除