开发者社区> 问答> 正文

关于平衡二叉树优化算法

这是在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;
}

展开
收起
a123456678 2016-06-07 18:30:01 2218 0
1 条回答
写回答
取消 提交回答
  • 码农|Coder| Pythonista

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

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

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

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

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

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

    2019-07-17 19:30:41
    赞同 展开评论 打赏
问答分类:
问答标签:
问答地址:
相关产品:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载