4. 树的概念
阅读信息
约 903 个字 3 分钟 本页总访问量：加载中... 次
Class Four
博弈树
- 用树解决零和博弈的问题(e.g.棋类)
- 每个节点的儿子表示下一步所有可能的走法,使用 minmax 算法和\(\alpha\beta\)剪枝
- 核心 1:评估每个节点.AlphaGo:根据之前人类棋谱学习,计算各种棋局获胜概率(收益)
- 核心 2:自己层取 max,对手层取 min
- 对围棋而言 minmax 计算量太大,利用蒙特卡洛按概率选择方向
树的概念
- 树和图的区别:树一定连通,没有回路.
- 对于图而言,连通,没回路,n 个点 n-1 条边,这三个条件知二推一
- 森林:树的集合
- degree of tree:每个节点有几个儿子;degree of graph:每个节点有几条出边
- 树上任何两点之间的 path 一定唯一
- depth:该点到根的距离
- height:该点到最低点的距离
树的实现
- 用链表,怎么解决每个节点儿子数不确定的问题?每个节点都有且仅有 FirstChild,NextSibling 两个指针
- 这样的树即化为二叉树
- 利用中缀表达式构建树：
- 读入数,存储指针
- 读入符号,抛出两个数,将符号的指针压入,抛出的数作为该符号的儿子
- 表达式前序遍历得到前序表达式，后序遍历得到后序表达式
- 遍历的本质:将二维结构变成一维的序列
- 线索树:根节点和叶节点浪费的指针指向遍历时的前一个点和后一个点.需要标记是指向的下一个节点还是根或叶的指针.每次判断是不是线索.
- 线索二叉树可增加哑头节点.
HW4
二叉树概念
- 树的度：一个节点有 m 个分叉，那么这个节点的度就为 m。叶子节点的度为 0，因为它没有分叉。二叉树节点的度只有 0，1，2 这三种，其中为 0 的肯定是叶子节点。
- 二叉树的深度：max(左子树深度，右子树深度)+1。
- 二叉树的分类
- 满二叉树：一棵深度为 k 且有个\(2^k-1\)节点的二叉树称为满二叉树。
- 完全二叉树：一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
- 平衡二叉树(AVL 树)：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。
- 完全二叉树的性质
- 在二叉树上的第 i 层上至多有\(2^{i-1}\)个节点(i>=1)
- 深度为 k 的二叉树至多有\(2^k-1\)个节点(k >= 1)
- 比较重要的一条性质：n0、n1、n2 分别代表度数为 0、1、2 的节点总数。n 为总结点数，则有： n=所有节点度之和+1 (所有树的性质) \(n_0=n_2+1;\) (满二叉树\(n_0=2^k,n_2=2^k-1\),非满二叉树\(n_0,n_2\)同时减小) \(n=n_0+n_1+n_2;\) \(分支总线=n-1=n_1+2n_2;\) (连通无回路图的边为 n-1，将 n0 用 n2 代入)
线索二叉树
-
线索二叉树的基本概念：
-
对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树(Threaded binary tree)。
-
引入线索二叉树的目的是：加快查找结点前驱和后继的速度。
-
线索二叉树的构造
-
线索二叉树的存储结构：lchild ltag data rtag rchild
- ltag=0,表示指示节点的左儿子;ltag=1,表示指示节点的前驱.rtag=0,表示指示节点的右孩子;ltag=1,表示指示节点的后继.