设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › PTA A_1020 Tree Traversals
返回列表 发新帖
查看: 1390|回复: 0

[技术交流] PTA A_1020 Tree Traversals

[复制链接]
798236606
发表于 2020-2-9 16:44:25 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 798236606 于 2020-2-9 16:43 编辑

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072

解：
1.二叉查找树递归插入+广度优先遍历
  1. #include<cstdio>
  2. #include<queue>

  4. using namespace std;

  6. typedef struct node{
  7.     int data;
  8.     struct node *lchild, *rchild;
  9.    
  10.     node()
  11.     {
  12.         lchild = rchild = NULL;
  13.     }
  14. }BTNode, *BTREE;

  16. int n, postorder[35], inorder[35];

  18. int find(int target)
  19. {
  20.     for (int i = 0; i < n; i++)
  21.         if (inorder[i] == target)
  22.             return i;
  23.             
  24.     return -1;
  25. }

  27. void insert(BTREE root, int pos)
  28. {
  29.     if (!root) return;
  30.    
  31.     int parents = find(root->data);
  32.    
  33.     if (pos > parents)
  34.     {
  35.         if (root->rchild)
  36.             insert(root->rchild, pos);
  37.         else
  38.         {
  39.             root->rchild = new BTNode;
  40.             root->rchild->data = inorder[pos];
  41.         }
  42.     }
  43.     else
  44.     {
  45.         if (root->lchild)
  46.             insert(root->lchild, pos);
  47.         else
  48.         {
  49.             root->lchild = new BTNode;
  50.             root->lchild->data = inorder[pos];
  51.         }           
  52.     }
  53. }

  55. void BFS(BTREE root)
  56. {
  57.     queue<BTREE> q;
  58.    
  59.     q.push(root);
  60.    
  61.     while (1)
  62.     {
  63.         printf("%d", q.front()->data);
  64.         
  65.         if (q.front()->lchild) q.push(q.front()->lchild);
  66.         if (q.front()->rchild) q.push(q.front()->rchild);
  67.         q.pop();
  68.         
  69.         if (q.empty()) break;

  71.         putchar(' ');
  72.     }
  73. }

  75. int main(void)
  76. {
  77.     scanf("%d", &n);
  78.    
  79.     if (!n) return 0;
  80.    
  81.     for (int i = 0; i < n; i++)
  82.         scanf("%d", postorder + i);
  83.         
  84.     for (int i = 0; i < n; i++)
  85.         scanf("%d", inorder + i);
  86.    
  87.     BTREE root = new BTNode;   
  88.     root->data = postorder[n - 1];
  89.    
  90.     for (int i = n - 2; i >= 0; i--)
  91.         insert(root, find(postorder[i]));
  92.         
  93.     BFS(root);

  95.     return 0;   
  96. }
复制代码

2.二叉查找树迭代插入+广度优先遍历
  1. #include<cstdio>
  2. #include<queue>

  4. using namespace std;

  6. typedef struct node{
  7.     int data;
  8.     struct node *lchild, *rchild;

  10.     node()
  11.     {
  12.         lchild = rchild = NULL;
  13.     }
  14. } BTNode, *BTREE;

  16. int n, postorder[35], inorder[35];

  18. int find(int target)
  19. {
  20.     for (int i = 0; i < n; i++)
  21.         if (inorder[i] == target)
  22.             return i;

  24.     return -1;
  25. }

  27. void insert(BTREE root, int pos)
  28. {
  29.     if (!root) return;

  31.     BTREE child = new BTNode;
  32.     child->data = inorder[pos];

  34.     while (1)
  35.     {
  36.         if (pos > find(root->data))
  37.         {
  38.             if (root->rchild)
  39.                 root = root->rchild;
  40.             else
  41.             {
  42.                 root->rchild = child;
  43.                 break;
  44.             }
  45.         }
  46.         else
  47.         {
  48.             if (root->lchild)
  49.                 root = root->lchild;
  50.             else
  51.             {
  52.                 root->lchild = child;
  53.                 break;
  54.             }
  55.         }
  56.     }
  57. }

  59. void BFS(BTREE root)
  60. {
  61.     queue<BTREE> q;

  63.     q.push(root);

  65.     while (1)
  66.     {
  67.         printf("%d", q.front()->data);

  69.         if (q.front()->lchild) q.push(q.front()->lchild);
  70.         if (q.front()->rchild) q.push(q.front()->rchild);
  71.         q.pop();

  73.         if (q.empty()) break;

  75.         putchar(' ');
  76.     }
  77. }

  79. int main(void)
  80. {
  81.     scanf("%d", &n);

  83.     if (!n) return 0;

  85.     for (int i = 0; i < n; i++)
  86.         scanf("%d", postorder + i);

  88.     for (int i = 0; i < n; i++)
  89.         scanf("%d", inorder + i);

  91.     BTREE root = new BTNode;
  92.     root->data = postorder[n - 1];

  94.     for (int i = n - 2; i >= 0; i--)
  95.         insert(root, find(postorder[i]));

  97.     BFS(root);

  99.     return 0;
  100. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-27 13:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表