给定一个二叉树的前序遍历序列为 "AB#D##C##",其中 '#' 表示空节点,若使用栈模拟递归方式构建此二叉树,当遍历到节点 'D' 时,栈中自栈底到栈顶的元素依次是哪些节点?(假设栈初始为空,且入栈顺序按前序遍历顺序)

答案解析

核心考点:二叉树的前序遍历、栈的应用、递归的模拟。解题思路分析:前序遍历顺序为 根 -> 左子树 -> 右子树。用栈模拟递归,每访问一个非空节点,将其入栈;访问空节点时,弹出栈顶元素(回溯),根据前序遍历构建二叉树的过程,我们可以模拟栈的变化。详细分析:1. 访问 A,A入栈,栈:|A|;2. 访问 B,B入栈,栈:|A|B|;3. 访问 #,B弹出,栈:|A|;4. 访问 D,D入栈,栈:|A|D|;5. 访问 #,D弹出,栈:|A|;6. 访问 #,A弹出,栈:| |;7. 访问 C,C入栈,栈:|C|;8. 访问 #,C弹出,栈:| |;9. 访问 #。所以当遍历到节点'D'时,栈中元素为A,之后D入栈,故当前栈中元素为A、D。A选项:只考虑了A和B。B选项:考虑了A,B,D,不符合此时栈的状态。C选项:只考虑了A,不符合此时栈的状态。D选项:只考虑了B,不符合此时栈的状态。易错点提醒:注意模拟递归时入栈和出栈的时机,要根据前序遍历的顺序进行,并且每次访问到#时需要弹栈。正确答案的关键依据:根据栈模拟递归,当遍历到D时,栈中元素为A和D。根据题意,此时是D刚入栈,因此栈顶为D,栈底为A。每个选项分析:A选项错误,栈中为A、D;B选项错误,D刚入栈,之前栈内为A;C选项错误,栈中为A、D;D选项错误,栈中为A、D。所以应选B。
正确答案:A
随机推荐
开始刷题