专栏首页架构说漫谈递归之完全二叉树

漫谈递归之完全二叉树

题目 完全二叉树

答案

//完全二叉树:

/**

1 Calculate the number of nodes (count) in the binary tree.

2 Start recursion of the binary tree from the root node of the binary tree with index (i) being set as 0 and the number of nodes in the binary (count).

3 If the current node under examination is NULL, then the tree is a complete binary tree. Return true.

4 If index (i) of the current node is greater than or equal to the number of nodes in the binary tree (count) i.e. (i>= count), then the tree is not a complete binary. Return false.

5 Recursively check the left and right sub-trees of the binary tree for same condition. 

For the left sub-tree use the index as (2*i + 1) while for the right sub-tree use the index as (2*i + 2).

6 The time complexity of the above algorithm is O(n). 

**/

bool isCompleteBinary(node *root)

{

    int total=isCompleteBinary(root);

   return is_complete_binary(root,1,total);



}

bool is_complete_binary(node *root,int index,int& length)

{

   if(root ==NULL)

   {

      return true;

   }

   if(index>length)

   {

     return false;

   }

  return  is_complete_binary(root->left,2*index,length) && is_complete_binary(root->right,2*index+1,length);

}

int get_node_number(node* root)

{

    if(root ==NULL)

    {

        return 0;

    }



    return 1+get_node_number(root->left)+get_node_number(root->right);

}

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 谈谈你对堆栈理解(初稿)

    为了理解堆栈区别, 我对比 c++,java,APP,javascipt(vue,v8) ,node.js, solidity, 都提到一个共同概念-虚拟机....

    程序员小王
  • 单链表中头节点作用(深入理解)

    今天QQ群里有人咨询一个问题 例如单链表中头节点作用 然后联想到做项目中解决core一个问题 虽然每天都在吃饭睡觉打豆豆,啥框架业务都不懂 解决了这一个...

    程序员小王
  • 每日一问08 什么是协程

    程序员小王
  • 使用边界变异消减(BVD)算法的高阶中央-上风冲击捕获方案 (CS)

    在本文中,我们提出了一种新型的基于边界变化递减(BVD)重构的冲击捕捉的混合非线性显式紧凑方案。在我们的方法中,我们通过BVD算法结合了一个非耗散的六阶中心紧凑...

    管欣8078776
  • Selecting multiple checkboxes inside a GridView control

    Introduction GridView is a new data bound control introduced by Microsoft in Vis...

    阿新
  • 聊聊flink的JDBCAppendTableSink

    flink-jdbc_2.11-1.7.0-sources.jar!/org/apache/flink/api/java/io/jdbc/JDBCAppendT...

    codecraft
  • Codeforces Round #434 (Div. 2, based on Technocup 2018 Elimination Round 1)&&Codeforces 861B Which

    B. Which floor? time limit per test:1 second memory limit per test:256 megabytes...

    Angel_Kitty
  • 聊聊flink的JDBCAppendTableSink

    flink-jdbc_2.11-1.7.0-sources.jar!/org/apache/flink/api/java/io/jdbc/JDBCAppendT...

    codecraft
  • Codeforces Round #483 (Div. 2) A. Game

    Initially there are nn integers a1,a2,…,ana1,a2,…,an written on the board. Each ...

    用户2965768
  • 漫谈可视化Prefuse(五)---一款属于我自己的可视化工具

      伴随着前期的基础积累,翻过API,读过一些Demo,总觉得自己已经摸透了Prefuse,小打小闹似乎已经无法满足内心膨胀的自己。还记得儿时看的《武状元苏乞儿...

    JackieZheng

扫码关注云+社区

领取腾讯云代金券