计算机科学论坛--[原创]已知先序中序序列确定二叉树的算法

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

最近复习都忙不赢上论坛了，前天看二叉树的时候写了个知先序中序序列确定二叉树的算法，现在贴出来供大家参考。：）

算法：（类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里的不分改成递归调用就行。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

又想起了考研生活~~~~~~~~~~~~有意思！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

如果先对Pre[i]或Order[i]做一下索引排序的话，应该可以把LocateElem的复杂度降到O(logn)，从而把整个算法的复杂度降到O(nlogn)？

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Logician在2005-12-25 16:01:00的发言：
如果先对Pre[i]或Order[i]做一下索引排序的话，应该可以把LocateElem的复杂度降到O(logn)，从而把整个算法的复杂度降到O(nlogn)？

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

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

索引排序就是先为数列建立一个索引表，然后在索引表上进行排序。
举个例子：
原中序数组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)。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Logician在2005-12-30 13:49:00的发言：
索引排序就是先为数列建立一个索引表，然后在索引表上进行排序。
举个例子：
原中序数组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)。

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

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

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

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

不管是什么体，总该有个种可以唯一区别两个不同元素的key吧？（不然你在重构时，万一遇到两个key相同的节点，岂不是要出错了？）
只要有唯一区别两个不同元素的key，就可以比较（实在不行就按它在计算机中的数值表示的大小排就可以了），从而就可以排序。:)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

改进后的算法：
#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 = 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 的提示。^_^

[此贴子已经被作者于2006-1-1 22:49:52编辑过]


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	125.000ms