算法：（类C语言描述）
#define   FALSE    0
#define   TRUE     1
typedef int Status;

Status createTree(BiTree &T, BiTNode pre[], BiTNode order[]){
          // 已知先序序列pre和中序序列order，构建一个二叉树T的非递归实现。
          // 其中涉及到的数据结构请参看清华大学《数据结构》(C语言版)

          InitStack(Stack);        //初始化栈
          for (i = 0; i < order.length; i ++) visited[ i ] = FALSE;
                                            // 初始化visited，visited用于标记order
                                            // 中的元素是否已经被访问过
          T = (BiTree *) malloc (sizeof(BiTree));
          T.data = pre[0]; T -> lchild = NULL; T -> rchild = NULL;
                                           // 生成根节点，先序pre中的第一个元素肯定是树根，
                                           // 左右孩子初始化为NULL。
          p = LocateElem(order, pre[0]);   // 在order中找到根节点所在的位置
          visited[ p ] = TRUE;                         // 标识order中的根元素已被访问过
          cur = root;                                    // cur表示当前构建的节点

          for (i = 1; i < pre.length; ) {
                p = LocateElem(order, pre[ i ]); // 定位pre[ i ]的位置
                if (p > 0 && !visited[p - 1]) {
                        // 在order中pre[ i ]的左边有元素并且未被访问过,说明有左子树存在，
                        // 生成左子树
                        cur->lchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->lchild.data = pre[i ++];
                                        // 将当前pre中的元素赋给lchild后指向下一个元素
                        cur->lchild->lchild = NULL; cur->rchild->rchild= NULL;
                        visited[ p ] = TRUE;
                        Push(Stack, cur);        // 当前节点进栈
                        cur = cur->lchild;        // 当前节点指向左孩子
                }
                else if (p < order.length - 1 && !visited[p + 1]) {
                        // 生成右子树
                        cur->lchild = NULL;   // 没有左孩子
                        cur->rchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->rchild.data = pre[i ++];
                        cur->rchild.lchild = NULL; cur->rchlid.rchild = NULL;
                        visited[ p ] = TRUE;
                        cur = cur->rchild;
                }
                else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                }
          }
}

算法分析：
假设有n个节点，在初始化visited时（第一个for循环）赋值次数等于order的长度n，生成左右子树时（第二个for循环）外层循环为n-1次，其中定位pre[ i ]时最坏比较n次，所以基本操作次数是n+n*(n-1)，时间复杂度为O(n方)。
根据这个非递归要写出递归实现很简单，只需将if-else里的不分改成递归调用就行。

您所说的索引排序是怎么回事？能否具体点？

谢谢：）
我改进下再贴出来。

刚才改的时候突然遇到一个疑问，在您上面的假设里节点的数据元素的类型是字符，如果他的元素类型不是字符，是一些结构体是不是就不行了啊？？

typedef struct {
       BiTNode node;  // 原来中序中的数据元素
       int index;           // 新加的索引字段
}IndexNode, IndexList;

