# 漫谈递归之完全二叉树

## 答案

```//完全二叉树：

/**

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);

}```

0 条评论

• ### 谈谈你对堆栈理解（初稿）

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

• ### 单链表中头节点作用(深入理解)

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

• ### 使用边界变异消减（BVD）算法的高阶中央-上风冲击捕获方案 (CS)

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

• ### Selecting multiple checkboxes inside a GridView control

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

• ### 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...

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

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

• ### 漫谈可视化Prefuse（五）---一款属于我自己的可视化工具

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