在网上一个论坛搜到的，原出处：http://60.28.222.210/dispbbs.asp?BoardID=60&id=25234&replyID=25234&star=1&skin=0
我感觉这个算法在建立右子树根的判断上是有点问题的：当前已建立的根结点（visited[p]）在中序序列中的后继元素（visited[p+1]）就是该根结点的右子树根吗？中序序列中的某点的的后继元素应该是该结点的右子树的最左孩子才对啊？
刚学数据结构不久，请各位前辈指教。愚钝之处还请包涵，谢谢。
#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的位置
}
}
}
思路捋顺了，谢谢回帖的前辈们。
（智商不太高偶尔会犯傻钻S胡同，还请见谅:)
[此贴子已经被作者于2007-8-26 16:48:37编辑过]
