数据结构篇：二叉树（四：交换左右子树）

应用递归思想

如果结点不为空，就交换其左右子树，而待交换的左右子树，我们不需要关心是否为空。

void Tree::ExChangeTree(BiTree *T) {

    BiTree *temp = new BiTree;
    if (T)
    {
        temp = T->rchild;
        T->rchild = T->lchild;
        T->lchild = temp;
        ExChangeTree(T->lchild);
        ExChangeTree(T->rchild);
    }
    else
    {
        return;
    }
}

运行截图

完整程序

//
// Created by 烟雨迷离半世殇 on 2018/11/28.
//

#include <iostream>
#include <string.h>

using namespace std;

struct BiTree {
    char data;
    BiTree *lchild, *rchild;
};

class Tree {
    BiTree *pt;
public :
    Tree() {
        pt = NULL;
    }

    BiTree *PreCreateBiTree();

    void PreOrderTraverse(BiTree *T);

    void InOrderTraverse(BiTree *T);

    void LastOrderTraverse(BiTree *T);

    void ExChangeTree(BiTree *T);
};

BiTree *Tree::PreCreateBiTree() {
    BiTree *T;
    char c;
    cin >> c;
    if (c == '#')
    {
        T = NULL;
    }
    else
    {
        T = new BiTree;
        if (!T)
        {
            cout << "请求内存失败。" << endl;
        }
        else
        {
            T->data = c;
        }
        T->lchild = PreCreateBiTree();
        T->rchild = PreCreateBiTree();
    }
    return T;
}

void Tree::PreOrderTraverse(BiTree *T) {
    if (!T)
    {
        return;
    }
    else
    {
        cout << T->data << " ";
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

void Tree::InOrderTraverse(BiTree *T) {
    if (!T)
    {
        return;
    }
    else
    {
        InOrderTraverse(T->lchild);
        cout << T->data << " ";
        InOrderTraverse(T->rchild);
    }
}

void Tree::LastOrderTraverse(BiTree *T) {
    if (!T)
    {
        return;
    }
    else
    {
        LastOrderTraverse(T->lchild);
        LastOrderTraverse(T->rchild);
        cout << T->data << " ";
    }
}

void Tree::ExChangeTree(BiTree *T) {

    BiTree *temp = new BiTree;
    if (T)
    {
        temp = T->rchild;
        T->rchild = T->lchild;
        T->lchild = temp;
        ExChangeTree(T->lchild);
        ExChangeTree(T->rchild);
    }
    else
    {
        return;
    }
}


int main() {
    Tree tree;
    BiTree *biTree;
    cout << "请以先序顺序输入数元素，以'#'代表虚空元素" << endl;
    biTree = tree.PreCreateBiTree();
    cout << "先序遍历结果为: " << endl;
    tree.PreOrderTraverse(biTree);
    cout << endl;
    cout << "中序遍历结果为: " << endl;
    tree.InOrderTraverse(biTree);
    cout << endl;
    cout << "后序遍历结果为: " << endl;
    tree.LastOrderTraverse(biTree);
    cout << "交换左右子树结果为: " << endl;
    tree.ExChangeTree(biTree);
    cout << "先序遍历结果为: " << endl;
    tree.PreOrderTraverse(biTree);
    cout << endl;
    cout << "中序遍历结果为: " << endl;
    tree.InOrderTraverse(biTree);
    cout << endl;
    cout << "后序遍历结果为: " << endl;
    tree.LastOrderTraverse(biTree);
    return 0;
}