草庐IT

二叉树：求树的高度（递归和非递归算法）

花间半盘棋 2025-06-22 原文

题目：假设二叉树采用二叉链表存储结构，设计一个算法求二叉树的高度。

递归

分析：用递归方式来实现比较抽象，有一种没有解决问题的错觉。如果要理解递归，就要理解递归。。。但是递归的代码量少，简洁。如图，要以一种抽象化的方式来理解。不能具体，一旦具体了，就跟啥都没解决似的。

算法思想：递归左子树高度和右子树的高度，取较大者+1。
代码：

int BTdepth(BiTree T){  // 求树的高度depth
	if(T!=NULL)  // 空树的高度为零
		return 0;
	ldepth=BTdepth(T->lchild);  // 求左孩子的高度
	rdepth=BTdepth(T->rchild);  // 求右孩子的高度
	if(ldepth>rdepth) 
		ldepth=ldepth+1;  
		// 树的高度为最大高度的子树加个根结点
		return ldepth;
	else
		rdepth=rdepth+1;
		return rdepth;
}

非递归

分析：非递归比较难理解，是在层次遍历的基础上进行改造，也是借助队列完成。那么如何要求出树的高度？可以让一个变量last始终指向每一层最右端的结点，指了几个结点，就有几层，即二叉树的高度。
如图，rear指向入队的结点，front指向要出队的结点，last指向当前层最右端的结点。last是一个普通的变量，值为0，rear和front是队列的，指向-1。
根结点A入队，rear指向A

然后front前进一步，front指向A，A出队，访问，A有BC两个左右孩子，BC入队，front等于last，所以将last指向rear。注意只要front等于last了，就将last指向rear。

然后front前进一步，front指向B，B出队，访问，B有DE两个左右孩子，DE入队。
front前进一步，指向C，C没有左右孩子，C直接出队。
rear指向最后入队结点E。
此时front等于last，所以将last指向rear。
front往前走一步，指向D，D没有左右孩子，直接出队。

front向前走一步，指向E，E出队，访问，发现E有FG两个左右孩子，将FG入队，rear指向G，此时front=last，所以将last指向rear指向的结点。

front前进一步，指向F，没有左右孩子，直接出队；
front再前进一步，指向G，没有左右孩子，直接出队；
此时front=rear，结束循环，最终rear分别指向过ACEG，恰好是每层最右端的结点，结点个数为4，所以此二叉树的高度为4。

总结：rear指向每次入队的最后结点，front每次向前走一步，当fronreat时lastrear。这就是核❤思想。然后层数level加1，最后level的值就是二叉树的高度。

算法思想：采用层次遍历的算法，设置变量level记录当前结点所在的层数，设置变量last指向当前层的最右结点，每次层次遍历出队时与last指针比较，若两者相等，则层数加1，并让last指向下一层最右端的结点，直到遍历完成。level的值即为二叉树的高度。核❤问题在于如何让last指向每层最右端的结点。

代码：

int BTdepth(BiTree T){
	if(T==NULL)  // 空树的高度为0
		return 0;
	int front=-1,rear=-1;  // 初始化一个空的队列
	int last=0,level=0;  
	// last指向当前层的最右结点，level记录树的层数
	BiTree Q[MaxSize];  // 假设队列足够大
	Q[++rear]=T;  // 根结点入队
	BiTree p;  // 初始化指针p
	while(front<rear){  
	// 队列不空，则循环
	// fornt<rear说明有入队的操作，队列不空
		p=Q[++front];  
		// front指向要出队的结点
		// 当前front指向的队列元素出队并访问
		if(p->lchild)  // 如果有左孩子
			Q[++rear]=p->lchild;  // 左孩子入队
		if(p->rchild)  // 如果有右孩子
			Q[++rear]=p->rchild;  // 右孩子入队
		if(front==rear){  // ❤
			level++;  // 层数加1
			last=rear;  // ❤
		}
	}
	return level;
}
递归二叉树spanclasstoken数据结构图论b树算法

有关二叉树：求树的高度（递归和非递归算法）的更多相关文章

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

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

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

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

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

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

  4. 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:

  5. ruby-on-rails - 在 Rails 中需要整个目录树的好方法是什么？ - 2

    我正在使用Rails3.2.2并希望递归加载某个目录中的所有代码。例如:[Railsroot]/lib/my_lib/my_lib.rb[Railsroot]/lib/my_lib/subdir/support_file_00.rb[Railsroot]/lib/my_lib/subdir/support_file_01.rb...基于谷歌搜索，我试过:config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**"]config.autoload_paths+=["#{Rails.root.to_s}/lib/my_lib/**/"

  6. 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]我还增加了机器的堆栈大

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

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

  8. ruby-on-rails - 如何以递归方式将 YAML 文件扁平化为 JSON 对象，其中键是点分隔的字符串？ - 2

    例如，如果我有YAML文件en:questions:new:'NewQuestion'other:recent:'Recent'old:'Old'这最终会变成一个json对象，例如{'questions.new':'NewQuestion','questions.other.recent':'Recent','questions.other.old':'Old'} 最佳答案 由于问题是关于在Rails应用程序上使用YAML文件进行i18n，因此值得注意i18ngem提供了一个辅助模块I18n::Backend::Flatten完全像

  9. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  10. ruby - 在 Ruby 中实现 Luhn 算法 - 2

    我一直在尝试用Ruby实现Luhn算法。我一直在执行以下步骤:该公式根据其包含的校验位验证数字，该校验位通常附加到部分帐号以生成完整帐号。此帐号必须通过以下测试:从最右边的校验位开始向左移动，每第二个数字的值加倍。将乘积的数字(例如，10=1+0=1、14=1+4=5)与原始数字的未加倍数字相加。如果总模10等于0(如果总和以零结尾)，则根据Luhn公式该数字有效；否则无效。http://en.wikipedia.org/wiki/Luhn_algorithm这是我想出的:defvalidCreditCard(cardNumber)sum=0nums=cardNumber.to_s.s

随机推荐