在一个用数组表示的完全二叉树中,如果根结点下标为1,那么下标为17和19这两个结点的最近公共祖先结点在哪里(数组下标)? (注:两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点) 写出计算过程
时间: 2024-01-24 13:19:27 浏览: 356
寻找二叉树两结点最近的祖先
4星 · 用户满意度95%
在一个用数组表示的完全二叉树中,下标为 $i$ 的结点的父节点下标为 $\lfloor \frac{i}{2} \rfloor$,左子节点下标为 $2i$,右子节点下标为 $2i+1$。
首先,根据给定的下标,可以求出它们的深度,下标为 $17$ 的结点深度为 $4$,下标为 $19$ 的结点深度为 $3$。
接下来,从深度较大的结点开始,不断向上找它们的公共祖先结点,直到找到它们的最近公共祖先结点为止。具体过程如下:
- 下标为 $17$ 的结点的祖先结点为 $8$(深度为 $3$)。
- 下标为 $19$ 的结点的祖先结点为 $9$(深度为 $3$)。
- 下标为 $8$ 和 $9$ 的结点的祖先结点为 $4$(深度为 $2$)。
- 下标为 $4$ 的结点的祖先结点为 $2$(深度为 $1$)。
因此,下标为 $17$ 和 $19$ 的结点的最近公共祖先结点下标为 $2$。
阅读全文