Question

有谁能答：已知一棵完全二叉树各节点的编号为0到n，如何得出其第一个非叶子节点的编号

答案我知道，可怎么推到出来的啊，高手指点。。。
我是指倒数第一个非叶子节点哈，呵呵

Answer 1

在完全二叉树中， 第一个非叶子结点 其实就是 最后一个叶子结点的父节点。
假定父节点为i；则 其左叶子为2i+1 ， 右叶子为2i+2；
则当叶子节点为n-1时，就有了上面这位兄弟的n/2 -1 的结论

Answer 2

最后一个叶子节点的索引值是n-1，它的父节点索引值是[(n-1)-1]/2 = n/2 -1

Answer 3

题目描述不清：第一个指的是哪一个？

追问

倒数第一个

追答

按照什么顺序倒数第一个，最右边的一个？另外，你是按照什么顺序标号的？先根？后根？

追问

好吧，是我描述不全，我是指一棵按照层序编号为0到n的完全二叉树（从根节点开始），请问这颗树倒数第一个非叶子节点的编号用n来表示是多少，我知道答案，可不知道是怎么推出来的，望前辈指点

追答

二叉树的节点数目是2^N - 1
倒数第二层是2^(N-1)-1，最后一个的编号是2^(N-1)-1-1 （如果从0开始）

追问

可这是满二叉树，我说的是完全二叉树，您知道堆排序不，其实我的问题来源于堆排序建立大根堆的过程中。。。

追答

Sorry.
如果是数学公式，应该是用log(N,2)+1算出层次，然后用上面公式算出倒数第二层的最后一个。

Answer 4

第一个非叶子节点???你这让人怎么理解
第一个非叶子节点不就是根节点？？？？

追问

倒数第一个

追答

你用中序遍历得到的倒数第二个节点就是你要的结果
数据结构上有中序遍历算法 你输入序号 出来的结果中的倒数第二个 嘿嘿

追问

我是指一棵按照层序编号为0到n的完全二叉树（从根节点开始），请问这颗树倒数第一个非叶子节点的编号用n来表示是多少，我知道答案，可不知道是怎么推出来的，望前辈指点

追答

其实我上面已经说的很清楚了：
数据结构书上有一个实现了的中序遍历函数
创建一颗二叉树
你把BTreeeNode->data=0....n
用中序遍历函数遍历出来 倒数第二个值就是你要的值

追问

不对吧，算了。。。

追答

对的 你仔细想一想我上面的
这样设计：
BTreeNode->data存放的是每个节点的编号
用中序遍历时候 输出每个节点 顺带输出节点的编号 倒数第二个不就是要的结果？？
好好想一想

追问

是你没弄懂我的题目。。。不过还是多谢参与