首页 > 代码库 > IT公司100题-15-求二元查找树的镜像

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

2024-07-16 20:04:42   222人阅读

问题描述：

输入一颗二元查找树，将该树转换为它的镜像树，即对每一个节点，互换左右子树。
 
例如输入：
  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 =http://www.mamicode.com/ 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, 8);    add_BSTree_node(root, 10);    add_BSTree_node(root, 6);    add_BSTree_node(root, 9);    add_BSTree_node(root, 11);    add_BSTree_node(root, 5);    add_BSTree_node(root, 7);    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 =http://www.mamicode.com/ 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, 8);    add_BSTree_node(root, 10);    add_BSTree_node(root, 6);    add_BSTree_node(root, 9);    add_BSTree_node(root, 11);    add_BSTree_node(root, 5);    add_BSTree_node(root, 7);    mirror_change(root);    print_tree(root);    cout << endl;}

 


联系
我们