这篇文章将为大家详细讲解有关C++中基于递归和非递归算法如何求二叉树镜像，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
创新互联网站建设由有经验的网站设计师、开发人员和项目经理组成的专业建站团队，负责网站视觉设计、用户体验优化、交互设计和前端开发等方面的工作，以确保网站外观精美、网站设计制作、网站制作易于使用并且具有良好的响应性。
具体如下：
/*求二叉树镜像 -- 采用递归和非递归方法
经调试可运行源码及分析如下：
***/
#include
#include
#include
using std::cout;
using std::cin;
using std::endl;
using std::queue;
/*二叉树结点定义*/
typedef struct BTreeNode
{
char elem;
struct BTreeNode *pleft;
struct BTreeNode *pright;
}BTreeNode;
/*
求二叉树镜像
递归方式步骤：
如果proot为NULL，则为空树，返回；
如果proot不为NULL，交换proot左右结点，然后分别求左右子树的镜像；
*/
/*递归求二叉树镜像*/
void get_bitree_mirror(BTreeNode* proot)
{
if (proot == NULL)
return ;
BTreeNode* temp_node = proot->pleft;
proot->pleft = proot->pright;
proot->pright = temp_node;
get_bitree_mirror(proot->pleft);
get_bitree_mirror(proot->pright);
return ;
}
/*
非递归方式步骤如下：
借助队列
首先，将根节点proot入队；
第一步：当队列非空时，获取当前层次的节点总数，即当前队列的长度；执行第二步；
第二步：按照当前层的节点总数，出队进行遍历节点，在遍历时，
交换左右节点，如果左右节点存在，则入队；
当遍历完当前层所有节点时，遍历下一层，执行第一步。
*/
void get_bitree_mirror_leveltraverse(BTreeNode* proot)
{
if(proot == NULL)
return ;
queue que;
que.push(proot);
int level_nodes_number = 0;
while (!que.empty())//层次遍历
{
level_nodes_number = que.size();
int level_count = 0;
while (level_count < level_nodes_number)
{
++level_count;
proot = que.front();
que.pop();
//交换左右子节点
BTreeNode* temp_node = proot->pleft;
proot->pleft = proot->pright;
proot->pright = temp_node;
if(proot->pleft != NULL)
que.push(proot->pleft);
if(proot->pright != NULL)
que.push(proot->pright);
}
}
return ;
}
/*初始化二叉树根节点*/
BTreeNode* btree_init(BTreeNode* &bt)
{
bt = NULL;
return bt;
}
/*先序创建二叉树*/
void pre_crt_tree(BTreeNode* &bt)
{
char ch;
cin >> ch;
if (ch == '#')
{
bt = NULL;
}
else
{
bt = new BTreeNode;
bt->elem = ch;
pre_crt_tree(bt->pleft);
pre_crt_tree(bt->pright);
}
}
/*先序遍历*/
void pre_order_traverse(BTreeNode* proot)
{
if(proot == NULL)
return;
cout<< proot->elem << " ";
pre_order_traverse(proot->pleft);
pre_order_traverse(proot->pright);
return;
}
int main()
{
int tree_node_number = 0;
BTreeNode *bt;
btree_init(bt);//初始化根节点
pre_crt_tree(bt);//创建二叉树
cout << "先序遍历输出如下：" << endl;
cout << "调用镜像函数前：" << endl;
pre_order_traverse(bt);
cout << endl;
get_bitree_mirror(bt);
cout << "递归调用镜像函数后：" << endl;
pre_order_traverse(bt);
cout << endl;
cout << "非递归调用镜像函数后：" << endl;
get_bitree_mirror_leveltraverse(bt);
pre_order_traverse(bt);
cout << endl;
system("pause");
return 0;
}
/*
运行结果：
a b c # # # d e # # #
------以上为输入-----------
------以下为输出-----------
先序遍历输出如下：
调用镜像函数前：
a b c d e
递归调用镜像函数后：
a d e b c
非递归调用镜像函数后：
a b c d e
请按任意键继续. . .
---------------------------------
本例创建的二叉树形状：
a
b d
c e
调用递归求二叉树镜像形状：
a
d b
e c
再次调用非递归求二叉树镜像形状（即镜像的镜像）:
a
b d
c e
*/
关于“C++中基于递归和非递归算法如何求二叉树镜像”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
网站标题：C++中基于递归和非递归算法如何求二叉树镜像
URL标题：
http://bjjierui.cn/article/pjgeoi.html
