二叉树的遍历

前言

二叉树和链表在历年春招笔试中，都是重点考核对象。链表由于算法简单，一般考代码实现能力。二叉树考核遍历。

二叉树

二叉树是树形结构中比较简单的，它又可细分成完美二叉树，斜二叉树（相当于链表），完全二叉树。

二叉树的几个性质

1. 第 i 层最大结点数为 2^(i-1)
2. 深度为 k 的二叉树最大结点数为 2^k -1 (完美二叉树)

二叉树的遍历

• 先序
• 中序
• 后序
• 层次遍历

先序

从根节点->左子树->右子树

image.png

中序

先中序遍历左子树->根节点->中序遍历右子树

image.png

后序

先后序遍历左子树->再后序遍历右 子树->根节点

image.png

手写

IMG_20180110_205719.jpg