C++ 二叉树的镜像实例详解

2025-01-27 01:05:42

二叉树的镜像：将一个二叉树的左右子树，调换位置。即下图的形式：

递归的思想是：

从根节点的左右子树进行交换，然后以根节点的左子树为根节点，而后以根节点的右结点为根节点，进行左右子树交换。遇到空节点或叶节点直接返回。下面求二叉树镜像的函数代码实现：

template<class T>
void MirroTree(TreeNode<T> * root)
{
  if (root == NULL)
    return;
  if (root->_left == NULL && root->_right == NULL)
    return;
  else
  {
    TreeNode<T>* temp = root->_left;
    root->_left = root->_right;
    root->_right = temp;
  }
  MirroTree(root->_left);
  MirroTree(root->_right);
}

非递归实现思想：

利用stack栈的FILO，即先进后出原则，将根节点先行压入栈中，然后进入栈同时取栈顶结点并pop栈，然后交换左右子树的结点，若根节点的左右子树不为空，即压入栈中，直到栈为空则停止。

下面是非递归实现代码：

template<class T>
void MirroTree_NoR(TreeNode<T>* root)
{
  stack<TreeNode<T>*> s;
  s.push(root);
  while (s.size())
  {
    TreeNode<T>* Top = s.top();
    if (Top->_left != NULL || Top->_right != NULL)
    {
      TreeNode<T>* temp = Top->_left;
      Top->_left = Top->_right;
      Top->_right = temp;
    }
    if (Top->_left != NULL)
      s.push(Top->_left);
    if (Top->_right != NULL)
      s.push(Top->_right);
  }
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

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

本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st
C++ 二叉树的镜像实例详解

二叉树的镜像:将一个二叉树的左右子树,调换位置.即下图的形式: 递归的思想是: 从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换.遇到空节点或叶节点直接返回.下面求二叉树镜像的函数代码实现: template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL &&
jenkins构建Docker 镜像实例详解

jenkins构建Docker 镜像实例详解前言:jenkins有Docker镜像,而之前我们说过使用jenkins打包Docker镜像,那么可否用jenkins的Docker镜像打包Docker镜像呢? 环境: CentOS 7 Docker 1.10.3 1.本机安装docker环境,并配置TCP访问接口 # vi /usr/lib/systemd/system/docker.service 修改ExecStart为: ExecStart=/usr/bin/docker daem
C++ 遍历二叉树实例详解

C++ 遍历二叉树实例详解 2叉数又叫红黑树,关于2叉数的遍历问题,有很多,一般有三种常用遍历方法: (1)前序遍历(2)中序遍历(3)后续遍历以下是经典示例: #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include <math.h > #define MaxSize 20 typedef struct BiTNode { int data; struct BiTNode
docker使用registry搭建本地镜像仓库实例详解

目录一.系统环境二.前言三.使用registry搭建私有镜像仓库 3.1 环境介绍 3.2 k8smaster节点配置镜像仓库 3.3 k8sworker1节点配置从私有仓库上传和拉取镜像 3.3.1 上传镜像到私有仓库 3.3.2 从私有仓库里拉取镜像四.附录:删除私有仓库镜像的Python脚本一.系统环境服务器版本 docker软件版本 CPU架构 CentOS Linux release 7.4.1708 (Core) Docker version 20.10.12 x86_6
hibernate4快速入门实例详解

Hibernate是什么 Hibernate是一个轻量级的ORMapping框架 ORMapping原理(Object RelationalMapping) ORMapping基本对应规则: 1:类跟表相对应 2:类的属性跟表的字段相对应 3:类的实例与表中具体的一条记录相对应 4:一个类可以对应多个表,一个表也可以对应对个类 5:DB中的表可以没有主键,但是Object中必须设置主键字段 6:DB中表与表之间的关系(如:外键)映射成为Object之间的关系 7:Object中属性的个数和名称可
Docker Swarm入门实例详解

Swarm 在 Docker 1.12 版本之前属于一个独立的项目,在 Docker 1.12 版本发布之后,该项目合并到了 Docker 中,成为 Docker 的一个子命令.目前,Swarm 是 Docker 社区提供的唯一一个原生支持 Docker 集群管理的工具.它可以把多个 Docker 主机组成的系统转换为单一的虚拟 Docker 主机,使得容器可以组成跨主机的子网网络. 1. Swarm 认识 Swarm 是目前 Docker 官方唯一指定(绑定)的集群管理工具.Docker 1.
Java 归并排序算法、堆排序算法实例详解

基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组
Vue的实例、生命周期与Vue脚手架（vue-cli）实例详解

一.Vue的实例 1.1.创建一个 Vue 的实例每个 Vue 应用都是通过 Vue 函数创建一个新的 Vue 实例开始的: var vm = new Vue({// 选项}) 虽然没有完全遵循 MVVM 模型,Vue 的设计无疑受到了它的启发.因此在文档中经常会使用 vm (ViewModel 的简称) 这个变量名表示 Vue 实例. 1.vue.js就是一个构造器,通过构造器Vue来实例化一个对象:例如:var vm = new Vue({}); 2.实例化Vue时,需要传入一个参数(选项
IntelliJ Idea SpringBoot 数据库增删改查实例详解

SpringBoot 是 SpringMVC 的升级,对于编码.配置.部署和监控,更加简单微服务微服务是一个新兴的软件架构,就是把一个大型的单个应用程序和服务拆分为数十个的支持微服务.一个微服务的策略可以让工作变得更为简便,它可扩展单个组件而不是整个的应用程序堆栈,从而满足服务等级协议. Spring 为微服务提供了一整套的组件-SpringClound , SpirngBoot 就是该基础. 第一个SpringBoot程序这里使用的开发软件是IntelliJ Idea,和Eclipse
Hadoop 分布式存储系统 HDFS的实例详解

HDFS是Hadoop Distribute File System 的简称,也就是Hadoop的一个分布式文件系统. 一.HDFS的优缺点 1.HDFS优点: a.高容错性 .数据保存多个副本 .数据丢的失后自动恢复 b.适合批处理 .移动计算而非移动数据 .数据位置暴露给计算框架 c.适合大数据处理 .GB.TB.甚至PB级的数据处理 .百万规模以上的文件数据 .10000+的节点 d.可构建在廉价的机器上 .通过多副本存储,提高可靠性 .提供了容错和恢复机制 2.HDFS缺点 a.低延迟数

C++ 二叉树的镜像实例详解

相关推荐

随机推荐