常见数据结构 |
您所在的位置：网站首页 › 层序遍历的概念 › 常见数据结构 |
常见数据结构
|
完全二叉树
完全二叉树1、定义2、特征3、C++简单实现完全二叉树的节点个数
完全二叉树
1、定义
完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 若一棵二叉树至多只有最下面两层的结点的度数可以小于2，并且最下层的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。
叶子结点只可能在最下面的两层上出现，对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1； 出于简便起见，完全二叉树通常采用数组而不是链表存储，其存储结构如下: var tree : array[1...n] of object; {n:integer; n>=1}对于tree，有如下特点： （1）若i为奇数且i>1，那么tree[i]的左兄弟为tree[i-1]； （2）若i为偶数且i1，tree[i]的双亲为tree[i div 2]； （4）若2*i} }; void preOrderRecur(Node* head) {//前序遍历 if (head == nullptr) { return; } std::cout curlevel++; node = node->left; } return curlevel - 1;//这里表达的意思，减1，应该就是把根节点对应的层数减掉， //下面的程序有补充加上根节点数量的过程。 } //node当前节点，curlevel代表在第几层，depth二叉树的最大深度 int cbtNode(Node* node, int curlevel, int depth) { if (curlevel == depth) {//相当于只有根节点一个 return 1; } if (getMostLevel(node->right, curlevel + 1) == depth) {//情况1 //整体是以node为头的二叉树的节点个数。这里的curlevel + 1已经把node对应的节点层数加上去了。 return (1 if (head == nullptr) { return 0; } return cbtNode(head, 1, getMostLevel(head, 1)); } int main() { Node* head = new Node(1); head->left = new Node(2); head->right = new Node(3); head->left->left = new Node(4); head->left->right = new Node(5); head->right->left = new Node(6); std::cout |
以下都不是完全二叉树 
【本文地址】
今日新闻 |
推荐新闻 |