IT公司100题-15-求二元查找树的镜像

问题描述：

输入一颗二元查找树，将该树转换为它的镜像树，即对每一个节点，互换左右子树。

 

例如输入：

  6
/    \
4     12
/ \   /   \
2  5 8   16

输出：

  6
/     \
12     4
/   \   / \
16  8 5  2

定义二元查找树的结点为：

typedef struct BSTree {

    int data;

    BSTree* left;

    BSTree* right;

} Node;

分析：

方法1：递归交换左右子树。

// 15_1.cc

#include <iostream>

using namespace std;

typedef struct BSTree {

    int data;

    BSTree* left;

    BSTree* right;

} Node;

// 创建二元查找树

void add_BSTree_node(Node* &p_current, int data) {

    if (NULL == p_current) {

        Node *node = new Node();

        node->left = NULL;

        node->right = NULL;

        node->data = data;

        p_current = node;

    } else {

        if (p_current->data > data)

            add_BSTree_node(p_current->left, data);

        else if (p_current->data < data)

            add_BSTree_node(p_current->right, data);

        else

            cout << "The data has already in the tree.";

    }

}

// 转换二叉树为镜像树

void mirror_change(Node *root) {

    if(!root)

        return;

    // 交换左右子树

    Node* t = root->left;

    root->left = root->right;

    root->right = t;

    // 左右子树分别递归

    if(root->left)

        mirror_change(root->left);

    if(root->right)

        mirror_change(root->right);

}

// 中序打印镜像树

void print_tree(Node* root) {

    if (!root)

        return;

    cout << root->data << " ";

    print_tree(root->left);

    print_tree(root->right);

}

int main() {

    Node *root = NULL;

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    mirror_change(root);

    print_tree(root);

    cout << endl;

}

方法2：使用栈模仿递归过程：

// 15_2.cc

#include <iostream>

#include <stack>

using namespace std;

typedef struct BSTree {

    int data;

    BSTree* left;

    BSTree* right;

} Node;

// 创建二元查找树

void add_BSTree_node(Node* &p_current, int data) {

    if (NULL == p_current) {

        Node *node = new Node();

        node->left = NULL;

        node->right = NULL;

        node->data = data;

        p_current = node;

    } else {

        if (p_current->data > data)

            add_BSTree_node(p_current->left, data);

        else if (p_current->data < data)

            add_BSTree_node(p_current->right, data);

        else

            cout << "The data has already in the tree.";

    }

}

// 转换二叉树为镜像树

void mirror_change(Node *root) {

    if(!root)

        return;

    stack<Node*> s;

    s.push(root);

    Node* p;

    while(!s.empty()) {

        p = s.top();

        s.pop();

        // 交换左右子树

        Node* t = p->left;

        p->left = p->right;

        p->right = t;

        // 左右子树分别入栈

        if(p->left)

            s.push(p->left);

        if(p->right)

            s.push(p->right);

    }

}

// 中序打印镜像树

void print_tree(Node* root) {

    if (!root)

        return;

    cout << root->data << " ";

    print_tree(root->left);

    print_tree(root->right);

}

int main() {

    Node *root = NULL;

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    add_BSTree_node(root, );

    mirror_change(root);

    print_tree(root);

    cout << endl;

}