原料：class LinkStack<T>; 步骤： 将起始顶点压入栈中 弹出栈顶顶点 v， 判断是否已经标记（比较：转2； 未标记：转3） 标记顶点， 并将顶点 v 的邻接顶点压入栈中 判断栈是否为空（非空：转2； 空：结束）

图的选择 MatrixGraph vs ListGraph 如何选择 ？ 时间复杂度的对比分析 小结论 MatrixGraph 适用于内存资源富足的场合（性能较好） ListGrap 适用于内存资源受限的场合 （节省空间） 图的遍历 从图中的某一顶点出发，沿着一些边访问图中的其它顶点，使得每个顶点最多被访问一次。 注：从某个顶点出发进行遍历，不一定能...

邻接矩阵法中的残留问题 {代码...} MatrixGraph 无法动态 添加 / 删除 顶点！！！ 资源耗费大；N = 1000, 邻接矩阵的体积为 4 * 1000 * 1000 字节；因此，图对象创建时的体积约为 4MB ！！！ 基本思想 为了进一步提高空间使用率，可以考虑使用链表替代数组，将邻接矩阵换为邻接链表。 邻接链表法 图中的所有顶点按照编号...

基本思想 用一维数组存储顶点：描述顶点相关的数据 用二维数组存储边：描述顶点间的关系和权 邻接矩阵法 设图 A = (V, E) 是一个有 n 个顶点的图，图的邻接矩阵为 Edgen, 则： 注：解决工程问题时，习惯于对图中的每个顶点进行编号；当需要权值时，取 W 非空表示结点间有连接。 无向图邻接矩阵法 无向图的邻接矩阵是对称...

图的定义 图是由顶点集合（Vertex）及顶点间的关系集合（Edge）组成的一种数据结构 : Graph = (V, E) V = {X | X ∈ 某个数据对象} 是顶点的有穷非空集合E = {(x, y) | x, y ∈ V} 是顶点之间关系的有穷集合 图的分类 思考：G1,G2,G3,G4 都是图吗？有什么异同？可以继续分类吗？ 无向边 顶点 x 和 y 之间的边没有方向，则...

面试题 一 单结点删除描述：编写一个函数用于删除二叉树中的所有单度结点要求：结点删除后，其唯一的子结点替代它的位置 情形1：结点中包含指向父结点的指针 定义功能：delOdd1(node) 删除 node 为根结点的二叉树中的单度结点 编程实验：单度结点的删除 {代码...} 输出： {代码...} 情形2：结点中只包含左右孩子指针 定...

将二叉树转换为双向链表的过程（非线性 → 线性） 能够反映某种二叉树的遍历次序（结点的先后访问次序） 利用结点的 right 指针指向遍历中的后继结点 利用结点的 left 指针指向遍历中的前驱结点

SharedPointer<BTree<T>> clone() const 克隆当前树的一份拷贝 返回值为堆空间中的一颗新二叉树（与当前树相等）

先序遍历 （Pre-Order Traversal） 中序遍历 （In-Order Traversal） 后序遍历 （Post-order Traversal）

二叉树的遍历 （Traversing Binay Tree） 是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

二叉树的属性操作 二叉树中结点的数目 定义功能： count(node) 在 node 为根结点的二叉树中统计结点数目 编程实验：二叉树中结点的数目 {代码...} 二叉树的高度 定义功能：height(node) 获取 node 为根结点的二叉树的高度 编程实验：二叉树的高度 {代码...} 二叉树的度数 定义功能：degree(node) 获取 node 为根结点的二...

基于数据元素值的删除 SharedPointer<Tree<T>> remove(const T &value); 基于结点的删除 SharedPointer<Tree<T>> remove(TreeNode<T> *node);

插入新结点 bool insert(TreeNode<T> *node); bool insert(TreeNode<T> *node, BTNodePos pos); 插入数据元素 bool insert(const T &value, TreeNode<T> *parent); bool insert(const T &value, TreeNode<T> *parent, BTNodePos pos);

基于数据元素值的查找 BTreeNode<T> *find(const T &value) const; 基于结点的查找 BTreeNode<T> *find(TreeNode<T> node) const;

