TUhjnbcbe - 2024/9/8 19:20:00
先序遍历(根左右)，u在w的前面后序遍历(左右根)，u在w的后面证明：u是w的祖先节点证明如下：反证法，假设u不是w的祖先节点，记二叉树为BT，二叉树的根节点为r，即u不在r到w的路径上。可分为以下两种情况：①u是w的字树上的节点记w的左子树wl（wleft），右子树wr（wright），u可能在wl上，或在wr上，先序遍历，w在wl之前，wl在wr之前，即w肯定在u之前，与题意不符。②u是w子树节点以外的其他节点记r到w的路径为r，r1，r2……rk，w.即u是r，r1，r2……rk其中某个节点的子树节点。取r，r1，r2……rk其中某个节点rx，记rx的左子树rxl，右子树rxr，rxl=w，rxr=u，先序遍历，u在w后面，与题意矛盾rxl=u，rxr=w，后序遍历，u在w前面，与题意矛盾综上，u只能是r，r1，r2……rk其中的某一个节点，即u是w的祖先节点。问题得证。