一道数据结构题

2025-02-26 01:30:49

推荐回答（3个）

回答1：

整个代码是用后序非递归算法来遍历二叉树，即按左右根的顺序来遍历二叉树。

p是刚刚遍历了的结点，q是p的父结点。画圈部分的意思是：
如果刚刚遍历的是右孩子，则遍历父结点q。
否则，执行②，先遍历父结点q的右孩子p。

回答2：

p表示当前遍历的父节点
q表示从栈S中取出的栈顶的节点
q->rchild == p
意思就是看栈顶的节点q的右孩子和当前遍历的父节点p是否相等

回答3：

表头插入时间复杂度O(1），因为不需用移动元素，常数时间完成操作；表尾插入复杂度O(n)，因为每次操作都需用把指针先移动到表尾，需用n次移动。顺序存储的线性表表头插入复杂度O(n)，因为每次操作前，都需用把n个元素从尾部开始向后移动一位，需用n次移动；在表尾插入元素的时间复杂度为O(1)，因为元素可以直接完成插入，不用向后移动元素，并且元素定位（寻址）时间不用考虑。