BJFU_数据结构习题_291平衡二叉树的高度的计算

待我称王封你为后i 2023-06-12 09:48 4阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 平衡二叉树的高度的计算 ###

**描述**  
假设一棵平衡二叉树的每个结点都标明了平衡因子b，设计一个算法，求平衡二叉树的高度。  
**输入**  
多组数据，每组数据一行，为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“\#”时，输入结束。  
**输出**  
每组数据输出一行，为平衡二叉树的高度。  
**输入样例 1**  
110\#\#\#0\#\#  
1110\#\#\#0\#\#10\#\#\#

#  #

**输出样例 1**  
3  
4

**第一种 普通递归**

#include<iostream>
    using namespace std;
    typedef struct BiTNode
    {
        
    	char data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    void CreateBiTree(BiTree &T,char S[],int &i)
    {
        
    	if(S[i]=='#')
    		T=NULL;
    	else
    	{
        
    		T=new BiTNode;
    		T->data=S[i];
    		CreateBiTree(T->lchild,S,++i);
    		CreateBiTree(T->rchild,S,++i);
    	}
    }
    int Depth(BiTree T)
    {
        
    	if(!T)
    		return 0;
    	else if(!T->lchild&&!T->rchild)
    		return 1;
    	return Depth(T->lchild)>=Depth(T->rchild)?Depth(T->lchild)+1:Depth(T->rchild)+1;
    }
    int main()
    {
        
    	char S[200];
    	while(cin>>S&&S[0]!='#')
    	{
        
    		int i=-1;
    	  	BiTree T;
    		CreateBiTree(T,S,++i);
    		cout<<Depth(T)<<endl;
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关 BJFU_数据结构习题_291平衡二叉树的高度的计算

欢迎登录北京林业大学OJ系统 [http://www.bjfuacm.com][http_www.bjfuacm.com] 平衡二叉树的高度的计算描述假设一

待我称王封你为后i/ 2023年06月12日 09:48/ 0 赞/ 5 阅读

相关数据结构-平衡二叉树

> 1.定义平衡二叉树又称为AVL树，或者为空树，或者具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。

た入场券/ 2023年06月09日 15:28/ 0 赞/ 144 阅读

相关 BJFU_数据结构习题_289二叉排序树的限定条件下的数据输出

欢迎登录北京林业大学OJ系统 [http://www.bjfuacm.com][http_www.bjfuacm.com] 289二叉排序树的限定条件下的数据输出

小咪咪/ 2023年05月30日 06:21/ 0 赞/ 26 阅读

相关 BJFU_数据结构习题_288二叉排序树的判定

欢迎登录北京林业大学OJ系统 [http://www.bjfuacm.com][http_www.bjfuacm.com] 288二叉排序树的判定描述假设二

╰+哭是因爲堅強的太久メ/ 2023年05月30日 06:21/ 0 赞/ 21 阅读

相关 BJFU_数据结构习题_272基于二叉树的表达式求值

欢迎登录北京林业大学OJ系统 [http://www.bjfuacm.com][http_www.bjfuacm.com] 272基于二叉树的表达式求值描述

左手的ㄟ右手/ 2022年12月23日 07:06/ 0 赞/ 258 阅读

相关 leetcode---110. 平衡二叉树(高度平衡)

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为： > 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例 1:

冷不防/ 2022年11月28日 00:21/ 0 赞/ 203 阅读

相关数据结构平衡二叉树

平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree）:是一种二叉排序树，其中每

￡神魔★判官ぃ/ 2022年09月19日 04:08/ 0 赞/ 272 阅读

相关数据结构-平衡二叉树

定义平衡二叉树，是对二叉搜索树的一种优化。向二叉搜索树中插入元素时，不同的插入次序，将构造出不同结构的树。通俗来讲，就是会导致树的深度和平均查找长度(ASL ave

清疚/ 2022年06月06日 05:56/ 0 赞/ 277 阅读

相关数据结构 - 平衡二叉树

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

迈不过友情╰/ 2022年04月22日 07:28/ 0 赞/ 231 阅读

相关数据结构——树——平衡二叉树

平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度

电玩女神/ 2022年04月16日 03:22/ 0 赞/ 324 阅读