c++ - 关于平衡二叉树优化算法
黄舟
黄舟 2017-04-17 11:39:52
[C++讨论组]

这是在geeksforgeeks上找到的关于平衡二叉树的优化算法,思路是在递归求深度的同时判断是否是平衡二叉树,解决了求深度的时候递归返回值的问题,但是还是不太理解那两行递归具体是怎么调用的?问题在注释中

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
  int data;
  struct node* left;
  struct node* right;
};

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);  
  r = isBalanced(root->right,&rh);
 //1.既然递归结束的条件是第一参数为NULL,那么l,r最终不都应该return true了吗?
 //2.lh,rh一直处于递归函数中,每次都被赋值成0,他们的值是怎么改变的?
  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}
黄舟
黄舟

人生最曼妙的风景,竟是内心的淡定与从容!

全部回复(1)
ringa_lee

1.既然递归结束的条件是第一参数为NULL,那么l,r最终不都应该return true了吗?

只有最深的那一层递归返回 1 吧? 下面注释写的非常清楚,如果左右高度不等,差距大于2,返回 0.

2.lh,rh一直处于递归函数中,每次都被赋值成0,他们的值是怎么改变的?

这个,你是不是看糊涂了呢? lh 和 rh 进入递归后,名字是 height,其改变的地方就在你问题的下面。。。

*height = (lh > rh? lh: rh) + 1;

个人认为,题主应该是没明白递归的基本概念,建议温习一下基础的递归知识。

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号