【算法集训】基础数据结构:九、完全二叉树
2023-12-16 19:19:46
完全二叉树是二叉树的一种,它是除了叶子节点外其余各节点都为满二叉树,叶子节点只在倒数第一层或第二层出现。
即使是最后一层的叶子节点也是从左到右依次排列,中间不会空。
每一层都是按从左到右的顺序编号,所以一个节点i
的叶子节点可以表示为2i
和2i + 1
。
完全二叉树和满二叉树的区别:
- 满二叉树一定是完全二叉树,反之则不然
- 满二叉树每个节点都有两个子节点(叶子节点除外),不会出现只有一个子节点的情况。
222. 完全二叉树的节点个数
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int countNodes(struct TreeNode* root) {
if(root == NULL) {
return NULL;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
文章来源:https://blog.csdn.net/m0_51425296/article/details/135035164
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!