5. 树的遍历和特殊的树
阅读信息
约 575 个字 2 分钟 本页总访问量：加载中... 次
Class Five
前序,中序,后序和栈
- 前序,中序推后序:前序确定根,中序确定左右子树的集合
- 中序,后序推前序:后序确定根,中序确定左右子树的集合
- 前序,后序推中序:不能实现,因为不能确定子树在左还是在右.
- e.g. 前序 AB,后序 BA
- 树的堆栈操作:一直向左 push 到底,到叶节点时 pop 一个元素,再从 pop 出的元素开始向右走.
- 栈推前序:push 的顺序
- 栈推中序:pop 的顺序
- 栈推后序:
- 第一个 push 的是根.
- 后面 push 的元素,如果前一个是 push,则是左儿子;如果前一个是 pop,则是 pop 出元素的右儿子
- 树和栈
- 每个合法的堆栈操作序列,都唯一确定一棵树.
- m 个节点构成的树,共有 Catalan(n)种.\(C_n=\sum\limits_{i=0}^{n-1}C_iC_{n-i-1}\)
- Catalan 数递推:m 个节点左右分配
几种特殊的树
Skewed Binary Trees 偏斜二叉树
Complete Binary Trees 完全二叉树
- 优点:能用数组存储
- 第 k 层,这一层最多节点数为\(2^{k-1}\),所有层最多节点数\(2_k-1\)
- \(n_0=n_2+1\) Pf:从下往上,总边数为 n0+n1+n2;从下往上,总边数为 n1+2n2.联立两式得到.
Binary Search Trees 二叉搜索树
每个节点左子树均比其小,右子树都比其大.
- find:每次向左或向右查找 使用尾递归实现.所有尾递归都能化成循环.
- insert:先向左或向右找到合适位置,走到 NULL 时 malloc 内存,将 NULL 变为节点.
- delete:
- 没有儿子或只有 1 个儿子:直接删除
- 有 2 个儿子:从左子树找最大值(或右子树找最小值),替换要删除的节点,再在左(或右)子树种删除相应值. PS:每次删除操作多,可使用懒标记(lazy tag).
平衡树
几种决定是否平衡的指标:
- AVL 树(平衡树) 由左右子树的高度决定.任意节点,左右子树高度相差为 0 或 1,认为树平衡.
- 红黑树 将每个节点标记为红或黑.任意分支满足: 1. 第一个和最后一个节点为红 2. 红节点数相同 3. 黑节点不相邻 则认为该树平衡. 平衡的红黑树最长分支和最短分支最多相差 1 倍.
- B+树 满足所有分支节点数最多为 m,最少为 m/2,所有叶节点在同一层的树,认为平衡. B+树应用于数据库管理.