pat 1043（patrol）

pat 1043（patrol）

1.pat 1043是一道有质量的二叉树题目 2.题意分析 A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: 【一棵二叉排序树是被递归定义为一棵二叉树，具有以下性质：】 The left subtree of a node contains only nodes with keys less than the node's key. 【一个结点的左子树仅仅包含结点值小于该节点的值的结点】 The right subtree of a node contains only nodes with keys greater than or equal to the node's key. 【一个结点的右子树仅仅包含结点值大于等于该节点的值的结点】 Both the left and right subtrees must also be binary search trees. 【左右子树必须都是二叉排序树】 If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST. 【如果我们调换左右子树的每个节点，我们将得到的新二叉树称为二叉树的镜像】 Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST. 【现在，给出一串整数，你将判断其是否是二叉树或者是二叉树的镜像的先序遍历序列】 Input Specification: 【输入解释】 Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space. 【每个输入文件包含一个测试用例，对于每个测试用例，第一行是一个小于1000的正整数N。接着下一行会给出N个正整数，所有的数是被一个空格分割】 Output Specification: 【具体输出】 For each test case, first print in a line "YES" if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or "NO" if not. Then if the answer is "YES", print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. 【对于每个测试用例，第一行打印“YES”,，如果序列是二叉排序树或者是二叉排序树镜像的先序遍历，然后在下一行输出那个树的后序遍历序列；如果不是先序序列，则输出“NO”】 我甚是“无聊”，于是将这题目的所有描述都给粘贴过来了。并且将其翻译成了中文。 3.源代码 #include #define null NULL #define maxSize 1003 typedef struct BiTree{ struct BiTree *lChild,*rChild;//左右子指针 int data;//数据域 }BiTree; int start[maxSize];//初始数组 int result1[maxSize];//先序遍历结果数组 int result2[maxSize];//后序遍历结果数组 int result3[maxSize];//DRL遍历结果数组 int result4[maxSize];//DRL遍历结果数组 int count1 = 0;//申请一个全局变量，用来存储LDR（先序遍历） int count2 = 0;//用来存储LRD（后序遍历） int count3 = 0;//用来存储DRL（未定义名遍历） int count4 = 0;//用来存储RLD（未定义名遍历） void insertBiTree(BiTree *&bt,int da){ //先判断树是否为空-->如果为空，则建树，直接返回 if(bt==null){ bt = new BiTree;//因为在main函数中，bt是null，所以需要先让其指向一个节点，才能在该节点上赋值操作！ bt->data = da; bt->lChild = null; bt->rChild = null; return ; } BiTree *pre;//探索指针 pre = bt; BiTree *follow;//跟随指针 follow = bt; int flag = -1; while(pre!=NULL){ if(pre->data <= da ) {//需要循环测试是否为null follow = pre;//暂存值 pre = pre->rChild; //变化的是follow!! flag = 1; } else if( pre != null && pre->data > da ){//需要循环测试是否为null follow = pre;//暂存值 pre = pre->lChild;//变化的是follow!! flag = -1; } } //注意！！如果说是跟随指针发现孩子为null,则添加节点，且将当前指针（pre）的孩子设成temp if(pre == null){ //下面是新建一个BiTree节点，并将其修改成标志的二叉树节点（左右子树均赋为空） BiTree *temp; temp = new BiTree; temp->data = da;//插入数据 temp->lChild = null; temp->rChild = null; if(flag == 1){ follow->rChild = temp; flag = -1; } else if(flag == -1){ follow->lChild = temp; flag = -1; } } } //先序遍历正常二叉树 void preOrderBiTree(BiTree *T){ if(T!=null){ result1[count1++] = T->data; //printf("%d ",T->data); } else return ;//否则终止递归--->递归结束边界 preOrderBiTree(T->lChild);//递归左子树 preOrderBiTree(T->rChild);//递归右子树 } //后序遍历正常二叉树 void postOrderBiTree(BiTree *T){ if(T!=null){ postOrderBiTree(T->lChild);//递归左子树 postOrderBiTree(T->rChild);//递归右子树 result2[count2++] = T->data; } else return ;//否则终止递归--->递归结束边界 } //DRL遍历正常二叉树--->得到镜像二叉树数据 void DRLOrderBiTree(BiTree *T){ if(T!=null){ result3[count3++] = T->data; DRLOrderBiTree(T->rChild);//递归右子树 DRLOrderBiTree(T->lChild);//递归左子树 } else return ;//否则终止递归--->递归结束边界 } //RLD遍历镜像二叉树 void RLDOrderBiTree(BiTree *T){ if(T!=null){ RLDOrderBiTree(T->rChild);//递归右子树 RLDOrderBiTree(T->lChild);//递归左子树 result4[count4++] = T->data; //printf("%d ",T->data); } else return ;//否则终止递归--->递归结束边界 } int main(){ BiTree *bt;//新建一个BiTree型头指针 bt = null;//初始化为null int number;//表示节点数 scanf("%d",&number);//输入number int i; int da; for(i = 0;i< number;i++){ scanf("%d",&da); start[i] = da;//存放到start中 insertBiTree(bt,da);//从bt的左子树中插入值到树中 } //先序遍历输出二叉树 preOrderBiTree(bt); postOrderBiTree(bt); DRLOrderBiTree(bt); RLDOrderBiTree(bt); //比较两个数组是否相同 for(i = 0;i< number;i++){ if(start[i]!=result1[i]){ break; } } if(i == number ){ printf("YES\n"); for(int j = 0;j < number ;j++){//输出后序遍历序列 if(j < number-1) { printf("%d ",result2[j]); } else printf("%d\n",result2[j]); } return 0; } for(i = 0;i< number;i++){ if(start[i]!=result3[i]){ break; } } if(i< number ){ printf("NO\n"); } else{ printf("YES\n"); for(int j = 0;j < number ;j++){//输出遍历序列 if(j < number-1) { printf("%d ",result4[j]); } else printf("%d\n",result4[j]); } } } /**测试用例 7 8 6 5 7 10 8 11 7 8 10 11 8 6 7 5 7 8 6 8 5 10 9 11 */4.总结 需要注意的地方有以下几处： （1）如果不使用递归的手法，你会建立一棵二叉排序树么？想想在建立二叉排序树的关键是什么！ （2）怎么实现判断二叉排序树的镜像的先序？不妨可以试试其与二叉排序树有什么关联。亲自试验之后，你会发现其实镜像就是二叉排序树的另外的几种输出方式罢了！

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