Chapter 4：Trees

1. 定义：
1. 树是一些节点的集合
2. 树是没有环路的（使用快慢指针进行判断）
3. 树是一种十分特殊的图
4. 树的每个节点是子树的根节点
5. 所有的算法基本都是递归的
6. 每棵子树的根叫做 root 的儿子（children），root 是每棵子树根的父亲（parent）
1. 没有孩子的节点称为树叶
2. 节点的儿子的数量称为这个节点的度
1. 所有节点度数的最大值称为这个树的度
3. 只有一个节点，不能是parent和children，因此必须含有至少两个节点
7. 如果一棵树上有个节点，那么就有个边
8. 对应的是同一个parent是兄弟树
9. path from to是唯一确定的，并且长度是边的数量
10. 高度/深度：从根节点开始算起（深度），从叶节点开始算起（高度）
1. 树的高度是指所有节点中最大的高度，算所经过边的个数
2. 向上和向下是不一样的

2. 树的表示：
1. 列表表示：
1. 如下图所表示

2. 链表表示：
1. 如下图所表示
2. 指针的数目是动态的

3. FirstChild-NextSibling 表示法
1. ⚠️一棵树儿子的顺序没有确定，每棵树表示的方法可能不一定
2. sibling的关系是一定的，不影响结果
3. 下面使用代码进行表示：

3. 二叉树(Binary trees)
1. A binary tree is a tree in which no node can have more than two children.
2. 表达式：
1. infix 中缀表达式，postfix后缀表达式
2. 首先将中缀表达式化为后缀表达式
3. 所有的操作符都是根节点，操作数都是叶节

3. 树的遍历：
1. 无论哪个节点的遍历都是线性的
2. 先序遍历(preorder)
1. 根→左→右
2. 伪代码实现

3. 后序遍历（postorder）
1. 根→右→左
2. 伪代码实现

4. 层次遍历
1. 从上到下，从左到右
2. 伪代码实现：

5. 中序遍历（infixorder）
1. 左子树→根节点→右子树
2. 只适用于二叉树
3. 伪代码实现

4. 线索二叉树
1. 如果一个节点的左儿子为空，那么它的左指针指向它的中序遍历前驱节点
2. 如果一个节点的右儿子为空，那么它的右指针指向它的中序遍历后继节点
3. 一定有一个 head node，左儿子为根，右儿子为自己



目的是：加速中序遍历的速度

二叉树(Binary Tree)

• 在二叉树中，左子树和右子树是完全不同的

• the maximum number of nodes on k depth is



关键在于引入Branch的概念
知道四个量中的其中两个就可以求出答案

二叉搜索树(Search Tree ADT — Binary Search Trees)

1. 静态数据搜索→→查找数据→
2. 动态数据检索→二叉搜索树→哈希树
3. 互联网的核心在于做搜索
• 二叉搜索树（binary search tree）是一种二叉树，非空情况下服从以下性质：
• 所有节点都有不同的 key（一个整数）
• 一个节点的左子树的所有节点的 key 都小于这个节点的 key
• 一个节点的右子树的所有节点的 key 都大于这个节点的 key
• 左子树和右子树也都是二叉搜索树
• 二叉搜索树的中序遍历是有序的
• ADT：用处是用来做动态查询的
• 操作：
• 插入和删除本质上也是一种查找
• 查找：（递归或者是迭代）
• 从根节点开始进行查找
• 如果小于节点的值，就会进入左子树
• 插入：（本质是查找）
• 删除：
• 中序遍历的时候是一个递增序列
• 删除叶节点：直接删除即可
• 删除只有一个儿子的节点：直接删除，然后把儿子接上
• 删除有两个儿子的节点
• 将该节点替换为左子树的最大值，或右子树的最小值
• 随意选择即可
• 递归删除左子树的最大值，或右子树的最小值
• 代码是这样实现的：
• 树的高度取决于：The height depends on the order of insertion.
• 插入的顺序

第六章 树与二叉树