当前位置：网站首页>交换二叉树中每个结点的左和右

交换二叉树中每个结点的左和右

2022-04-23 03:03:00 【学习kl＆tk】

以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。

输入格式:

输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

输出有两行：

第一行是原二叉树的中序遍历序列；

第二行是交换后的二叉树的中序遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA

AFDGEBC

#include "bits/stdc++.h"

using namespace std;

struct Tree{
    char val;
    Tree* lchild;
    Tree* rchild;
};
int len = 0;
Tree* bulid(){
    char c;
    cin >> c;
    if(c=='#') return NULL;
    Tree* root = new Tree();
    root->val = c;
    root->lchild = bulid();
    root->rchild = bulid();
    return root;
}
string s;
void dfs(Tree* root){
    if(root == NULL) return;
    if(root->lchild) dfs(root->lchild);
    s+=root->val;
    if(root->rchild) dfs(root->rchild);
}
int main()
{
    Tree* root = bulid();
    dfs(root);
    cout << s<< endl;
    reverse(s.begin(),s.end());
    cout << s<< endl;
    return 0;
}

版权声明
本文为[学习kl＆tk]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_53013914/article/details/124280619