精选留言(38)

• 
  Jsoulan

  2019-01-09

  感觉后面栈描述的过程像广度优先遍历呢

  作者回复: 栈是先进后出，还是深度优先。队列先进先出，适合广度优先

  

  23
• 
  pyhhou

  2019-03-12

  对于思考题： 1. 图中结点之间的关系是 “邻居”， 树中结点之间的关系 “父子”，如果是无向图，“邻居” 之间是互通的，但是 “父子” 默认是单向关系，一般遍历从 “父” 到 “子”，子结点中一般不保留父结点的信息 2. 图和树不一样的是，图会存在 “环” 的概念，就是回路，树中永远不可能有回路，否则就不是一棵树 可以说链表是特殊的树，树是特殊的图。 综上所述，对比树，在一般的图中做深度优先搜索的区别就是：我们需要记录我们之前访问过的结点，防止重复访问

  展开

  作者回复: 分析得很到位

  

  22
• 
  Wing·三金

  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
• 
  Ben

  2020-09-10

  第 3 步，将结点 123、879、945 和 131 压入栈中。 准确来说应该是 131, 945, 879, 123. 123是最后压栈的, 所以是最先出栈, 然后先处理123的子节点

  作者回复: 确实是，严格来说应该按照入栈的顺序来说

  

  2
• 
  罗耀龙@坐忘

  2020-04-04

  茶艺师学编程 今天老师讲完了树的深度优先搜索。它本身是图论的遍历算法之一，(另一个是广度优先搜索BFS)，俗话说，就是"一条路走到黑"。 在有向树上，深度优先搜索借助堆栈工具可以无脑遍历——树的结构主要是由上至下的"父子关系"，走到一个"叶子"了，倒回去，换个方向，再走。 而在一般的图上，这样的走法就显得没那么效率了——至少其中某些点会被重复走很多遍。因为在一般的图上，点与点的关系就不光是单向的"父子关系"，平级、来回方向的，都有。

  展开

  

  2
• 
  Paul Shan

  2019-08-23

  这里深度优先遍历的顺序和前一篇文章中的不太一样，区别在于前一篇文章中的深度遍历,当发现一个新节点的时候入栈，然后马上处理这个新节点也就是栈顶，这篇文章中是把一个节点相连的所有节点入栈，然后再处理栈顶元素，请问老师，我的理解是否准确？

  作者回复: 是的，一个只要访问最深的某条路径，一个是需要遍历所有路径

  

  2
• 
  半湖思絮

  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")); } }

  展开

  

  1
• 
  张洋

  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
• 
  qinggeouye

  2019-02-24

  # python 简单实现 class TreeNode(object): """节点""" def __init__(self, label=None, prefix=None, explanation=None, is_word=False): """:param label: 节点的名称 在前缀树里是单个字母 :param prefix: 根节点到当前节点的字母组成的前缀 :param explanation: 单词解释 :param is_word: False不是一个单词""" self.explanation = explanation self.prefix = prefix self.label = label self.is_word = is_word self.sons = dict() # 存放子节点 class Tree(object): def __init__(self): self._root = TreeNode() def add(self, word, explanation): """向 Tree 中添加一个单词 :param explanation: 单词解释 :param word: 英文单词 :return:""" cur = self._root # 从根节点开始 for c in word: # 遍历单词中的字母 if cur.sons.get(c, None) is None: if cur.prefix is None: prefix = cur.label else: prefix = cur.prefix + cur.label # print(prefix) cur.sons[c] = TreeNode(c, prefix) cur = cur.sons.get(c) # 单词字母遍历结束，添加单词解释 cur.explanation = explanation cur.is_word = True # print(cur.explanation) @property def root(self): return self._root def dfs_by_stack(root): """使用栈来实现深度优先搜索 :param root: 根节点""" stack = list() #元素TreeNode stack.append(root) #压入根节点 while len(stack) > 0: #只要栈有节点 继续 node = stack.pop() #弹出栈顶节点 if node.is_word: print(node.prefix + node.label, node.explanation) # 是一个单词，则输出 if len(node.sons) == 0: continue stack_temp = [node.sons.get(son) for son in node.sons] while len(stack_temp) > 0: stack.append(stack_temp.pop()) if __name__ == "__main__": testTree = Tree() word_dict = {'love': '爱', 'like': '喜欢', 'successful': '成功的', 'success': '成功'} for _word, _explanation in word_dict.items(): testTree.add(_word, _explanation) dfs_by_stack(testTree.root)

  展开

  

  1
• 
  Joe

  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

  展开

  作者回复: 很好的实现，代码简洁

  共 2 条评论

  1
• 
  Being

  2019-01-09

  广度优先一般用队列来做，FIFO，这样做到层级遍历；深度优先则用栈来做，FILO，这样做到按深度一条条的遍历下去。在实现上是这么区别的，我看上面有同学混淆了。

  作者回复: 总结的很好

  

  1
• 
  Leon Wong

  2022-11-29 来自广东

  利用栈这个数据结构作为辅助DFS遍历的工具确实很巧妙，节点信息都会存储到一个连续的存储空间，减少内存碎片的产生

  

  
• 
  013923

  2022-07-28

  谢谢老师！

  

  
• 
  Geek_27ca2b

  2021-01-12

  JS 实现的，就是散列表要自己实现一下。 地址： https://github.com/wss2020/Frontend-04-Template/tree/master/z.js%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E6%95%B0%E5%AD%A6%E5%9F%BA%E7%A1%80%E8%AF%BE/4%20%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/1%20%E5%89%8D%E7%BC%80%E6%A0%91

  展开

  共 1 条评论

  
