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

2024-02-23 22:54:03 48

/*求二叉树镜像--采用递归和非递归方法经调试可运行源码及分析如下： ***/ #include #include #include usingstd::cout; usingstd::cin; usingstd::endl; usingstd::queue; /*二叉树结点定义*/ typedefstructBTreeNode { charelem; structBTreeNode*pleft; structBTreeNode*pright; }BTreeNode; /* 求二叉树镜像递归方式步骤：如果proot为NULL，则为空树，返回；如果proot不为NULL，交换proot左右结点，然后分别求左右子树的镜像； */ /*递归求二叉树镜像*/ voidget_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入队；第一步：当队列非空时，获取当前层次的节点总数，即当前队列的长度；执行第二步；第二步：按照当前层的节点总数，出队进行遍历节点，在遍历时，交换左右节点，如果左右节点存在，则入队；当遍历完当前层所有节点时，遍历下一层，执行第一步。 */ voidget_bitree_mirror_leveltraverse(BTreeNode*proot) { if(proot==NULL) return; queueque; que.push(proot); intlevel_nodes_number=0; while(!que.empty())//层次遍历 { level_nodes_number=que.size(); intlevel_count=0; while(level_countpleft; 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; returnbt; } /*先序创建二叉树*/ voidpre_crt_tree(BTreeNode*&bt) { charch; cin>>ch; if(ch=='#') { bt=NULL; } else { bt=newBTreeNode; bt->elem=ch; pre_crt_tree(bt->pleft); pre_crt_tree(bt->pright); } } /*先序遍历*/ voidpre_order_traverse(BTreeNode*proot) { if(proot==NULL) return; cout<elem<<""; pre_order_traverse(proot->pleft); pre_order_traverse(proot->pright); return; } intmain() { inttree_node_number=0; BTreeNode*bt; btree_init(bt);//初始化根节点 pre_crt_tree(bt);//创建二叉树 cout<<"先序遍历输出如下："<

/*
运行结果：
abc###de###
------以上为输入-----------
------以下为输出-----------
先序遍历输出如下：
调用镜像函数前：
abcde
递归调用镜像函数后：
adebc
非递归调用镜像函数后：
abcde
请按任意键继续...
---------------------------------
本例创建的二叉树形状：
a
bd
ce
调用递归求二叉树镜像形状：
a
db
ec
再次调用非递归求二叉树镜像形状（即镜像的镜像）:
a
bd
ce
*/

希望本文所述对大家C++程序设计有所帮助。

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

热门推荐

随机推荐