知识卡片
树的图表示还需保留左右位置
从父指向孩子可把二叉树画成DAG:根入度0,其余节点入度1,各节点出度至多2,所有节点从唯一根可达。只满足“无环、出度最多2”还可能是多根森林或有共享孩子的DAG,不足以定义一棵二叉树。
此外二叉树区分左孩子与右孩子,普通无序邻接Set只存两个孩子时会丢掉这种位置语义,尤其仅有一个孩子时无法知道它是左还是右。若要忠实转换,还需边标签、固定槽位等额外表示约定;本章未实现它。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
二叉树该如何用图来表示呢? 答:二叉树是一种带有如下属性的有向无环图:除了根结点外,每个结点最多只能作为两条边的起点,一条边的终点。根结点本身只能作为两条边的起点。由某顶点出发的边与顶点的子结点相连。而终结于某顶点的边与该顶点的父结点相连。因此,每个顶点的邻接表都包含自己的子结点。
参考来源
- 位置:《算法精解:C语言描述》第11章《问与答》(spine1334;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1301.html;u201-ch11-026)。
- 结论依据:201末问完整问答与前文BiTree左右指针/邻接Set无序定义直接对照,补全根可达和位置语义边界,不把本书简答当无损转换代码。
- 原始内容:二叉树该如何用图来表示呢? 答:二叉树是一种带有如下属性的有向无环图:除了根结点外,每个结点最多只能作为两条边的起点,一条边的终点。根结点本身只能作为两条边的起点。由某顶点出发的边与顶点的子结点相连。而终结于某顶点的边与该顶点的父结点相连。因此,每个顶点的邻接表都包含自己的子结点。