Pat 1020（patients）

Pat 1020（patients）

1.题意 （1）给出一棵二叉树的中序序列，以及后序序列，求出该树的层次遍历顺序序列。 2.分析 对于这种题目，我们自己可以很快给出答案，但是要是精确的用代码表示出来，却又有一番难度，难处在于： （1）我们该怎么将我们的思维转换成这种直接的代码，根据两个序列建成一个二叉树，然后根据层序输出二叉树。 （2）先来看题意中的一个后序序列以及中序序列： number     7 postPrder  2 3 1 5 7 6 4 inOrder      1  2 3 4 5 6 7 我们自己来分析建树步骤： Step1:后序序列中最后一个肯定是根节点（如果连这个都不清楚的话，麻烦多看两边书…… Strep2:在中序序列中找到这个根节点值，从而将其左右两边分成左子树与右子树。 Step3:对其左子树以及右子树进行Step1,Step2操作，直到该根节点德左子树或者右子树为NULL时，返回根节点值。 Step4:最后一步简单，就是对其使用队列+二叉树，即可得到层序遍历结果。 3.编写代码 根据以上分析，我们大概就已经知道这么一个过程是什么样子： （1）要使用递归过程建树； （2）要返回不同的区间值； （3）……等等 4.源代码 #include #include #include using namespace std; #define maxSize 100 #define null NULL typedef struct BiTree{ struct BiTree *lChild,*rChild;//左右子树指针 int data;//数据域 }; int number; int postOrder[maxSize]; int inOrder[maxSize]; //从二叉树中找出结点并建树 //注意返回的是二叉树的头结点指针 BiTree* foundData(int postLeft,int postRight,int inLeft,int inRight){ if(postRight < postLeft){ return null; } int i ; int root;//根节点的值 int rootIndex;//根节点在中序数组中的下标 root = postOrder[postRight];//找到root BiTree *T; T = new BiTree;//指向具体的结点 T->data = root; //注意细节！for循环边界取值 for(i = inLeft;i <= inRight;i++){ if(inOrder[i] == postOrder[postRight]){ rootIndex = i;//记录下标 break; } } int leftNodeNumber ;//表示左子树包含的结点个数 leftNodeNumber = rootIndex - inLeft;//注意是减去inLeft,而非postLeft T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树 return T; } //前序遍历 void preTraverseBiTree(BiTree *T){ if(T == null){ return ; } printf("%d ",T->data); preTraverseBiTree(T->lChild); preTraverseBiTree(T->rChild); } //使用层次遍历（BFS） void BfsBiTree(BiTree *T){ int count = 0;//输出计数 queue q;//使用队列存储指针结点 q.push(T);//首先将根节点入队 while(!q.empty()){//当队列非空时 BiTree* now = q.front();//得到队首 q.pop(); //将根结点出队 count ++; if(count < number ) printf("%d ",now->data); //输出 else printf("%d",now->data); if(now->lChild!=null) q.push(now->lChild);//左子树入队 --->注意这里是now，而非是T!! if(now->rChild!=null) q.push(now->rChild);//右子树入队 } } int main(){ scanf("%d",&number); int i; for(i = 0;i< number;i++){ scanf("%d",&postOrder[i]); } //输入inOrder for(i = 0;i< number;i++){ scanf("%d",&inOrder[i]); } BiTree *T; T = foundData(0,number-1,0,number-1); //返回作为根节点 //preTraverseBiTree(T);//前序遍历二叉树 BfsBiTree(T); } /* 4 2 3 1 4 1 2 3 4 7 2 3 1 5 7 6 4 1 2 3 4 5 6 7 **/ 5.总结 （1） T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树 为整个代码的关键所在，关键之处在于： 1）明白一个递归过程的调用 2）确定范围值得选取  （2）对于上述的取区间的问题，我们首先应该对一个复杂的表达式抽取出一般项，然后对其一般项进行操作；.检验方法：试用多个特殊的项来对总结的表达式进行检验，判断一般项的正确性。  1）比如，对于上面的两个式子 T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树 我们将其区间合并一下得到：【postLeft,postLeft + leftNodeNumber -1,postLeft + leftNodeNumber,postRight -1】与【inLeft,rootIndex - 1,rootIndex + 1,inRight】是不是仔细想想就发现竟然是一个完整的区间！！！到这里大家终于明白了递归就是将一个大问题分解成很多小问题，然后这些小问题合并就是大问题分解的逆过程。如果知道了这一点，就会理解这个区间取值是怎么取的。希望大家好运！ T->lChild = foundData(postLeft, postLeft + leftNodeNumber -1,inLeft,rootIndex-1);//建左子树 T->rChild = foundData(postLeft + leftNodeNumber, postRight - 1,rootIndex + 1,inRight);//建右子树

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。