个人中心
gpt4 book ai didi

C++基于递归和非递归算法求二叉树镜像的方法

转载 作者：qq735679552 更新时间：2022-09-28 22:32:09 27 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++基于递归和非递归算法求二叉树镜像的方法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法。分享给大家供大家参考，具体如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*求二叉树镜像 -- 采用递归和非递归方法
经调试可运行源码及分析如下：
***/
#include <stdlib.h>
#include <iostream>
#include <queue>
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 <BTreeNode*> 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;
}
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
运行结果：
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++基于递归和非递归算法求二叉树镜像的方法的文章就讲到这里了,如果你想了解更多关于C++基于递归和非递归算法求二叉树镜像的方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

27 4 0
文章推荐： 优化企业网站需要留意哪些问题?网站建设10大策划技巧
文章推荐： 如何设置Tomcat的默认端口(图文)
文章推荐： 汽车之家开发团队使用代码发布系统的经验总结
文章推荐： Tomcat7.0安装配置详细(图文)
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com