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 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 */