搜题
  1. 问题易首页
  2. 大学
导航：题目详情 | 答案解析 | 相关问题 | 最新问题

设计一个程序 根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树。

大学 序列,指针,根据 已帮助 人

设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树。

热搜：二叉排序树的查找效率与二叉树的树形有关

答案解析

难度★★☆ 搜索

  • (1)数据结构
       采用二叉树的链接表示。
       (2)思路
       二叉树的先根序列和对称序序列，用两个数组preorder和inorder存放。先根序列的第一个元素的值preorder[0]应为二叉树的根上的元素值，在另一个数组中查到此值，设为inorder[k]。此时，数组preorder中从preorder[1]到preorder[k]的序列(长度为k)和数组inorder中从inorder[0]到inorder[k-1](长度为k)的序列，恰好分别是根结点左子树(k个结点)的先根序列和对称序序列。数组preorder中从preorder[k+1]到preorder[n-1]的序列(长度为n-k-1)和数组inorder中从inorder[k+1]到inorder[n-1](长度为n-k-1)的序列，恰好分别是根结点左子树(n-k-1个结点)的先根序列和对称序序列。
       根据上述分析，算法先创建根结点，再递归调用自己两次来分别创建左右子树。
       (3)算法
       int create_BTree(PBinTree pbtree,DataType*preorder,DataType*inordeL int n){
       /*根据先根序列preorder和对称序序列inorder(长度为n)创建二叉树pbtree。对于正确的先根序列和对称序序列,算法返回TRUE,否则返回FALSE*/
       int i,k;
       int tag1,tag2;
       if(n==0){
           *pbtree=NULL:
           return TRUE;
       }
       for(i=0;i＜n;i++)
           if(inorder[i]==preorder[0])
               break;
       if(i==n){
           *pbtree=NULL;
           return FALSE;
           /*输入的先根序31j或对称序序列有误,创建失败*/
       }
       k=i;
       *pbtree=(PBinTreeNode)malloc(sizeof(struct BinTreeNode));
       (*pbtree)-＞info=preorder[0];
           tag1=create_BTree(&(*pbtree)-＞llink,preorder+1,inordeg k);
                                                                    /*递归调用本算法创建左子树*/
           tag2=create_BTree(&(*pbtree)-＞dink,preorder+k+1,inorder+k+1,n-k-1);    /*递归调用本算法创建右子树*/
           if(tag1==TRUE&&tag2==TRUE) return TRUE;
           return FALSE;    /*二叉树创建成功当且仅当其左右子树都创建成功*/
       }
       (4)代价分析
       最坏的情况是，每个非叶结点只有左子树。这时两个数组之间需要比较n+(n-1)+…+1=O(n2)次。所以，该算法的时间代价为O(n2)。空间代价主要包括：存放二叉树的空间O(n)和用于递归调用的栈空间(不超过O(n))。