Question

一道数据结构题

请问，这个题，我画圈部分，q－>rchild＝＝p，这句话什么意思呀，谢谢





Answer 1

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

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

追问

我红笔框住的这段

意思是不是这样

要是栈不空，并且栈顶元素给q并且q的右孩子是刚刚遍历的p的话，就把出栈的栈顶元素给p，并打印p

是吗？

追答

是啊，就是遍历根啊。q的右孩子是刚刚遍历的p，那q不就是根吗？

追问

下面的那个圈2

是啥情况呀

没想明白

追答

你应该知道什么是后序遍历吧？否则，就很难说清楚了。

追问

这个肯定知道

左右根

追答

对。上面的框中的while退出的条件之一就是当前遍历的结点p不是父结点的q的右孩子，那p就是左孩子吗。左孩子遍历完了，圈②就是遍历右孩子啊！

追问

哦哦懂了

这个意思

还有一点，

这个框上面的部分，看右边的图把。你看我描述的有问题吗，就是
p是二叉树根节点指针，当p存在时，p进栈，然后找p的左，没有，就找p的右孩子

刚开始，p指向的是A吧？然后顺着找A的左的左，找到

D

这个时候p指向D

此时，D没有左右孩子，然后跳出第一个while循环

进入第二个while循环，对吗？

这个时候，已经进入的栈顶元素，是不是还是刚开始的A呀？

追答

对。

追问

那这时，不应该D是栈顶元素吗？

追答

但p此时为NULL

即D的右孩子。

追问

为啥p为null了？

不是吧，从A开始，找A的左左，找到D，D此时被p指针指着

追答

所以第一个while依然为真啊，会执行else啊，结果是p为NULL。

追问

我有点蒙，第一个while，到了D结束后，这个时候，是只是A在栈里，还是，ABD都在栈里？

追答

p指着D，还得执行第一个while啊

追问

哦哦

对，p为null

追答

p最后不是指向了D的右孩子吗？

追问

在？

追答

块不在了！

追问

这个时候应该是ABD都在栈里

吧

追答

肯定啊

接着是执行第二个while

追问

对，然后，第二个while也通了。哈哈

有点疑问，为啥会出现不是右孩子的情况？

追答

遍历弹出D，获取B(不弹出)，发现D不是B的右孩子，执行if，p指向E，接着执行第一个while，压入EF

此时栈是ABEF，F是栈顶

追问

小小问一下，怎么获取B的？是又从新从头开始了嘛

追答

算法就这个样子，其它你自己分析，好吧！记得要采纳哦！

追问

必须采纳

辛苦你了

我一会一定加很多的财富值

就是有一点点不懂，B是怎么获取的？最后一个问题了

感谢

是又从p＝T开始了吗

对。忘了多给你财富值了

随便回答一下我问的别的问题，都给你

追答

不是又从p=T开始，当栈中是ABD时，开始执行第二个while，会遍历弹出D，获取B并赋给q(B并没有弹出，因为用的是getTop)，因为D不是B的右孩子，退出第二个while，执行if，然后p指向E（E是B的右孩子），然后执行第一个while，压入E，再压入E的左孩子F，栈此时为ABEF，p又为NULL，又开始执行第二个while，弹出F，因为F不是E的右孩子，退出第二个while，执行if，p指向E的右孩子G，执行第一个while，压入G，栈此时为ABEG，然后......，就这样。

B是在第二个while中用getTop获取的啊。当栈是ABD时，弹出D后，getTop赋给q的就是B啊。

追问

明白

哎，我太笨了，你太好了，换成别人，都要骂我了

好人一生平安，我关注你了，以后希望多多指教，争取快快变得不笨

Answer 2

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

追问

那个while模块部分呢

是不是把树所有元素按后序的方式进栈？

追答

while(p)的意思写成代码就是while(p!=NULL)，就是说二叉树中仍然存在没有遍历到的节点。

追问

对，里面不是还有一个push进栈嘛

要是有，就进栈，当没有时，意思就是里面的东西都进栈了，然后出栈，是吗？

说错了，没有了，意思都进栈了，就跳出循环，是嘛

我有点糊涂。可以把while模块流程简单说明一下吗

Answer 3

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

追问

你妈死了？

在瞎回答我的问题，你们家十八代不得好死