// pre -- 先序
// in  -- 中序
void Post(List *pre, List *in)
{
  Element  e;
  POSITION pos;
  List     *lin, *rin;    
  List     *lpre,*rpre;
  e = GetFront(pre);  // 取得先序表中的第一个元素（必定为二叉树的根节点）
  pos = FindElement(in, e); // 根节点必定把中序分成左右两部分，
                            //左半部为左子树序列，右半部为右子树序列
  lin = GetLeft(in, pos);     // 以pos为界取得中序的左半部分
  rin = GetRight(in, pos);    // 取得右半部分
  lpre = FindLeft(pre, lin);  // 从先序中找到左子树部分
  rpre = FindRight(pre，rin); // 从先序中找到右子树部分
  Post(lpre, lin);            // 访问左子树
  Post(rpre, rin);            // 访问右子树
  Vist(e);                    // 访问根
}

评论