|
最近复习都忙不赢上论坛了，前天看二叉树的时候写了个知先序中序序列确定二叉树的算法，现在贴出来供大家参考。：）
算法：（类C语言描述）#define FALSE 0#define 算法：（类C语言描述）#define FALSE 0#define TRUE 1typedef 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->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的位置 } }}
算法分析：假设有n个节点，在初始化visited时（第一个for循环）赋值次数等于order的长度n，生成左右子树时（第二个for循环）外层循环为n-1次，其中定位pre[ i ]时最坏比较n次，所以基本操作次数是n+n*(n-1)，时间复杂度为O(n方)。根据这个非递归要写出递归实现很简单，只需将if-else里的不分改成递归调用就行。该算法的改进算法请参考该帖：http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=25234
附代码(C版本)：2008/1/6日更新500)this.width=500'>BinTree.rar
|
