首页 > 代码库 > 【编程题目】输入一颗二元查找树，将该树转换为它的镜像
【编程题目】输入一颗二元查找树，将该树转换为它的镜像
第 15 题（树）：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/ \ / \
5 7 9 11
输出：
8
/ \
10 6
/ \ / \
11 9 7 5
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
思路：
做了几道题了，终于思路也上趟了。后序遍历做就可以了。
1 /* 2 第 15 题（树）： 3 题目：输入一颗二元查找树，将该树转换为它的镜像， 4 即在转换后的二元查找树中，左子树的结点都大于右子树的结点。 5 用递归和循环两种方法完成树的镜像转换。 6 例如输入： 7 8 8 / 9 6 10 10 / \ / 11 5 7 9 11 12 输出： 13 8 14 / 15 10 6 16 / \ / 17 11 9 7 5 18 定义二元查找树的结点为： 19 struct BSTreeNode // a node in the binary search tree (BST) 20 { 21 int m_nValue; // value of node 22 BSTreeNode *m_pLeft; // left child of node 23 BSTreeNode *m_pRight; // right child of node 24 }; 25 26 start time = 17:55 27 end time = 18:51 28 */ 29 30 31 //思路 后序遍历 32 #include <iostream> 33 #include <vector> 34 using namespace std; 35 36 typedef struct BSTreeNode // a node in the binary search tree (BST) 37 { 38 int m_nValue; // value of node 39 BSTreeNode *m_pLeft; // left child of node 40 BSTreeNode *m_pRight; // right child of node 41 }BSTreeNode; 42 43 int addBSTreeNode(BSTreeNode * &T, int data) //把data加入的以T为根的树中 44 { 45 if(T == NULL) //根节点单独处理 46 { 47 T = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 48 T->m_nValue =http://www.mamicode.com/ data; 49 T->m_pLeft = NULL; 50 T->m_pRight = NULL; 51 } 52 else 53 { 54 BSTreeNode * x = T; 55 BSTreeNode * px = NULL; 56 while(x != NULL) 57 { 58 if(data >= x->m_nValue) 59 { 60 px = x; 61 x = x->m_pRight; 62 } 63 else 64 { 65 px = x; 66 x = x->m_pLeft; 67 } 68 } 69 70 if(data >= px->m_nValue) 71 { 72 px->m_pRight = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 73 px->m_pRight->m_nValue =http://www.mamicode.com/ data; 74 px->m_pRight->m_pLeft = NULL; 75 px->m_pRight->m_pRight = NULL; 76 } 77 else 78 { 79 px->m_pLeft = (BSTreeNode *)malloc(sizeof(BSTreeNode)); 80 px->m_pLeft->m_nValue =http://www.mamicode.com/ data; 81 px->m_pLeft->m_pLeft = NULL; 82 px->m_pLeft->m_pRight = NULL; 83 } 84 } 85 return 1; 86 } 87 88 int RecursiveMirror(BSTreeNode * T) 89 { 90 if(T == NULL) 91 { 92 return 0; 93 } 94 else 95 { 96 RecursiveMirror(T->m_pLeft); 97 RecursiveMirror(T->m_pRight); 98 BSTreeNode * x = T->m_pLeft; 99 T->m_pLeft = T->m_pRight;100 T->m_pRight = x;101 }102 }103 104 int NonRecursiveMirror(BSTreeNode * T)105 {106 vector<BSTreeNode *> stack;107 int tag[50] = {0};108 int tagnum = 0;109 BSTreeNode * x = T;110 stack.push_back(T);111 while(!stack.empty())112 {113 while((x = stack.back()) != NULL)114 {115 x = x->m_pLeft;116 stack.push_back(x);117 tag[tagnum++] = 0;118 }119 while(tag[tagnum - 1] == 1) //注意先判断是否处理数据 再弹出120 {121 stack.pop_back();122 tagnum--;123 BSTreeNode * cur = stack.back();124 BSTreeNode * tmp = cur->m_pLeft;125 cur->m_pLeft = cur->m_pRight;126 cur->m_pRight = tmp;127 128 }129 stack.pop_back();130 tagnum--;131 if(!stack.empty()) //注意这里的条件132 {133 stack.push_back(stack.back()->m_pRight);134 tag[tagnum++] = 1;135 }136 137 }138 return 1;139 }140 int main()141 {142 BSTreeNode * T = NULL;143 addBSTreeNode(T, 8);144 addBSTreeNode(T, 6);145 addBSTreeNode(T, 10);146 addBSTreeNode(T, 5);147 addBSTreeNode(T, 7);148 addBSTreeNode(T, 9);149 addBSTreeNode(T, 11);150 151 NonRecursiveMirror(T);152 RecursiveMirror(T);153 return 1;154 }
上网搜答案，发现先序遍历也可以。而且先序遍历要比后序遍历写起来容易些。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。