24小时热门版块排行榜

返回列表

当前主题已经存档。

zsglly

木虫 (著名写手)

应助: 0 (幼儿园)
贵宾: 0.15
金币: 2268.7
帖子: 1035
在线: 4.1小时
虫号: 83160
注册: 2005-07-28
性别: GG
专业: 传热传质学

[交流] [原创]已知先序中序序列确定二叉树的算法

前天看二叉树的时候写了个知先序中序序列确定二叉树的算法，现在贴出来供大家参考。：）

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

[ Last edited by 幻影无痕 on 2006-11-25 at 07:33 ]

回复此楼

» 猜你喜欢

做人要厚道啊！厚道啊！

1楼 2005-12-13 19:25:12

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 zsglly 的主题更新

返回列表