|
原来在“已知先序中序序列求二叉树算法”( http://blogger.org.cn/blog/more.asp?name=binaryluo&id=11409)中的算法"生成左右子树时（第二个for循环）外层循环为n-1次，其中定位pre[ i ]时最坏比较n次，所以基本操作次数是n+n*(n-1)，时间复杂度为O(n方)"，考虑到在order中定位pre[ i ]的时候可以先将中序的序列进行一次索引排序，即：索引排序就是先为数列建立一个索引表，然后在索引表上进行排序。举个例子：原中序数组InOrder[n]={f,e,a,g,d,c,b,h}那么先建立一个索引（为了清楚起见，我把它所对应的InOrder值也写在旁边）：Idx[n]={<0,f>,<1,e>,<2,a>,<3,g>,<4,d>,<5,c>,<6,b>,<7,h>}然后以InOrder[n]为关键字，对Idx[n]进行排序。最后Idx[n]={<2,a>,<6,b>,<5,c>,<4,d>,<1,e>,<0,f>,<3,g>}（实际上Idx[n]只用保存{2,6,5,4,1,0,3}就可以了，后面的值可以随时在InOrder里查）。这样排序之后，既可以在O(log n)的时间内，通过Idx数组在InOrder中查到任意需要的节点，又不会破坏原InOrder的顺序。上述构造能在O(log n)的时间能找到所需要的子树边界，从而把时间复杂度降到O(nlogn)。改进后的算法：（红色的部分是在原算法上改进的地方）#define FALSE 0#define TRUE 1typedef 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 - indx[ 0 ].data].index; // 用索引在order中定位 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 = idx[pre[ i ++].data - idx[ 0 ].data].index; // 用索引在order中定位 visited[ p ] = TRUE; cur = cur->rchild; } else { Pop(Stack, cur); // 左右都没有子树即是叶子，则退栈 p = idx[cur.data - indx[ 0 ].data].index; // 用索引在order中定位 } }}改进后的算法生成左右子树时（第二个for循环）的时间复杂度降为O(n)，而在进行索引排序时的时间复杂度由选择的排序算法决定，在此选择了快速排序，所以时间复杂度为O(nlogn)。总的算法时间复杂度：O(nlogn) + O(n)，取O(nlogn)。但是由于要创建一个索引表，所以空间复杂度为O(n)。在此特别感谢W3China的 Logician 的提示。^_^
|
