对称序周游序列是什么

问题描述

精选答案

在一颗二叉树中，要将它按对称序线索化，其做法是按对称序周游此二叉树，在周游的过程中用线索代替空指针。

周游采用非递归的方法对二叉树按顺序周游，所以设置一个栈结构，保存周游过程中需要回溯的指针。

算法中的指针，p指向正在访问的结点，pr是指向它的对称序的前驱，即上一次刚访问过的结点。

要周游对称序二叉树，首先找到对称序列中的第一个结点，然后依次找到结点的后继结点，直到其后继结点为空即可。

要找第一个结点，只要从根节点出发，沿着左指针不断往下走，直至左指针为空，到达最左下结点，这就是第一个结点。

找任意结点的对称序后继结点。一个结点的右指针如果是线索，它就指向该结点在对称序下的后继。如果不是线索，则它指向该结点右子树的根，而该结点在对称序下的后继应是此右子树的最左下结点。