Status IndexSort(BiTNode order[], IndexList idx){
       for (i = 0; i < order.length; i ++){  // 构建一个索引表
             idx[ i ].node = order[ i ];
             idx[ i ].index = i;
       }

       QSort(idx, 0, L.length);  // 快速排序，需在清华数据结构274-275页算法的基础上稍加改变

       return OK;
}
Status createTree(BiTree &T, BiTNode pre[], BiTNode order[]){
          // 已知先序序列pre和中序序列order，构建一个二叉树T的非递归实现。
          // 其中涉及到的数据结构请参看清华大学《数据结构》(C语言版)

          IndexList *idx;            
          IndexSort(order, idx);  // 对order索引排序
          InitStack(Stack);        //初始化栈
          for (i = 0; i < order.length; i ++) visited[ i ] = FALSE;
                                            // 初始化visited，visited用于标记order
                                            // 中的元素是否已经被访问过
          T = (BiTree *) malloc (sizeof(BiTree));
          T.data = pre[0]; T -> lchild = NULL; T -> rchild = NULL;
                                           // 生成根节点，先序pre中的第一个元素肯定是树根，
                                           // 左右孩子初始化为NULL。
          p = LocateElem(order, pre[0]);   // 在order中找到根节点所在的位置
          visited[ p ] = TRUE;                         // 标识order中的根元素已被访问过
          cur = root;                                    // cur表示当前构建的节点

          for (i = 1; i < pre.length; ) {
                p = idx[pre[ i ].node.data - order[ 0 ].node.data].index; // 用索引在order中定位
                if (p > 0 && !visited[p - 1]) {
                        // 在order中pre[ i ]的左边有元素并且未被访问过,说明有左子树存在，
                        // 生成左子树
                        cur->lchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->lchild.data = pre[i ++];
                                        // 将当前pre中的元素赋给lchild后指向下一个元素
                        cur->lchild->lchild = NULL; cur->rchild->rchild= NULL;
                        visited[ p ] = TRUE;
                        Push(Stack, cur);        // 当前节点进栈
                        cur = cur->lchild;        // 当前节点指向左孩子
                }
                else if (p < order.length - 1 && !visited[p + 1]) {
                        // 生成右子树
                        cur->lchild = NULL;   // 没有左孩子
                        cur->rchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->rchild.data = pre[i ++];
                        cur->rchild.lchild = NULL; cur->rchlid.rchild = NULL;
                        visited[ p ] = TRUE;
                        cur = cur->rchild;
                }
                else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                }
          }
}

改进后的算法生成左右子树时（第二个for循环）的时间复杂度降为O(n)，而在进行索引排序时的时间复杂度由选择的排序算法决定，在此选择了快速排序，所以时间复杂度为O(nlogn)。总的算法时间复杂度：O(nlogn) + O(n)，取O(nlogn)。但是由于要创建一个索引表，所以空间复杂度为O(n)。在此特别感谢 Logician 的提示。^_^

算法1：（类C语言描述）
#define   FALSE    0
#define   TRUE     1
typedef int Status;

Status createTree(BiTree &T, BiTNode pre[], BiTNode order[]){
          // 已知先序序列pre和中序序列order，构建一个二叉树T的非递归实现。
          // 其中涉及到的数据结构请参看清华大学《数据结构》(C语言版)

          InitStack(Stack);        //初始化栈
          for (i = 0; i < order.length; i ++) visited[ i ] = FALSE;
                                            // 初始化visited，visited用于标记order
                                            // 中的元素是否已经被访问过
          T = (BiTree *) malloc (sizeof(BiTree));
          T.data = pre[0]; T -> lchild = NULL; T -> rchild = NULL;
                                           // 生成根节点，先序pre中的第一个元素肯定是树根，
                                           // 左右孩子初始化为NULL。
          p = LocateElem(order, pre[0].data);   // 在order中找到根节点所在的位置
          visited[ p ] = TRUE;                         // 标识order中的根元素已被访问过
          cur = T;                                    // cur表示当前构建的节点

          for (i = 1; i < pre.length; ) {
               
                if (p > 0 && !visited[p - 1]) {
                        // 在order中pre[ i ]的左边有元素并且未被访问过,说明有左子树存在，
                        // 生成左子树
                        cur->lchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->lchild.data = pre[ i ];
                                        // 将当前pre中的元素赋给lchild后指向下一个元素
                        cur->lchild->lchild = NULL; cur->rchild->rchild= NULL;
                        p = LocateElem(order, pre[ i ++].data); // 定位pre[ i ]的位置
                        visited[ p ] = TRUE;
                        Push(Stack, cur);        // 当前节点进栈
                        cur = cur->lchild;        // 当前节点指向左孩子
                }
                else if (p < order.length && !visited[p + 1]) {
                        // 生成右子树
                        cur->lchild = NULL;   // 没有左孩子
                        cur->rchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->rchild.data = pre[ i ];
                        cur->rchild.lchild = NULL; cur->rchlid.rchild = NULL;
                        p = LocateElem(order, pre[ i ++].data); // 定位pre[ i ]的位置
                        visited[ p ] = TRUE;
                        cur = cur->rchild;
                }
                else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                        p = LocateElem(order, cur.data); // 重新定位p的位置
                }
          }
}

