首页 > 代码库 > 二元查找树的翻转（镜像）的两种思路
二元查找树的翻转（镜像）的两种思路
问题描述：
输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
算法：
测试用例：
10
/ \
5 11
/ \
3 7
/ \ / \
2 4 6 9
/ /
1 8
算法：
有两种思路：
①递归。对树翻转，只需对他的左右子树翻转，再交换左右子树的位置即可。
②非递归。设置一个队列queue，从根节点开始处理：人节点先入列，当队列非空时，循环进行以下处理：从队列中取出一节点，交换他的左右子树的位置，将它的左右子节点入列（若存在的话）。当队列为空时，返回。
代码实现：
①递归
//递归template<class T>void ReverseTree(BinaryTreeNode<T>* t){<span style="white-space:pre"> </span>if (!t)<span style="white-space:pre"> </span>return;<span style="white-space:pre"> </span>BinaryTreeNode<T>* temp = new BinaryTreeNode<T>;<span style="white-space:pre"> </span>temp = t->LeftChild;<span style="white-space:pre"> </span>t->LeftChild = t->RightChild;<span style="white-space:pre"> </span>t->RightChild = temp;<span style="white-space:pre"> </span>ReverseTree(t->LeftChild);<span style="white-space:pre"> </span>ReverseTree(t->RightChild);<span style="white-space:pre"> </span>return;}
非递归：
//非递归
template<class T>
void ReverseTree2(BinaryTreeNode<T>* t)
{
if (!t)
return;
Queue<BinaryTreeNode<T>*> q;
q.Add(t);
BinaryTreeNode<T>* tt = new BinaryTreeNode < T >;
while (!q.IsEmpty())
{
q.Delete(tt);
BinaryTreeNode<T>* temp = new BinaryTreeNode < T >;
temp = tt->LeftChild;
tt->LeftChild = tt->RightChild;
tt->RightChild = temp;
if (tt->LeftChild)
q.Add(tt->LeftChild);
if (tt->RightChild)
q.Add(tt->RightChild);
}
}
输出测试：
InOrder(n10); cout << endl; ReverseTree(n10); InOrder(n10); cout << endl; ReverseTree2(n10); InOrder(n10); cout << endl;
输出结果：
二元查找树的翻转（镜像）的两种思路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。