请教：如何查找完全二叉树最后一层的最右边的结点

aresyt

如题。
对基于数组实现完全二叉树容易做到，只需返回数组最后一项。
但是对基于指针实现的完全二叉树，应该使用什么算法呢？
多谢！

xiaobaixi

右子树的右子树的右子树

直到最后一层

这样不是行了吗??

aresyt

不对啊，完全二叉树不一定是满二叉树啊。
在最后一层，所有结点从左至右依次无缝排列。

冷夜星光

确实，用GoFastRight();函数寻找有点麻烦！

mars1004

广度优先搜索。

zphoenix

:) 用一个链表，做按层的搜索。
第一层，把根扔进链表。
第二层，找到根的L、R子节点，替换链表中的根。
第三层，找到根的L、R子节点的子节点，替换到链表中。
如此递归，如果某个节点没有子节点，就删掉了，否则就被自己的子节点替换。保持子节点从左到右的顺序。
这样到最后一层，最后一个子节点就是你要找的了。

当然实现的时候要把一层遍历完，才能删除上一层的。 :)

aresyt

哦，我明白了。
就是说采用基于队列的广度优先遍历，每次从队列弹出已访问的结点入栈，遍历结束后在栈顶的数据项即为所求。
这种算法的复杂度的确比基于数组的复杂度大的多啊。

菜鸟级高手

按层遍历的最后一个结点

ch1074856

从头开始不断找右子树，没有右子树就找左子树。一直到叶子节点。

ch1074856

上面ch1074856 的方法是错的，请无视。