本文实例讲述了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 dc e调用递归求二叉树镜像形状： ad b e c再次调用非递归求二叉树镜像形状（即镜像的镜像）: a b dc e*/ |
希望本文所述对大家C++程序设计有所帮助。
