12 | 树的深度优先搜索（下）：如何才能高效率地查字典？

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

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

用 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 函数直接逆序。

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

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

老师遍历出所有的单词 是不是用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); }); } }

老师讲解的树有多个分支，这里用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

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

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

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