| 查看: 250 | 回复: 0 | |||
| 当前主题已经存档。 | |||
zsglly木虫 (著名写手)
|
[交流]
[原创]已知先序中序序列确定二叉树的算法
|
||
|
前天看二叉树的时候写了个知先序中序序列确定二叉树的算法，现在贴出来供大家参考。：） 算法：（类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 ] |
回复此楼» 猜你喜欢
29号明天会评吗
已经有4人回复
-
国社科又开始会评了，不知道这次命运如何
已经有10人回复
-
梦想
已经有4人回复
-
中青基了要发朋友圈吗？
已经有6人回复
-
基金不中，共勉
已经有12人回复
-
能否申诉？
已经有7人回复
-
有多少人是今天查系统知道结果的？
已经有19人回复
-
面上意见出来了
已经有19人回复
-
为什么到现在没收到通知？
已经有5人回复
-
有没有仍没收到信息的
已经有8人回复
投票:
10