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

贴子主题： [原创]已知先序中序序列确定二叉树的算法

本主题类别:

上述的算法在构建时候有问题，现已更正如下：

算法1：（类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].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的位置
                }
          }
}

算法2：（红色的部分是在原算法上改进的地方）
#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 = 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 - idx[ 0 ].data].index; // 用索引在order中定位
                        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 = idx[pre[ i  ++].data - idx[ 0 ].data].index; // 用索引在order中定位
                        visited[ p ] = TRUE;
                        cur = cur->rchild;
                }
                else {
                        Pop(Stack, cur);        // 左右都没有子树即是叶子，则退栈
                        p = idx[cur.data - idx[ 0 ].data].index; // 用索引在order中定位
                }
          }
}

实在不好意思了，原来写完以后一高兴就忘记检查了，今天才发现错误。
敬请原谅。

[此贴子已经被作者于2006-1-6 12:26:14编辑过]


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