<style> .reveal p {text-align:left;} </style> # 二叉树 --- #### 1、二叉树定义 如果每个结点的子结点的数目最多为2个，则该树称为二叉树。  --- 特点： * 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。 * 左子树和右子树是有顺序的，次序不能任意颠倒。 * 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。 --- `满二叉树`：所有分支结点都有两个子结点，并且所有叶结点都在最后一层。 * n层的满二叉树：结点个数为 $1+2+4+...+2^{n-1} = 2^{n} - 1$ * 按从上到下、从左到右对结点编号： - 第i层编号为 $2^{i-1}$ 开始，到 $2^i - 1 $ 结束 - 对编号k的结点，其左子孩子编号为 $2\times k$, 右孩子为$2\times k+1$ - 对编号k的结点，其父亲（除根外）编号为$\lfloor \frac{k}{2} \rfloor$  --- `完全二叉树`：每个结点的位置与满二叉树的结点位置一样（但不一定满）。 --- ### 2、二叉树存储 对于完全二叉树，可以用一维数组进行存储，根据结点的父子关系就可以正常访问。 例子：上面的满二叉树 ``` char v[10] = "-ABCDEFG"; ``` 对于非完全二叉树，如果不想浪费空间（没有子结点的位置也被占用），可以继续用邻接表方式存储。 --- ### 3、遍历方式 二叉树的每个结点，加上其左孩子（子树）、右孩子（子树），一共三个部分，在遍历的时候，可以按照不同的次序进行遍历（孩子必须先左后右），共有三种： * 先序：根 左 右 * 中序：左 根 右 * 后序：左 右 根 对例子满二叉树来说： * 先序：A B D E C F G * 中序：D B E A F C G * 后序：D E B F G C A --- # 树的遍历 --- ### 树上 DFS 在树上 DFS 是这样的一个过程：先访问根节点，然后分别访问根节点每个儿子的子树。 可以用来求出每个节点的深度、父亲等信息。 --- ### 二叉树 DFS 遍历 --- #### 先序遍历  按照 **根，左，右** 的顺序遍历二叉树。 --- 实现 ```c++ void preorder(BiTree* root) { if (root) { cout << root->key << " "; preorder(root->left); preorder(root->right); } } ``` --- #### 中序遍历  按照 **左，根，右** 的顺序遍历二叉树。 --- 实现 ```c++ void inorder(BiTree* root) { if (root) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } ``` --- #### 后序遍历  按照 **左，右，根** 的顺序遍历二叉树。 --- 实现 ```c++ void postorder(BiTree* root) { if (root) { postorder(root->left); postorder(root->right); cout << root->key << " "; } } ``` --- #### 反推 已知中序遍历序列和另外一个序列可以求第三个序列。  --- 1. 前序的第一个是 `root`，后序的最后一个是 `root`。 2. 先确定根节点，然后根据中序遍历，在根左边的为左子树，根右边的为右子树。 3. 对于每一个子树可以看成一个全新的树，仍然遵循上面的规律。 --- ### 树上 BFS 从树根开始，严格按照层次来访问节点。 BFS 过程中也可以顺便求出各个节点的深度和父亲节点。 --- #### 树的层序遍历 树层序遍历是指按照从根节点到叶子节点的层次关系，一层一层的横向遍历各个节点。根据 BFS 的定义可以知道，BFS 所得到的遍历顺序就是一种层序遍历。但层序遍历要求将不同的层次区分开来，所以其结果通常以二维数组的形式表示。 例如，下图的树的层序遍历的结果是 `[[1], [2, 3, 4], [5, 6]]`（每一层从左向右）。  --- ## 例题与练习 |题目| |---| |[找树根和孩子](http://39.99.183.126:8888/p/YBTJ1336)| |[单词查找树](http://39.99.183.126:8888/p/YBTJ1337)| |[求后序遍历](http://39.99.183.126:8888/p/YBTJ1339)| |[小球](http://39.99.183.126:8888/p/YBTJ1363)| |[FBI树(fbi)](http://39.99.183.126:8888/p/YBTJ1365)| |[对称二叉树](http://39.99.183.126:8888/p/YBTJ1368)| |[Simple path](http://39.99.183.126:8888/p/abc270c)|