当前位置:   article > 正文

树1----7-3 列出叶结点

树1----7-3 列出叶结点

对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶结点。

输入格式:

首先第一行给出一个正整数 n(≤10),为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 "-"。编号间以 1 个空格分隔。

输出格式:

在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

  1. 8
  2. 1 -
  3. - -
  4. 0 -
  5. 2 7
  6. - -
  7. - -
  8. 5 -
  9. 4 6

输出样例:

4 1 5

代码演示:

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct node{
  4. int data;
  5. struct node*left;
  6. struct node*right;
  7. }Node;
  8. typedef struct que{
  9. Node *data[1000];
  10. int front;
  11. int rear;
  12. }queue;
  13. int Findhead(char **node,int n){
  14. int test[n];
  15. for(int i=0;i<n;i++){
  16. test[i] = 0;
  17. }
  18. for(int i=0;i<n;i++){
  19. if(node[i][0] != '-'){
  20. test[(node[i][0]-'0')] = 1;
  21. }
  22. if(node[i][2] != '-'){
  23. test[(node[i][2]-'0')] = 1;
  24. }
  25. }
  26. int flag;
  27. for(int i=0;i<n;i++){
  28. if(test[i] == 0){
  29. flag = i;
  30. break;
  31. }
  32. }
  33. return flag;
  34. }
  35. Node *createtree(int head,Node *root,char **node,int n){
  36. root = (Node*)malloc(sizeof(Node));
  37. root->data = head;
  38. root->left = NULL;
  39. root->right = NULL;
  40. if(node[head][0]!='-'){
  41. root->left = createtree(node[head][0]-'0',root->left,node,n);
  42. }
  43. if(node[head][2]!='-'){
  44. root->right = createtree(node[head][2]-'0',root->left,node,n);
  45. }
  46. return root;
  47. }
  48. void levelprintleave(Node *root)
  49. {
  50. int flag = 0;
  51. if(root){
  52. queue *Q = (queue*)malloc(sizeof(queue));
  53. Q->front = -1;
  54. Q->rear = -1;
  55. Q->data[++Q->rear] = root;//初始化
  56. while(Q->front<Q->rear){
  57. Node *item = Q->data[++Q->front];//留值
  58. if(!item->left&&!item->right){
  59. if(flag==0){
  60. flag = 1;
  61. printf("%d",item->data);
  62. }else
  63. printf(" %d",item->data);//访问
  64. }
  65. if(item->left){
  66. Q->data[++Q->rear] = item->left;
  67. }
  68. if(item->right){
  69. Q->data[++Q->rear] = item->right;
  70. }
  71. }
  72. }
  73. }
  74. int main()
  75. {
  76. int n;
  77. scanf("%d",&n);
  78. char **node = (char**)malloc(sizeof(char*)*n);
  79. getchar();
  80. for(int i=0;i<n;i++){
  81. node[i] = (char *)malloc(sizeof(char)*4);
  82. gets(node[i]);
  83. }
  84. int head = Findhead(node,n);
  85. Node *root = createtree(head,root,node,n);
  86. levelprintleave(root);
  87. return 0;
  88. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/721734
推荐阅读
相关标签
  

闽ICP备14008679号