思路就是“栈”，我不知道还有第二种思路，知道的同学可以交流
深度遍历：
( top_node )表示当前的根节点（即栈顶），( poped_node )记录最近出栈的节点 （最近出栈的节点一定是栈顶的子节点，因为入栈节点是栈顶的子节点，所以出栈节点，一定是栈顶的子节点。本人认为这是关键，没有这一点，就不能证明算法是正确的）
算法：
如果栈顶存在，则根据 栈顶 和 最近弹出的子节点，决定下一步要做什么。每一步维护 栈顶 和 最近弹出的子节点。
void dfs(root)
if (root == NULL) return // 边界情况尽早处理
stack = new Stack()
stack.push(root)
poped_node = NULL
while (not stack.empty()) // 栈中存在根节点
top_node = stack.top() // top() 只取值，不出栈
if (poped_node == NULL) { // 子节点未出栈
if ( top_node有在左子树 ) 左子树入栈
else if ( top_node有右子树 ) 右子树入栈
else {
stack.pop()
poped_node = top_node
}
} else { // 子节点出栈
if (poped_node == top_node.left_node) {
if ( top_node有右子树 ) 右子树入栈
else {
stack.pop()
poped_node = top_node
}
}
else if ( poped_node == top_node.right_node ) {
stack.pop()
poped_node = top_node
}
else {
raise Exception("出栈节点非栈顶的子节点，请检查算法逻辑")
}
}
}
先序，中序，后序，本质都是深度优先遍历，只需要在上面代码中插入打印语句；
先序遍历：左子树入栈前，打印出根节点；简单说，就是入栈时，同时打印
中序遍历：左子树出站后，打印出根节点；简单说，就是栈顶没有左子树，或者左子树出站后，打印栈顶
后序遍历：右子树出栈后，打印根节点；简单说，就是栈顶出栈时，同时打印
网友评论