最近复习都忙不赢上论坛了，前天看二叉树的时候写了个知先序中序序列确定二叉树的算法，现在贴出来供大家参考。：）
算法：（类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里的不分改成递归调用就行。
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → [原创]已知先序中序序列确定二叉树的算法
(订阅本版)
2005/12/10 16:57:00
新浪微博
[原创]已知先序中序序列确定二叉树的算法
顶端