• 【数据结构】二叉树—二叉树镜面反转


    目录

    题目描述

    思路分析

    AC代码


    题目描述

    假设二叉树用二叉链表存储,用先序序列结果创建。输入二叉树的先序序列,请你先创建二叉树,并对树做个镜面反转,再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。

    --程序要求--

    程序中不允许使用STL库等第三方对象或函数实现本题的要求

    输入

    测试次数t

    每组测试数据是一个二叉树的先序遍历序列,#表示空树

    输出

    对每棵二叉树,输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树,输出四个NULL(后面不加空格,每个NULL独自一行,中间没有空行)。如下:

    NULL

    NULL

    NULL

    NULL

    输入样例1 

    3
    41#32###65##7##
    AB#C##D##
    AB##C##

    输出样例1

    4 6 7 5 1 3 2 
    7 6 5 4 3 2 1 
    7 5 6 2 3 1 4 
    4 6 1 7 5 3 2 
    A D B C 
    D A C B 
    D C B A 
    A D B C 
    A C B 
    C A B 
    C B A 
    A C B 

    思路分析

    我们假设你已经会了先序遍历、中序遍历、后序遍历和层次遍历。

    那么这道题其实非常简单,我们只需要在建树的时候,把原来的建树顺序改变一下即可,即,先建立右子树,再建立左子树。

    然后因为这道题说不能用STL,但是你的BFS,也就是你的层次遍历需要一个队列,所以你需要自己实现一个队列,在小数据的范围内,写一个简单的队列还是很简单的,用一个定长的数组,加上滑动双下标就可以实现一个队列了,当然是有范围的队列。

    AC代码

    1. #include
    2. #include
    3. using namespace std;
    4. class BiTreeNode {
    5. public:
    6. char data; //数据域
    7. int weight = 0;
    8. BiTreeNode *leftChild, *rightChild; //左右子树指针
    9. BiTreeNode() : leftChild(NULL), rightChild(NULL) {}
    10. ~BiTreeNode() {}
    11. };
    12. class mySTL {
    13. public:
    14. BiTreeNode *volume[10000];
    15. int front = 0;
    16. int rear = 0;
    17. BiTreeNode *top() {
    18. return volume[front];
    19. }
    20. void pop() {
    21. front++;
    22. }
    23. void push(BiTreeNode *item) {
    24. volume[rear++] = item;
    25. }
    26. bool empty() {
    27. if (front == rear)
    28. return true;
    29. return false;
    30. }
    31. };
    32. class BiTree {
    33. private:
    34. BiTreeNode *root; //根结点指针
    35. string sTree; //建树字符串
    36. int pos; //标识建树字符串的当前字符位置
    37. BiTreeNode *CreateTree();//建树私有函数
    38. public:
    39. int maxPath = 0;
    40. BiTree() : root(NULL) {};
    41. void Create(string vArray); //建树公有接口,参数是特定的先序遍历字符串
    42. void LevelOrder(BiTreeNode *T) {
    43. mySTL open;
    44. BiTreeNode *p = T;
    45. if (p)
    46. open.push(p);
    47. while (!open.empty()) {
    48. p = open.top();
    49. open.pop();
    50. if (p) {
    51. cout << p->data<<' ';
    52. open.push(p->leftChild);
    53. open.push(p->rightChild);
    54. }
    55. }
    56. cout << endl;
    57. }
    58. void PreOrder(BiTreeNode *T) {
    59. if (T == NULL)
    60. return;
    61. cout << T->data<<' ';
    62. PreOrder(T->leftChild);
    63. PreOrder(T->rightChild);
    64. }
    65. void InOrder(BiTreeNode *T) {
    66. if (T == NULL)
    67. return;
    68. InOrder(T->leftChild);
    69. cout << T->data<<' ';
    70. InOrder(T->rightChild);
    71. }
    72. void PostOrder(BiTreeNode *T) {
    73. if (T == NULL)
    74. return;
    75. PostOrder(T->leftChild);
    76. PostOrder(T->rightChild);
    77. cout << T->data<<' ';
    78. }
    79. void Show() {
    80. if(root==NULL){
    81. cout<<"NULL"<"NULL"<"NULL"<"NULL"<
    82. }
    83. PreOrder(root);
    84. cout << endl;
    85. InOrder(root);
    86. cout << endl;
    87. PostOrder(root);
    88. cout << endl;
    89. LevelOrder(root);
    90. }
    91. };
    92. void BiTree::Create(string vArray) {
    93. pos = 0;
    94. sTree.assign(vArray); //把参数保存到内部字符串
    95. root = CreateTree(); //建树成功后root指向根结点
    96. }
    97. BiTreeNode *BiTree::CreateTree() {
    98. if (pos == sTree.size() || sTree[pos] == '#') {
    99. pos++;
    100. return NULL;
    101. }
    102. BiTreeNode *T = new BiTreeNode();
    103. T->data = sTree[pos++];
    104. T->rightChild = CreateTree();
    105. T->leftChild = CreateTree();
    106. return T;
    107. }
    108. int main() {
    109. int t;
    110. string temp;
    111. cin >> t;
    112. while (t--) {
    113. cin >> temp;
    114. BiTree tree;
    115. tree.Create(temp);
    116. tree.Show();
    117. }
    118. return 0;
    119. }
  • 相关阅读:
    24考研王道408数据结构-第三章“栈、队列、数组”课后算法题(P70--栈的模拟)
    java开发手册-04安全规约
    新手GitHub使用指南
    【Git】Git基础操作一文详解,入门易懂(附图和案例)
    Java学习多态之向上转型
    Fetch与Axios数据请求
    Tomcat选择不同配置文件启动
    阿里云/腾讯云幻兽帕鲁服务器为什么更新/重启之后,服务器存档没了?
    二、vue基础语法
    ECharts多个数据视图进行自适应大小的解决方案
  • 原文地址:https://blog.csdn.net/weixin_62264287/article/details/127649820