BTree 为二叉树结构，每个结点最多只有两个后继结点 BTreeNode 只包含四个固定的公有成员（1数据、1前驱指针、2后驱指针） 实现树结构的所有操作（增，删，查，等）

性质 1 在二叉树的第 i 层最多有 2i-1 个结点(i >= 1)。 第一层最多有 21-1 = 1 个结点 第二层最多有 22-1 = 2 个结点 第二层最多有 23-1 = 4 个结点 ... 性质 2 高度为 k 的二叉树最多有 2k-1 个结点(k >= 0)。 如果有一层，最多有 1 = 21-1 = 1 个结点 如果有两层，最多有 1 + 2 = 22 - 1 = 3 个结点 如果有三层...

通用树结构的回顾 双亲孩子表示法 每个结点都有一个指向其双亲的指针 每个结点都有若干个指向其孩子的指针 另一种树结构模型 孩子兄弟表示法 每个结点都有一个指向其第一个孩子的指针 每个结点都有一个指向其第一个右兄弟的指针 孩子兄弟表示法的特点 能够表示任意的树形结构 每个结点包含一个数据成员和两个指针成员 孩...

在树中定义一个游标 (GTreeNode<T> *) 遍历开始前将游标指向根结点 (root()) 获取游标指向的数据元素 通过结点的 child 成员移动游标

树中结点的数目 定义功能：count(node) 在 node 为根结点的树中统计结点数目 树结点数目的计算示例 count(A) = count(B) + count(C) + count(D) + 1 编程实验：树中结点的数目 {代码...} 树的高度 定义功能：height(node) 获取 node 为根结点的树的高度 树的高度示例 height(A) = MAX{ height(B), height(C), height(D) ...

基于数据元素的删除 SharedPointer<Tree<T>> remove(const T &value) 基于结点的删除 SharedPointer<Tree<T>> remove(TreeNode<T> *node)

清除操作的定义 void clear() 将树中所有的结点清除（释放堆中的结点） 树中数据元素的清除 清除操作功能的定义 free(node) 清除 node 为根结点的树 释放树中的每一个结点 编程实验：清除树中的结点 文件：GTree.h {代码...} 问题 树中的结点可能来源于不同的存储空间，如何判断堆空间中的结点并释放？ {代码...} 问题分...

插入新结点 bool insert(TreeNode<T> *node); 插入数据元素 bool insert(const T &value, TreeNode<T> *parent);

基于数据元素值的查找 GTreeNode<T> *find(const T &value) const; 基于结点的查找 GTreeNode<T> *find(TreeNode<T> *node) const;

GTree 为通用树结构，每个结点可以存在多个后继结点 GTreeNode 能够包含任意多个指向后继结点的指针 实现书结构的所有操作（增，删，查，等）

树是一种非线性数据结构 树是由 n(n>=0) 个结点组成的有限集合 如果 n = 0, 称为空树； 如果 n > 0, 则： 有一个特定的称之为根(root)的结点 根结点只有直接后继，但没有直接前驱 除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,...,Tm-1,每个集合又是一颗树，并且称之为根的子树(sub tree)

应用一 排序类(Sort(与数组类(Array)的关系 新增的成员函数 编程实验：排序类与数组类的关系 文件：Array.h {代码...} 文件：Sort.h {代码...} 文件：main.cpp {代码...} 输出： {代码...} 应用二 问题 当待排数据元素为体积庞大的对象时，如何提高排序的效率？ {代码...} 问题分析 排序过程中不可避免的需要进行交换操...

将 3 个有序序列归并为一个新的有序序列，称为 3 路归并 将 N 个有序序列归并为一个新的有序序列，称为 N 路归并 将多个有序序列归并为一个新的有序序列，称为多路归并

每次从后向前进行 （假设为第 i 次），j = n-1, n-2,...,i;两两比较 V[j-1] 和 V[j] 的关键字；如果发生逆序，则交换 V[j-1] 和 V[j]。

每次（例如第 i 次， i = 0,1,...,n-2） 从后面 n-i 个待排的数据元素中选出关键字最小的元素，作为有序元素序列 i 个元素。

例：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为:14,23,36,49,52,58,61,75,80,97