2019-01-09感觉后面栈描述的过程像广度优先遍历呢作者回复: 栈是先进后出，还是深度优先。队列先进先出，适合广度优先
9- 2019-03-12对于思考题：
1. 图中结点之间的关系是 “邻居”， 树中结点之间的关系 “父子”，如果是无向图，“邻居” 之间是互通的，但是 “父子” 默认是单向关系，一般遍历从 “父” 到 “子”，子结点中一般不保留父结点的信息
2. 图和树不一样的是，图会存在 “环” 的概念，就是回路，树中永远不可能有回路，否则就不是一棵树
可以说链表是特殊的树，树是特殊的图。
综上所述，对比树，在一般的图中做深度优先搜索的区别就是：我们需要记录我们之前访问过的结点，防止重复访问作者回复: 分析得很到位
8 
2019-03-19用 python 实现了 DFS 和字典树，比起 C++ 简直不要简单太多，感觉有点暴殄天物……
### 在 python 中定义一个结点类
class Node:
def __init__(self, alpha, pre, exp):
self.alpha = alpha
self.prefix = pre
self.explanation = exp
self.sons = dict()
def find(self, alpha):
if self.sons.get(alpha) == None:
return False
else:
return True
def create(self, alpha, son):
self.sons[alpha] = son
self.sons = {key: self.sons[key] for key in sorted(set(self.sons))}
return True
def get(self, alpha):
return self.sons[alpha]
class DictTree:
def __init__(self, words, alpha=''):
self.root = Node(alpha, '', '')
self.build(words)
def build(self, words):
for word in words:
self.add(word)
def add(self, word):
cur_node = self.root
for i in word:
i = i.lower()
pre = cur_node.prefix + cur_node.alpha
if not cur_node.find(i):
cur_node.create(i, Node(i, pre, ''))
cur_node = cur_node.get(i)
cur_node.explanation = "This is a pyeudo explanation of '%s'" % word
def DFS_search(self, word):
word = word.lower()
cur_node = self.root
i = 0
while True:
if i == len(word):
if cur_node.explanation != '':
return cur_node.explanation
else:
return "The word '%s' is not in this dictionary." % word
if cur_node.find(word[i]):
cur_node = cur_node.get(word[i])
i += 1
continue
else:
return "The word '%s' is not in this dictionary." % word
DFS 的实现可以用 list 代替 stack，在“压入”时可以用 reversed 函数直接逆序。展开作者回复: 是的 Python简洁很多
3
2019-10-22老师遍历出所有的单词 是不是用explanation判断更合适，因为一个通路是可以有多个单词的。
public static void dfsByStack(){
Stack<TreeNode> stack = new Stack<>();
stack.push(headNode);
while(stack.size()>0){
TreeNode node = stack.pop();
if(!StringUtils.isEmpty(node.explanation)){
System.out.println(node.explanation);
}
Map<Character, TreeNode> sons = node.sons;
sons.forEach((sonKey,sonValue)->{
stack.push(sonValue);
});
}
}展开作者回复: 这也是可以的，适用于字典的应用场景👍
1
2019-08-23这里深度优先遍历的顺序和前一篇文章中的不太一样，区别在于前一篇文章中的深度遍历,当发现一个新节点的时候入栈，然后马上处理这个新节点也就是栈顶，这篇文章中是把一个节点相连的所有节点入栈，然后再处理栈顶元素，请问老师，我的理解是否准确？作者回复: 是的，一个只要访问最深的某条路径，一个是需要遍历所有路径
1
2019-02-24文中深度优先搜索代码，if else 分枝：
if (node.sons.size() == 0){
...
}else{
...
}
如果一个单词完全是另一个单词的前缀，打印出一个单词，另一个应该不会打印了，比如这种：
word_dict = {'successful': '成功的', 'success': '成功'}展开作者回复: 很好的发现，如果是这样，就是说不一定非要叶子结点才是一个单词，需要把每个点再设置一个状态，表明这个结点是不是一个合法的单词。我稍后修改一下代码。
1
2019-01-17老师讲解的树有多个分支，这里用C++简单演示了下二叉树的DFS。
/**
* Objective:Given a b-tree, do the depth-first-search(DFS) or traversal.
* Appraoch: stack, no recursion.
* Example:
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* Output:
* preorder: 1 2 4 5 3 6 7
*/
#include <iostream>
#include <stack>
using namespace std;
// tree node
class TreeNode {
public:
int data;
TreeNode* left = NULL;
TreeNode* right = NULL;
public:
TreeNode(int data)
: data(data) {
}
};
// depth-first-search
class DFS {
public:
void printDFS(TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
// begins!
while (!s.empty()) {
TreeNode* temp = s.top();
s.pop();
// push right first
if (temp->right != NULL) {
s.push(temp->right);
}
if (temp->left != NULL) {
s.push(temp->left);
}
// print data
cout << temp->data << " ";
}
}
};
// test!
int main(void) {
// build tree.
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
DFS test;
cout << "Depth-First-Search: " << endl;
test.printDFS(root);
}
输出：
Depth-First-Search:
1 2 4 5 3 6 7展开作者回复: 很好的实现，代码简洁
1 1
2019-01-10勘误：
栈是先进后出。
第3步将结点123、879、945和131压入栈中。
第4步，重复第2步和第3步弹出和压入的步骤，处理结点123，.....
123结点应该是最后处理的，应该先处理131.展开作者回复: 图里画的是对的，文字表达有歧义，我稍后改一下
1
2019-01-09广度优先一般用队列来做，FIFO，这样做到层级遍历；深度优先则用栈来做，FILO，这样做到按深度一条条的遍历下去。在实现上是这么区别的，我看上面有同学混淆了。作者回复: 总结的很好
1
2020-01-08如果在图中进行深度优先搜索，一个是要记录走过的节点，另外一个就是可能没有办法保障第一次就走完最长的路线，因为所有的点都是平级的，没有父子关系。所以，对图来说，是不是没有深度优先和广度优先的说法，只有遍历而已。- 2020-01-08在数学课里面看到关于用数据结构表达树，还是感觉有点奇怪，不过作者给出的 TreeNode 应该算是比较经典的一种，学习了。我觉的前缀树里面 prefix 和 label 的设计，很有想法，可以很方便的做前缀树的搜索，以前可能是忽略了这一部分。
使用 TreeNode 和 Stack 实现深度优先搜索，还是比较巧妙的，虽然也许递归的写法看上去会更简单一些。
使用临时栈来保证子节点的访问顺序和递归遍历时的访问顺序一致，也是一个比较有意思的地方。
自己用代码实现比较困难，所以还是学习了留言中的代码，其中 @qinggeouye 的 Python 代码最为漂亮，感谢。展开作者回复: 嗯，自己动手，比较自己和其他人的代码，学习更高效
- 2019-12-30学到这里，其实一直有一个疑问困惑着我。就是如何设计递归实现。递归设计一直是让我感到头痛的问题，这么些年来，我是能避免用递归就不用递归，因为，对我而言，递归算法实在是过于抽象，其中的递推过程很容易把人给绕晕。我个人对递归所秉持的态度就是敬而远之。我知道这样不利于我编程，但是没办法，设计实现递归的过程于我而言实在是太痛苦，太烧脑了。老师能不能单独开一个专题来详细地讲一讲递归啊，拜谢!!!
作者回复: 你可以把递归和回溯的过程想象成拆礼物盒。第一层递归就是最外层的大盒子，第二层递归就是里面的中等盒子，第三层就是最里面的小盒子，第四层就是你要的礼物，看完礼物后，再遵照小盒子、中盒子、大盒子的顺序还原，就是回溯了。当然，在编程的时候，我们可能需要在拆每一层的时候进行一定的动作，完成期望的逻辑。
2019-12-14首先一般的图的存储结构和树的存储结构不一样，因此，搜索算法也会不一定，其次，在一般的图中深度优先搜索时，可能会碰到回路，也就是某些节点会重复搜索，因此，搜索时要注意标记已经搜索过的节点。作者回复: 是的👍
2019-12-12字典树查找Java
public class Lesson12_1 {
/**
* @Description: 前缀树的结点
*/
class TreeNode {
public char label;
public HashMap<Character, TreeNode> sons = null;
public String prefix = null;
public String explanation = null;
// 初始化结点
public TreeNode(char l, String pre, String exp) {
label = l;
prefix = pre;
explanation = exp;
sons = new HashMap<>();
}
private TreeNode build(String str, String exp, String pre, TreeNode root) {
if ("".equals(str)) {
this.explanation = exp;
return root;
}
// 处理当前字符串的第一个字母
char c = str.toCharArray()[0];
TreeNode found = null;
// 如果字母结点已经存在于当前父结点之下，找出它。否则就新生成一个
if (this.sons.containsKey(c)) {
found = this.sons.get(c);
} else {
TreeNode son = new TreeNode(c, pre, "");
this.sons.put(c, son);
found = son;
}
return found.build(str.substring(1), exp, pre + str.substring(0, 1), root);
}
public TreeNode build(String str, String exp) {
return this.build(str, exp, "", this);
}
public String search(String str) {
if ("".equals(str)) {
return null;
}
TreeNode found = this;
char[] chars = str.toCharArray();
for (char c : chars) {
if (!found.sons.containsKey(c)) {
return null;
} else {
found = found.sons.get(c);
}
}
return found.explanation;
}
}
@Test
public void test() {
TreeNode treeNode = new TreeNode((char) 0, "", "");
treeNode.build("hello", "你好").build("helloworld", "你好世界");
System.out.println(treeNode.search("hello"));
}
}展开
2019-12-05图的深度优先搜索需要标记访问过的节点
2019-12-04说到这里，你可能会好奇，为什么只有结点的定义，而没有边的定义呢？实际上，这里的有向边表达的是父子结点之间的关系，我把这种关系用 sons 变量来存储父结点。
老师，这里是不是说错了，应该是 sons 变量来存储子结点。作者回复: 对
2019-11-16上一节迭代法会在一个结点判断选择一个分支继续下去，从这一节的栈的方法，看起来会遍历一些无用的分支，整体上看针对查找某个单词，迭代法性能会更高吗？作者回复: 递归或者栈主要是用于遍历，对于单个词的查找没有必要
2019-11-05判断当前节点是否被访问过。- 2019-10-22private static TreeNode headNode = new TreeNode('~',"im head node",null);
public static void buildPrefixTree(String word){
if(StringUtils.isEmpty(word)) {
return;
}
TreeNode findNode = headNode;
String prefix = "";
String explanation = null;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
Map<Character, TreeNode> sons = findNode.sons;
if(sons.containsKey(c)){
findNode = sons.get(c);
}else{
if(i == word.length()-1){
explanation = prefix + c;
}
TreeNode sonNode = new TreeNode(c,explanation,prefix);
sons.put(c,sonNode);
findNode = sonNode;
}
prefix += c;
}
}
public static TreeNode findWrod(String word){
if(StringUtils.isEmpty(word)) {
return null;
}
TreeNode findNode = headNode;
for(int i=0;i<word.length();i++){
char c = word.charAt(i);
Map<Character, TreeNode> sons = findNode.sons;
if( sons.size()!=0 && sons.containsKey(c)){
findNode = sons.get(c);
}else{
return null;
}
}
if(StringUtils.isEmpty(findNode.explanation)){
return null;
}
return findNode;
}
/**
* 使用栈便利所有的单词
*/
public static void dfsByStack(){
Stack<TreeNode> stack = new Stack<>();
stack.push(headNode);
while(stack.size()>0){
TreeNode node = stack.pop();
if(!StringUtils.isEmpty(node.explanation)){
System.out.println(node.explanation);
}
Map<Character, TreeNode> sons = node.sons;
sons.forEach((sonKey,sonValue)->{
stack.push(sonValue);
});
}
}展开 
2019-07-28老师这章代码有相应的github地址吗，想看看递归实现作者回复: 暂时没有，以后有机会我整理一下