草庐IT

二叉树交换左右子树递归以及非递归算法

ucas-2023-An 2023-03-28 原文

递归方式基本思想：

  • 1、当待处理节点非空时，判断其左右孩子是否不同时为空：若是，转到2、否则分别递归调用左右子树进行操作。
  • 2、新建一个辅助结点，执行交换操作。
  • 3、递归调用非空的左右子树进行操作。
BiTree *exchangeChild(BiTree *&T){
	if(T==null) return null;//当结点为null直接return null
	if(T->lchild!=null||T->rchild!=null){//当待处理结点左右孩子不同时为空时交换
		BiTNode *temp=T->lchild;//辅助结点，用于交换
		T->lchild=T->rchild;
		T->rchild=temp;
	}
	//递归交换左右子树
	exchangeChild(T->lchild);
	exchangeChild(T->rchild);
	return T;
}

非递归方式基本思想：

需要利用队列进行操作：

  • 1、当待处理结点非空时入队。
  • 2、当队非空时，转到3、，否则代表操作完成，直接return 根结点。
  • 3、队头元素出队，判断其左右孩子是否不同时为空：若是，转到4、否则将非空的左右孩子依次入队，执行2、。
  • 4、新建一个辅助结点，执行交换操作。并将非空的左右孩子依次入队，执行2、。
BiTree *exchangeChild(BiTree *&T){
	BiTNode *temp;              //辅助结点，用于交换结点
	InitQueue(Q);               //利用队列实现，初始化队列
	if(T!=null) EnQueue(Q,T);   //当结点不为空时入队
	while(!IsEmpty(Q)){         //当队非空时
		DeQueue(Q,T);       //队首元素出队
		if(T->lchild!=null||T->rchild!=null){//当队首元素的左右孩子不同时为空时执行交换操作
			temp=T->lchild;
			T->lchild=T->rchild;
			T->rchild=temp;
		}
		//对非空的孩子结点入队，继续执行上述操作
		if(T->lchild!=null){
			EnQueue(Q,T->lchild);
		}
		if(T->rchild!=null){
			EnQueue(Q,T->rchild);
		}
	}
	return T;//返回根结点
}

                             若有错误，欢迎指正
                              我们一起进步！

递归二叉树入队lchildrchildC语言

有关二叉树交换左右子树递归以及非递归算法的更多相关文章

  1. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. 【鸿蒙应用开发系列】- 获取系统设备信息以及版本API兼容调用方式 - 2

    在应用开发中，有时候我们需要获取系统的设备信息，用于数据上报和行为分析。那在鸿蒙系统中，我们应该怎么去获取设备的系统信息呢，比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况，一种是设备信息的获取，一种是系统信息的获取。1.1、获取设备信息获取设备信息，鸿蒙的SDK包为我们提供了DeviceInfo类，通过该类的一些静态方法，可以获取设备信息，DeviceInfo类的包路径为：ohos.system.DeviceInfo.具体的方法如下：ModifierandTypeMethodDescriptionstatic StringgetAbiList​()Obt

  4. 阿里云国际版免费试用：如何注册以及注意事项 - 2

    作为新的阿里云用户，您可以50免费试用多种优惠，价值高达1,700美元（或8,500美元）。这将让您了解和体验阿里云平台上提供的一系列产品和服务。如果您以个人身份注册免费试用，您将获得价值1,700美元的优惠。但是，如果您是注册公司，您可以选择企业免费试用，提交基本信息通过企业实名注册验证，即可开始价值$8,500的免费试用！本教程介绍了如何设置您的帐户并使用您的免费试用版。​关于免费试用在我们开始此试用之前，您还必须遵守以下条款和条件才能访问您的免费试用：只有在一年内创建的账户才有资格获得阿里云免费试用。通过此免费试用优惠，用户可以免费试用免费试用活动页面上列出的每种产品一次。如果您有多个帐

  5. ruby - 递归地将所有数字字符串转换为 Ruby 哈希中的整数 - 2

    我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj

  6. Ruby:标准递归模式 - 2

    我经常迷上ruby​​的一件事是递归模式。例如，假设我有一个数组，它可能包含无限深度的数组作为元素。所以，例如:my_array=[1,[2,3,[4,5,[6,7]]]]我想创建一个方法，可以将数组展平为[1,2,3,4,5,6,7]。我知道.flatten可以完成这项工作，但这个问题是作为我经常遇到的递归问题的一个例子-因此我试图找到一个更可重用的解决方案。简而言之-我猜这种事情有一个标准模式，但我想不出任何特别优雅的东西。任何想法表示赞赏 最佳答案 递归是一种方法，它不依赖于语言。您在编写算法时要考虑两种情况:再次调用函数的情

  7. ruby - ruby 中的同一个程序如何接受来自用户的输入以及命令行参数 - 2

    我的ruby​​脚本从命令行参数获取某些输入。它检查是否缺少任何命令行参数，然后提示用户输入。但是我无法使用gets从用户那里获得输入。示例代码:test.rbname=""ARGV.eachdo|a|ifa.include?('-n')name=aputs"Argument:#{a}"endendifname==""puts"entername:"name=getsputsnameend运行脚本:rubytest.rbraghav-k错误结果:test.rb:6:in`gets':Nosuchfileordirectory-raghav-k(Errno::ENOENT)fromtes

  8. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  9. ruby - 为什么我用递归得到 "stack level too deep"？ - 2

    我有这个ruby代码:defget_sumnreturn0ifn似乎正在为999之前的值工作。当我尝试9999时，它给了我这个:stackleveltoodeep(SystemStackError)所以，我添加了这个:RubyVM::InstructionSequence.compile_option={:tailcall_optimization=>true,:trace_instruction=>false}但什么也没发生。我的ruby版本是:ruby1.9.3p392(2013-02-22revision39386)[x86_64-darwin12.2.1]我还增加了机器的堆栈大

  10. ruby - 构建网络蜘蛛时，应该使用递归吗？ - 2

    构建一个深度优先的网络蜘蛛，这意味着它将访问第一页上的所有链接，然后转到每个链接，并访问所有第二页上的链接...你应该使用递归吗？我发现这是CPU密集型的。defrecursion()linkz_on_first_page.eachdo|link|recursion(link)endendrecursion(firstpage) 最佳答案 绝对不是，由于万维网的实际性质，您很快就会遇到问题。当您访问带有主导航部分的网站时，每个页面都链接到其他页面，您就进入了一个无限循环。您可以跟踪您处理了哪些链接，但即便如此，递归循环并不真正适合万

随机推荐