• 
  l c

  2020-07-04

  不是很理解为什么用显式栈实现dfs更省空间，我的理解中他们所用的空间是一样的。假使做全遍历，都是n(n为所有节点个数)。显式栈的优势不是只在于避免堆栈溢出吗？请老师解答一下。

  作者回复: 这个取决于每种语言和编程的具体实现是否有优化，如果没有优化，可能会导致每次嵌套调用的时候，都生成变量的副本

  

  
• 
  咕咕咕

  2020-05-08

  那个用栈的应该属于bfs吧，虽说用的栈但还是一波一波往外扩的。

  作者回复: 栈一般用在dfs上，当然做适当修改也是可以做bfs，但是bfs队列就够了，所以不用了

  

  
• 
  喻茂

  2020-03-16

  // 定义往单词数中插入的单词 $wordsArr = ['yes','no','yell','nyll']; $rootNode = new TreeNode('','',0,null); // 定义一个空节点作为数的根节点 $tree = new Tree($rootNode); foreach ($wordsArr as $wordsArrOne) { $curWordLen = strlen($wordsArrOne); $curPrefix = ""; // 到目前为止的前缀 $isCompleteWord=0; // 是否为完整单词 $curTreeSonNums = count($tree->root->childArr); $curtempNode = $tree->root; for ($i=0;$i<=$curWordLen-1;$i++) { if ($i==$curWordLen-1) { // 已经是完整单词 $isCompleteWord = 1; } // 如果当前的子层有这个字母无需插入节点 $isexist = 0; foreach ($curtempNode->childArr as $curChildKey=>$childOne) { if ($childOne->label == $wordsArrOne[$i]) { $isexist = 1; // 字母已经存在 } } if ($isexist == 0) { // 没有需要插入节点 $curLetterNode = new TreeNode($wordsArrOne[$i],$curPrefix,$isCompleteWord,null); $curtempNode->childArr[] = $curLetterNode; $curtempNode = $curtempNode->childArr[count($curtempNode->childArr)-1]; } else { $curtempNode->childArr[$curChildKey]->isCompleteWord = $isCompleteWord; $curtempNode = $curtempNode->childArr[$curChildKey]; } $curPrefix .= $wordsArrOne[$i]; // 更新前缀 } } // 遍历树 $tree->preOrder($tree->root); // 查看某一单词是否在树中存在 echo " "; $tree->wordExists($tree->root,'yes'); $tree->wordExists($tree->root,'yel'); $tree->wordExists($tree->root,'ok'); $tree->wordExists($tree->root,'yess'); echo " "; $tree->dfsByStack($tree->root);

  展开

  

  
• 
  喻茂

  2020-03-16

  // 整个单词树 class Tree{ public $root; public function __construct($root=null){ $this->root = $root; } // 前序遍历 public function preOrder($node) { if (!is_null($node)) { echo $node->label.","; foreach ($node->childArr as $childNodeOne) { $this->preOrder($childNodeOne); } } } // 使用数组模拟栈打印所有单词 public function dfsByStack($node) { $stackArr = []; array_push($stackArr,$node); while ($stackArr) { $curNode = array_pop($stackArr); if ($curNode->isCompleteWord==1) { // 完整单词，直接打印 echo $curNode->prefix.$curNode->label." "; } if (!empty($curNode->childArr)) { $curChildArr = array_reverse($curNode->childArr); foreach ($curChildArr as $curChildArrOne) { array_push($stackArr,$curChildArrOne); } } } } // 查看某一单词是否在树中存在 public function wordExists($node,$word) { $isExists = 0; $wordLen = strlen($word); // 忽略根节点 从第一层节点查 $nodeArr = $node->childArr; for ($i=0;$i<$wordLen;$i++) { // 定义当前层是否有字母可以匹配 $curMatch = 0; if (empty($nodeArr)) { // 单词长度还没到就到了树的子节点查找失败 break; } foreach ($nodeArr as $nodeKey=>$nodeArrOne) { if ($nodeArrOne->label == $word[$i]) { // 匹配成功 $curMatch = 1; break; } } if ($curMatch == 1) { // 当前层查询成功 $node = $nodeArr[$nodeKey]; $nodeArr = $node->childArr; } else { break; // 匹配失败 } } if (($i == $wordLen) && ($node->isCompleteWord == 1)) { // 匹配到了最后一个字母这时要查看当前节点是不是完整单词 $isExists = 1; } if ($isExists == 1) { echo "查找成功 "; } else { echo "查找失败 "; } } }

  展开

  

  
• 
  喻茂

  2020-03-16

  php示例 // 每个节点 class TreeNode{ public $label; // 当前节点的名称，当前字母 public $prefix=""; // 从树的根到当前结点这条通路上，全部字母所组成的前缀 public $isCompleteWord=0; // 是否为完整单词 public $childArr=[]; // 子节点集合 public function __construct($label='',$prefix='',$isCompleteWord=0,$child=null){ $this->label = $label; $this->prefix = $prefix; if ($this->isCompleteWord==0) { $this->isCompleteWord = $isCompleteWord; } if ($child) { $this->childArr[] = $child; } } }

  展开

  

  
• 
  吴宇晨

  2020-03-10

  图的dfs因为不一定全部联通要记一下访问过的节点，然后可能有环要判断一下吧

  作者回复: 对，对于可能的环路要判断是否已经访问过

  

  