算法2：（红色的部分是在原算法上改进的地方）
#define   FALSE    0
#define   TRUE     1
typedef int Status;

typedef struct {
       BiTNode node;  // 原来中序中的节点
       int index;           // 新加的索引字段
}IndexNode, IndexList;

Status IndexSort(BiTNode order[], IndexList idx){
       for (i = 0; i < order.length; i ++){  // 构建一个索引表
             idx[ i ].node = order[ i ];
             idx[ i ].index = i;
       }

       QSort(idx, 0, L.length);  // 快速排序，需在清华数据结构274-275页算法的基础上稍加改变

       return OK;
}

Status createTree(BiTree &T, BiTNode pre[], BiTNode order[]){
          // 已知先序序列pre和中序序列order，构建一个二叉树T的非递归实现。
          // 其中涉及到的数据结构请参看清华大学《数据结构》(C语言版)
            
          IndexList *idx;            
          IndexSort(order, idx);  // 对order索引排序
          InitStack(Stack);        //初始化栈
          for (i = 0; i < order.length; i ++) visited[ i ] = FALSE;
                                            // 初始化visited，visited用于标记order
                                            // 中的元素是否已经被访问过
          T = (BiTree *) malloc (sizeof(BiTree));
          T.data = pre[0]; T -> lchild = NULL; T -> rchild = NULL;
                                           // 生成根节点，先序pre中的第一个元素肯定是树根，
                                           // 左右孩子初始化为NULL。
          p = idx[ pre[ 0 ].data - idx[ 0 ].data].index   // 在order中找到根节点所在的位置
          visited[ p ] = TRUE;                         // 标识order中的根元素已被访问过
          cur = T;                                    // cur表示当前构建的节点

          for (i = 1; i < pre.length; ) {
               
                if (p > 0 && !visited[p - 1]) {
                        // 在order中pre[ i ]的左边有元素并且未被访问过,说明有左子树存在，
                        // 生成左子树
                        cur->lchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->lchild.data = pre[ i ];
                                        // 将当前pre中的元素赋给lchild后指向下一个元素
                        cur->lchild->lchild = NULL; cur->rchild->rchild= NULL;
                        p = idx[pre[ i  ++].data - idx[ 0 ].data].index; // 用索引在order中定位
                        visited[ p ] = TRUE;
                        Push(Stack, cur);        // 当前节点进栈
                        cur = cur->lchild;        // 当前节点指向左孩子
                }
                else if (p < order.length && !visited[p + 1]) {
                        // 生成右子树
                        cur->lchild = NULL;   // 没有左孩子
                        cur->rchild = (BiTNode *) malloc (sizeof(BiTNode));
                        cur->rchild.data = pre[ i ];
                        cur->rchild.lchild = NULL; cur->rchlid.rchild = NULL;
                        p = idx[pre[ i  ++].data - idx[ 0 ].data].index; // 用索引在order中定位
                        visited[ p ] = TRUE;
                        cur = cur->rchild;
                }
                else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                        p = idx[cur.data - idx[ 0 ].data].index; // 用索引在order中定位
                }
          }
}

实在不好意思了，原来写完以后一高兴就忘记检查了，今天才发现错误。
敬请原谅。

这个用类C语言描述的算法已经很接近程序了，只需要加上变量声明等一些语法规则就可以了啊。

你说的加标签有什么意义呢？如果是为了排序的话最好就是O(nlgn)了。

这个hash函数不好构造……

o?!

else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                        p = LocateElem(order, cur.data); // 重新定位p的位置
}

首先要说明的是栈只是用来临时保存左子树。

else {
                         Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                         p = LocateElem(order, cur.data); // 重新定位p的位置
}
的意思是当当前结点的左子树生成完（if语句），且右子树也生成完（else if语句）后，如果栈不空，说明还有其它节点的子树未构造，那么就接着处理这些节点，所以要退栈。

第一次写的有个错误，在第二页上我已更正，你看的是更正后的吗？